堆排序和快速排序（在快速排序， 堆排序，归并排序中 哪个是最稳定的排序方法）

本文目录

• 在快速排序， 堆排序，归并排序中 哪个是最稳定的排序方法
• 在快速排序、堆排序、归并排序中，什么排序是稳定的
• 对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序,最省时间的算法是什么
• C语言:若原始记录接近正序或反序，则选用堆排序，若初始记录无序则最好选用快速排序这是为什么
• 为什么在平均情况下，快速排序比堆排序要优秀
• 快速排序和堆排序都不稳定
• 堆排序与快速排序时间效率的一点问题
• 如何理解快速排序的效率高于归并排序，堆排序，如何

在快速排序， 堆排序，归并排序中 哪个是最稳定的排序方法

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《s《2 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好

在快速排序、堆排序、归并排序中，什么排序是稳定的

归并排序是稳定的排序算法。

归并排序的稳定性分析：

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素或者2个序列，然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。

可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等，没有外部干扰，将不会破坏稳定性。

那么，在短的有序序列合并的过程中，稳定性是没有受到破坏的，合并过程中如果两个当前元素相等时，把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

扩展资料：

算法稳定性的判断方法：

在常见的排序算法中，堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。

需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

比如，快速排序原本是不稳定的排序方法，但若待排序记录中只有一组具有相同关键码的记录，而选择的轴值恰好是这组相同关键码中的一个，此时的快速排序就是稳定的。

参考资料来源：百度百科-排序算法稳定性

对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序,最省时间的算法是什么

对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的算法是冒泡排序。

冒泡排序的最好比较次数为n次，最差比较次数为n＾2次，最差比较次数为0次，最差比较次数为n＾2次，最差比较次数为1次，最差比较次数为1次。

快速排序的最好比较次数为nlogn次，最差比较次数为n＾2次，最差比较次数为logn次，最差比较次数为n次，最差比较次数为logn次，最差比较次数为n次。

堆排序的最好比较次数为nlogn次，最差比较次数为nlogn次，最差比较次数为nlogn次，最差比较次数为nlogn次，最差比较次数为1次，最差比较次数为1次。

扩展资料：

冒泡排序（BubbleSort）重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

由于冒泡排序比较是相邻的两个元素，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

C语言:若原始记录接近正序或反序，则选用堆排序，若初始记录无序则最好选用快速排序这是为什么

1，堆排序的性能：时间复杂度总是Nlogn(N) 的。

2，快速排序不属于原地排序，由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。在平均情况下，需要O(logn) 的栈空间；最坏情况下，栈空间可达O(n) 。
1 ）划分元素的选取是影响时间性能的关键。
2 ）输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快。快速排序不是自然排序方法。
3 ）改变划分元素的选取方法，至多只能改变算法平均情况下的时间性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是O(n 2 )。

为什么在平均情况下，快速排序比堆排序要优秀

快速排序是二叉查找树（二叉查找树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数，但是顺序不同。对于排序算法的稳定性指标，原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。
快速排序的最直接竞争者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。然而，堆排序需要有效率的随机存取才能变成可行。
快速排序也与归并排序（Mergesort）竞争，这是另外一种递归排序算法，但有坏情况O(n log n)运行时间的优势。不像快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链表（linkedlist）和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在炼串列上，但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点，是在最佳情况下需要Ω(n)额外的空间。
快速排序和堆排序不稳定，归并排序稳定。

快速排序和堆排序都不稳定

不稳定：就是大小相同的两个数，经过排序后，最终位置与初始位置交换了。

快速排序：
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输出，不稳定。

堆排序与快速排序时间效率的一点问题

首先快排最适合用来排序完全随机的数据，此时不存在退化情况（只要不是人品极差，或者可以随机选择主元规避退化情况）。其次，虽然三者的渐进运行时间都是O(nlgn)，但隐藏在O里的系数快排是最小的。再次，快排和堆排是原址(in place)的，这一点归并在运行时还要负担额外的内存开销。故快排总体表现是最稳定的，也是工业上使用最为广泛的排序之一。

如何理解快速排序的效率高于归并排序，堆排序，如何

堆排序
平均时间：o(n*logn)
最坏：o(n*logn)
快速排序
平均时间：o(n*logn)
最坏：o(n的平方)
归并排序
平均时间：o(n*logn)
最坏：o(n的平方)
排序算法没有最快情况的说法。
从平均性能来说，快速排序最佳，因为所需时间最短，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。n较大时，归并排序所需时间较堆排序省，但归并排序需要的辅助存储量更大。