关于快速排序比较次数的问题

显示全部楼层 · 2008-10-30 11:47:32

不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。
1．n=7时在最好情况下需进行多少次比较？请说明理由。
对n=7给出一个最好情况的初始排列实例。
2．n=15时在最好情况下需进行多少次比较？请说明理由。
对n=15给出一个最好情况的初始排列实例

千问 · 2008-10-30 11:47:32

1，2，3，4，5，6，7；三次，最好就是第一次取到4，以4为列子，就是最好取到的数是位于中间大于左面3个，小于右边3个；第一次比较比4小的放左边，大的右边。然后第二次；以同样的方法再取，取到2，6最好啦；比较左右各一次；共2次。（这里我把左右比较用一个循环控制比较算做一次）n=15，就是俩个n=7就是3次了快排也有点像二路归并：从一个无序的序列中随机取出一个值q做为支点,然后把大于q的放到一边，小于q的放到q的另一边,然后再以q为分界点，分别对q的两边进行排序（快排时直接再对q两边重新取支点，整理，再取支点，...直到支点两旁都有序。也就是支点两旁只有一个数时）...

千问 · 2008-10-30 11:47:32

42315674作为中枢值，^231567->123^567->1234567...