1楼：奔跑吧皮皮虾
是归并排序，我刚刚也做
这个题目。 因为堆排序时间复杂度为n*logn，空间复杂度为1，是不稳定排序，适合较多情况； 而归并排序的时间复杂度为n*logn，空间复杂度为n，是稳定排序。 快速排序的时间复杂度为n，空间复杂度最好的情况是logn
2楼：墨易展寒烟
首先你说归并排序最坏的情形为o(nlogn)，这是不正确的归并排序如果不借助辅助空间的话，复杂度为o(n^2)，借助的话就是o(nlogn)(o(nlog2n))归并排序
平均复杂度是
o(nlogn)
比较快快速排序快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。
一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是o(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。
所以随机化快速排序可以对于绝大多数输入数据达到o(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。
”随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到o(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。
综合来说快速排序速度最快，时间复杂度最小。希望对你有所帮助！
我实验怎么得出归并排序比快速排序要快啊,谁能告诉我为什么啊 20
3楼：匿名用户
数据分配够随机吗？有多少重复的？
你的快速排序其实可以有些需要优化的地方的。
关于快速排序和归并排序的时间复杂度
4楼：匿名用户
首先你说归并排序最坏的情形为o(nlogn)，这是不正确的归并排序如果不借助辅助空间的话，复杂度为o(n^2)，借助的话就是o(nlogn)(o(nlog2n))归并排序 平均复杂度是 o(nlogn) 比较快
快速排序快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。
一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是o(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。
所以随机化快速排序可以对于绝大多数输入数据达到o(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。
”随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到o(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。
综合来说快速排序速度最快，时间复杂度最小。希望对你有所帮助！
在快速排序、堆排序、归并排序中，什么排序是稳定的？
5楼：沉珂侧畔
归并排序是稳定的“快速排序和堆排序都不稳定.不稳定：就是大小相同的两个数，经过排序后，最终位置与初始位置交换了。
快速排序：
27 23 27 3
以第一个27作为pivot中心点，则27与后面那个3交换，形成
3 23 27 27，排序经过一次结束，但最后那个27在排序之初先于初始位置3那个27，所以不稳定。
堆排序：
比如：3 27 36 27，
如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。”
“2 归并排序（mergesort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。”
以ai与aj为例子
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_indexij都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。
交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。
在快速排序， 堆排序，归并排序中 哪个是最稳定的排序方法？ 20
6楼：匿名用户
1 快速排序（quicksort）
快速排序是一个就地排序，分而治之，大规模递归的算法。
从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。
（2） 一般选择序列最左边的值作为支点数据。
（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2 归并排序（mergesort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3 堆排序（heapsort）
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 shell排序（shellsort）
shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是o(nlogn)。其中分组的合理性会对算法产生重要的影响。
现在多用d.e.knuth的分组方法。
shell排序比冒泡排序快5倍，比插入排序大致快2倍。shell排序比起quicksort，mergesort，heapsort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。
它对于数据量较小的数列重复排序是非常好的。
5 插入排序（insertsort）
插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。
一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。
6 冒泡排序（bubblesort）
冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是o(n^2)的算法。
7 交换排序（exchangesort）和选择排序（selectsort）
这两种排序方法都是交换方法的排序算法，效率都是 o(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。
8 基数排序（radixsort）
基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。
9 总结
下面是一个总的**，大致总结了我们常见的所有的排序算法的特点。
排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 o(n2) o(n2) 稳定 o(1) n小时较好
交换 o(n2) o(n2) 不稳定 o(1) n小时较好
选择 o(n2) o(n2) 不稳定 o(1) n小时较好
插入 o(n2) o(n2) 稳定 o(1) 大部分已排序时较好
基数 o(logrb) o(logrb) 稳定 o(n)
b是真数(0-9)，
r是基数(个十百)
shell o(nlogn) o(ns) 1 快速 o(nlogn) o(n2) 不稳定 o(nlogn) n大时较好 归并 o(nlogn) o(nlogn) 稳定 o(1) n大时较好 堆 o(nlogn) o(nlogn) 不稳定 o(1) n大时较好 7楼：无心字 是归并排序，我刚刚也做这个题目。 因为堆排序时间复杂度为n*logn，空间复杂度为1，是不稳定排序，适合较多情况； 而归并排序的时间复杂度为n*logn，空间复杂度为n，是稳定排序。 快速排序的时间复杂度为n，空间复杂度最好的情况是logn，最坏的情况是n^2，是不稳定的排序方法。（书本原话）。 8楼：庆纯 堆排序 n*logn 时间在这里比较优 不过稳定性差快排 o(nlogn)，最坏情况为o(n^2)。在实际应用中，快速排序的平均时间复杂度为o(nlogn)。 比较均衡 直接插入排序，简单选择排序 n^2 希尔排序和基数排序 不太了解 空间的话 个人认为是一样的 因为你要用同样的数组去存 只是存的顺序不同罢了 时间的话 100w以内 快排 最优 100w以上 堆排的优越性就明显出来了 所以一般快排就可以满足 1楼 carry 小小 二分法插入排序 复杂度 o nlogn 快速排序 o nlogn 有可能退化归并排序 o nlogn 比较快 堆排序 o nlogn 最稳定的 在快速排序 堆排序 归并排序中，什么排序是稳定的？ 2楼 沉珂侧畔 归并排序是稳定的 快速排序和堆排序都不稳定 不稳定 就是大小相同... 1楼 匿名用户 内存空间不足的时候使用归并排序，能够使用并行计算的时候使用归并排序。 对时间复杂度o nlogn 依然不满意的情况下使用快速排序。 2楼 杭幻梅吉名 总体上是快排 详细的说 若数据比较无序，快排快。 若数据中部分有序，归并快。 建议你使用快排，因为就算归并快，也快不了多少。而快排能处... 1楼 q给你毛起 关键字比较次数永远是n n 1 2，记录移动次数最多为3 n 1 ，最少0次，前者起主导作用，因此实际上时间复杂度还是o n 2 。 在直接选择排序中，共需要进行n 1次选择和交换，每次选择需要进行 n i 次比较 1 i n 1 而每次交换最多需要3次移动，因此，总的比较次数c ...“二分法插入排序快速排序归并排序”和“堆排序”的
什么时候用归并排序，什么时候用快速排序
直接选择排序算法在最好情况下的时间复杂度为多少