快速排序、堆排序、归并排序中哪种排序方式最稳定？

快速排序是一种局部排序、分治、大规模递归算法。本质上，它是合并排序的就地版本。快速排序可由以下四个步骤组成。

(1)如果数据不超过1，直接返回。

(2)一般选取序列最左边的值作为支点数据。

(3)将序列分成两部分，一部分大于支点数据，另一部分小于支点数据。

(4)递归排序两边的序列。

快速排序比大多数排序算法都快。虽然我们可以写一个在某些特殊情况下比快速排序更快的算法，但是一般来说，没有比它更快的了。快速排序是递归的，这对于内存非常有限的机器来说不是一个好的选择。

2合并排序(MergeSort)

归并排序首先分解要排序的序列，从1到2，2到4，然后依次分解。当只分解1组时，可以对这些组进行排序，然后依次合并回原序列，这样就可以对所有数据进行排序。合并排序比堆排序快一点，但是它需要两倍于堆排序的内存空间，因为它需要一个额外的数组。

3堆排序(HeapSort)

堆排序适用于数据非常大(数百万数据)的情况。

堆排序不需要大量的递归或多维临时数组。这适用于数据量非常大的序列。比如有几百万条以上的记录，因为快速排序和归并排序都是用递归来设计算法，在数据量非常大的情况下可能会出现堆栈溢出错误。

堆排序会将所有数据构建成一个堆，最大的数据放在堆的顶部，然后将顶部的数据与序列的最后一个数据交换。然后再次重建堆，交换数据，依次进行，就可以对所有数据进行排序了。

4壳排序

Shell排序将数据分成不同的组，先对每个组进行排序，然后一次性插入所有元素，减少数据交换和移动的次数。平均效率为O(nlogn)。分组的合理性会对算法产生重要影响。现在经常使用D.E.Knuth的分组方法。

外壳排序比冒泡排序快5倍，比插入排序快2倍。Shell排序比QuickSort，MergeSort，HeapSort慢很多。但相对简单，适用于数据量在5000以下，速度不是特别重要的情况。对于小数据量的数据序列的重复排序非常好。

5插入排序(插入排序)

插入排序是通过将序列中的值插入到已经排序的序列中，直到序列结束。插入排序是对冒泡排序的改进。它比冒泡排序快一倍。通常，当数据大于1000时，没有必要使用插入排序，或者重复排序超过200个数据项的序列。

6泡排序

冒泡排序是最慢的排序算法。它是实际应用中效率最低的算法。它反复比较数组中的每个元素，使较大的数据下沉，较小的数据上升。就是O(n ^ 2)的算法。

7交换排序和选择排序排序。

这两种排序方法都是交换法的排序算法，效率都是O(n2)。在实际应用中，它与冒泡排序处于相同的位置。它们只是排序算法发展的初级阶段，在实践中很少使用。

8半径排序

基数排序与通常的排序算法不同。这是一个新颖的算法，但它只能用于排序整数。如果要把同样的方法应用到浮点数上，就必须了解浮点数的存储格式，用特殊的方式把浮点数映射到整数上，然后再映射回来。这是个很麻烦的东西，所以用的不多。而且，最重要的是，这个算法还需要更多的存储空间。

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是基数(一百)

壳牌O(nlogn)O(ns)1 & lt；s & lt2不稳定O(1) s是选择的数据包。

快O(nlogn) O(n2)不稳定O(nlogn) n更好。

最好合并O(nlogn) O(nlogn)，稳定O (1) N。

当O(nlogn) O(nlogn)不稳定且O(1) n较大时更好。