nnpc.net
当前位置:首页 >> 快速排序最好情况 >>

快速排序最好情况

最好的情况是每次都能均匀的划分序列.例如 4,1,3,2,6,5,7,每次使用序列的第一个元素做枢轴.比较总次数为10次,交换3次,具体如下:第一次枢轴为4,序列划分为{2,1,3},4,{6,5,7} 比较6次(4与每个元素比较一次),交换1次(4与2交换) 第二次的两个序列枢轴分别为2和6,此时划分序列得{1},2,{3},4,{5},6,{7} 比较4次(两个序列各比较两次),交换两次(1和2,6和5) 第三次由于各个序列的元素都为1,因此排序完成得1,2,3,4,5,6,7

最好的情况,每次都能均匀的划分序列. 时间复杂度O(nlogn) 最坏情况是枢纽元为最大或者最小数字,那么所有数都划分到一个序列去了 时间复杂度为O(n^2) 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.

一般情况下,快速排序效率要高于堆排序.因为堆排序的常数较大(不过也是1~2之间吧).快速排序的平均时间复杂度是o(1.39nlogn).一般来说,除非有需要绝对保证不能出现o(n^2)的要求,不使用堆排.堆排序需要有效的随机存取.

从时间复杂度看,所有内部排序方法可以分为两类. 1.插入排序 选择排序 起泡排序 其时间复杂度为o(n2); 2.堆排序 快速排序 归并排序 其时间复杂度为o(nlog2n). 这是就平均情况而言的,如果从最好的情况考虑, 则插入排序和起泡排序的时间复杂度最好,为o(n), 而其他算法的最好情况同平均情况大致相同. 如果从最坏的情况考虑,快速排序的时间复杂度为o(n2),插入排序和起泡排序虽然同平均情况相同,但系数大约增加一倍,运行速度降低一半,而选择排序、堆排序和归并排序则影响不大. 总之, 在平均情况下,快速排序最快; 在最好情况下,插入排序和起泡排序最快; 在最坏情况下,堆排序和归并排序最快.

快速排序最好的情况是每次把上一次的数组平均分成两个子数组.设数组总数一共为n,如果把这n个数每次分成2半最后每个数组只包含一个元素,假设要分k次,则2的k次方=n,解得k=log2 n(log以2为底对n取对数).也就是说要分log2 n次,而每次都是处理n个数据.所以总的时间复杂度为O(n*log2 n).

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两边重新取支点,整理,再取支点,直到支点两旁都有序.也就是支点两旁只有一个数时)

最坏情况下比较次数最少的为D)堆排序:A)冒泡排序 需要比较O(n^2)次(n(n - 1)/2次),即序列逆序的情况 B)简单选择排序,无论是否最坏都需要O(n^2)次(n(n - 1)/2次) C)直接插入排序,最坏情况需要比较O(n^2)次(n(n - 1)/2次) D)堆排序,无论是否最坏比较O(nlog2n)次 E)快速排序,最坏情况退化为冒泡排序,需要比较O(n^2)次(n(n - 1)/2次)

快速排序是先找到一个轴值,比较时把所有比轴值小的放到轴值的左边, 比轴值大的放到右边,再在两边各自选取轴值再按前面排序,直到完成 (1)已经排序完成,是最快的; (2)反序,需要将小于5的转移到5的左边,大于5的转移到5的右边,每个数都要经过比较,所以是最慢的 (3)轴值为9,需要将9右边的转移到左边,比较次数介于(1),(2)之间; (4)轴值为5,需要将左边的9转移到5的右边,3转移到5的左边; 总体比较次数(1)

楼上说的是什么啊,最坏情况下,是整个序列都已经有序且完全倒序 ,此时,快速排序退化为冒泡排序,要比较n*(n-1)/2次才能完成 最好的情况下只需一次!

快排最好nlogn,最坏n*n.将n=100000000带进去大致是最好26.57亿,最坏1亿亿.

sytn.net | rprt.net | gmcy.net | jmfs.net | qwfc.net | 网站首页 | 网站地图
All rights reserved Powered by www.nnpc.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com