算法快速与合并排序的总结

⑴ 关于快速排序和归并排序的时间复杂度

首先你说归并排序最坏的情形为O(NlogN)，这是不正确的归并排序如果不借助辅助空间的话，复杂度为O(n^2)，借助的话就是O(nlogn)(O(nlog2n))归并排序 平均复杂度是 O(nlogn) 比较快
快速排序快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。
综合来说快速排序速度最快，时间复杂度最小。希望对你有所帮助！

⑵ 排序算法概述

十大排序算法：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序、希尔排序、计数排序，基数排序，桶排序

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。

算法的复杂度往往取决于数据的规模大小和数据本身分布性质。
时间复杂度 ： 一个算法执行所耗费的时间。
空间复杂度 ：对一个算法在运行过程中临时占用存储空间大小的量度。
常见复杂度由小到大 ：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

在各种不同算法中，若算法中语句执行次数(占用空间)为一个常数，则复杂度为O(1)；
当一个算法的复杂度与以2为底的n的对数成正比时，可表示为O(log n)；
当一个算法的复杂度与n成线性比例关系时，可表示为O (n)，依次类推。

冒泡、选择、插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为
（一遍找元素O(n)，一遍找位置O(n)）
快速、归并、堆基于分治思想，log以2为底，平均时间复杂度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相关
而希尔排序依赖于所取增量序列的性质，但是到目前为止还没有一个最好的增量序列 。例如希尔增量序列时间复杂度为O(n²)，而Hibbard增量序列的希尔排序的时间复杂度为 ， 有人在大量的实验后得出结论;当n在某个特定的范围后希尔排序的最小时间复杂度大约为n^1.3。

从平均时间来看，快速排序是效率最高的：
快速排序中平均时间复杂度O(nlog n)，这个公式中隐含的常数因子很小，比归并排序的O(nlog n)中的要小很多，所以大多数情况下，快速排序总是优于合并排序的。

而堆排序的平均时间复杂度也是O(nlog n)，但是堆排序存在着重建堆的过程，它把根节点移除后，把最后的叶子结点拿上来后需要重建堆，但是，拿上的值是要比它的两个叶子结点要差很多的，一般要比较很多次，才能回到合适的位置。堆排序就会有很多的时间耗在堆调整上。

虽然快速排序的最坏情况为排序规模（n）的平方关系，但是这种最坏情况取决于每次选择的基准， 对于这种情况，已经提出了很多优化的方法，比如三取样划分和Dual-Pivot快排。
同时，当排序规模较小时，划分的平衡性容易被打破，而且频繁的方法调用超过了O(nlog n)为
省出的时间，所以一般排序规模较小时，会改用插入排序或者其他排序算法。

一种简单的排序算法。它反复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这个工作重复地进行直到没有元素再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为元素会经由交换慢慢“浮”到数列的顶端。
1.从数组头开始，比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到尾部的最后一对，这样在最后的元素应该会是最大(小)的数；
3.重复步骤1~2，重复次数等于数组的长度，直到排序完成。

首先，找到数组中最大（小）的那个元素；
其次，将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）；
再次，在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。
这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最大（小）者。

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素在都向后移动一位。
插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。
总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。

一种基于插入排序的快速的排序算法。简单插入排序对于大规模乱序数组很慢，因为元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1 次移动。
希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法是突破O(n^2）的第一批算法之一。
希尔排序是把待排序数组按一定数量的分组，对每组使用直接插入排序算法排序；然后缩小数量继续分组排序，随着数量逐渐减少，每组包含的元素越来越多，当数量减至 1 时，整个数组恰被分成一组，排序便完成了。这个不断缩小的数量，就构成了一个增量序列。

在先前较大的增量下每个子序列的规模都不大,用直接插入排序效率都较高，尽管在随后的增量递减分组中子序列越来越大,由于整个序列的有序性也越来越明显,则排序效率依然较高。
从理论上说，只要一个数组是递减的，并且最后一个值是1，都可以作为增量序列使用。有没有一个步长序列,使得排序过程中所需的比较和移动次数相对较少,并且无论待排序列记录数有多少,算法的时间复杂度都能渐近最佳呢？但是目前从数学上来说，无法证明某个序列是“最好的”。
常用的增量序列
希尔增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N为原始数组的长度，这是最常用的序列，但却不是最好的
Hibbard序列：{2^k-1, ..., 3,1}
Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表达式为

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。
为了提升性能，有时我们在半子表的个数小于某个数（比如15）的情况下，对半子表的排序采用其他排序算法，比如插入排序。
若将两个有序表合并成一个有序表，称为2-路归并，与之对应的还有多路归并。

快速排序（Quicksort）是对冒泡排序的一种改进，也是采用分治法的一个典型的应用。
首先任意选取一个数据（比如数组的第一个数）作为关键数据，我们称为基准数(Pivot)，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序，也称为分区（partition）操作。
通过一趟快速排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数组变成有序序列。
为了提升性能，有时我们在分割后独立的两部分的个数小于某个数（比如15）的情况下，会采用其他排序算法，比如插入排序。

基准的选取：最优的情况是基准值刚好取在无序区数值的中位数，这样能够最大效率地让两边排序，同时最大地减少递归划分的次数，但是一般很难做到最优。基准的选取一般有三种方式，选取数组的第一个元素，选取数组的最后一个元素，以及选取第一个、最后一个以及中间的元素的中位数（如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为5, 所以选择5作为基准）。
Dual-Pivot快排：双基准快速排序算法，其实就是用两个基准数, 把整个数组分成三份来进行快速排序，在这种新的算法下面，比经典快排从实验来看节省了10%的时间。

许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将他们排序，很多时候，我们每次只需要操作数据中的最大元素（最小元素），那么有一种基于二叉堆的数据结构可以提供支持。
所谓二叉堆，是一个完全二叉树的结构，同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在一个二叉堆中，根节点总是最大（或者最小）节点。
堆排序算法就是抓住了这一特点，每次都取堆顶的元素，然后将剩余的元素重新调整为最大（最小）堆，依次类推，最终得到排序的序列。

推论1：对于位置为K的结点 左子结点=2 k+1 右子结点=2 (k+1)
验证：C:2 2 2+1=5 2 (2+1)=6
推论2：最后一个非叶节点的位置为 (N/2)-1，N为数组长度。
验证：数组长度为6，(6/2)-1=2

计数排序对一定范围内的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序，而且待排序元素值分布较连续、跨度小的情况。
计数排序是一个排序时不比较元素大小的排序算法。
如果一个数组里所有元素都是整数，而且都在0-K以内。对于数组里每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，利用某种函数的映射关系将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序）。
桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做排序即可。

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。基数排序不是基于比较的算法。
基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。

基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：
MSD 从高位开始进行排序
LSD 从低位开始进行排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值

有时，待排序的文件很大，计算机内存不能容纳整个文件，这时候对文件就不能使用内部排序了（我们一般的排序都是在内存中做的，所以称之为内部排序，而外部排序是指待排序的内容不能在内存中一下子完成，它需要做内外存的内容交换），外部排序常采用的排序方法也是归并排序，这种归并方法由两个不同的阶段组成：
采用适当的内部排序方法对输入文件的每个片段进行排序，将排好序的片段（成为归并段）写到外部存储器中（通常由一个可用的磁盘作为临时缓冲区），这样临时缓冲区中的每个归并段的内容是有序的。
利用归并算法，归并第一阶段生成的归并段，直到只剩下一个归并段为止。

例如要对外存中4500个记录进行归并，而内存大小只能容纳750个记录，在第一阶段，我们可以每次读取750个记录进行排序，这样可以分六次读取，进行排序，可以得到六个有序的归并段
每个归并段的大小是750个记录，并将这些归并段全部写到临时缓冲区（由一个可用的磁盘充当）内了，这是第一步的排序结果。
完成第二步该怎么做呢？这时候归并算法就有用处了。

⑶ 各种排序算法的总结和比较

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

点击以下图片查看大图：

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模 k："桶"的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

包含以下内容：

1、冒泡排序 2、选择排序 3、插入排序 4、希尔排序 5、归并排序 6、快速排序 7、堆排序 8、计数排序 9、桶排序 10、基数排序

排序算法包含的相关内容具体如下：

冒泡排序算法

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

选择排序算法

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

插入排序算法

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

希尔排序算法

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

归并排序算法

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

计数排序算法

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

桶排序算法

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

基数排序算法

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

⑷ 快速排序算法原理与实现

快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边。

然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。

以下的代码中会常常使用交换数组中两个元素值的Swap方法，其代码如下

publicstaticvoidSwap(int[] A, inti, intj){

inttmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

(4)算法快速与合并排序的总结扩展阅读：

快速排序算法 的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直 到所有要进行排序的数据变为有序为止。

定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通 常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划 分序列的起始元素决定。

从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值 为 key。

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

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

⑹ 合并排序和快速排序的区别

归并排序，简单来说就是先将数组不断细分成最小的单位，然后每个单位分别排序，排序完毕后合并，重复以上过程最后就可以得到排序结果。
快速排序，简单来说就是先选定一个基准元素，然后以该基准元素划分数组，再在被划分的部分重复以上过程，最后可以得到排序结果。
两者都是用分治法的思想，不过最后归并排序的合并操作比快速排序的要繁琐。

⑺ 插入排序、合并排序和快速排序算法的C语言实现与性能比较

前三个的实现很简单，代码也是很容易找的，不过楼上说的clock()函数可能无法统计函数调用所用的时间，那个只能统计某一段所用的时间，而不包括某个函数调用的时间呢

不过可以用
#include<time.h>

的
LARGE_INTEGER BegainTime ;
LARGE_INTEGER EndTime ;
LARGE_INTEGER Frequency ;

QueryPerformanceFrequency(&Frequency);
QueryPerformanceCounter(&BegainTime) ;
调用的函数；
QueryPerformanceCounter(&EndTime);
printf("运行时间（单位：s）：%f" ,(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart)

⑻ 几种排序方法

这两天复习了一下排序方面的知识，现将目前比较常见的整理一下。 选择排序选择排序的思想是首先先找到序列中最大元素并将它与序列中最后一个元素交换，然后找下一个最大元素并与倒数第二个元素交换，依次类推。此排序很简单，这不做多说，代码实现如下：View Code插入排序算法流程：1. 从第一个元素开始，该元素可以认为已经被排序 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到下一位置中 6. 重复步骤2View Code冒泡排序依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 View Code合并排序在介绍合并排序之前，首先介绍下递归设计的技术，称为分治法。分治法的核心思想是：当问题比较小时，直接解决。当问题比较大时，将问题分为两个较小的子问题，每个子问题约为原来的一半。使用递归调用解决每个子问题。递归调用结束后，常常需要额外的处理，将较小的问题的结果合并，得到较大的问题的答案。 合并排序算法在接近数组中间的位置划分数组，然后使用递归运算对两个一半元素构成的数组进行排序，最后将两个子数组进行合并，形成一个新的已排好序的数组。 代码如下：View Code快速排序快速排序与合并排序有着很多相似性。将要排序的数组分成两个子数组，通过两次递归调用分别对两个数组进行排序，再将已经排好序的两个数组合并成一个独立的有序数组。但是，将数组一分为二的做法比合并排序中使用的简单方法复杂的多。它需要将所有小于或者等于基准元素的元素放置到基准元素前面的位置，将大于基准的元素放置到基准后面的位置。

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

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

归并排序的稳定性分析：

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

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

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

(9)算法快速与合并排序的总结扩展阅读：

算法稳定性的判断方法：

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

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

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

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

参考资料来源：网络-排序算法稳定性

⑽ 常见的几种排序算法总结

对于非科班生的我来说，算法似乎对我来说是个难点，查阅了一些资料，趁此来了解一下几种排序算法。
首先了解一下，什么是程序

关于排序算法通常我们所说的往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等

冒泡排序它重复地走访过要排序的元素，一次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

选择排序类似于冒泡排序，只不过选择排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

插入排序比冒泡排序和选择排序更有效率，插入排序类似于生活中抓扑克牌来。
插入排序具体算法描述，以数组[3, 2, 4, 5, 1]为例。

前面三种排序算法只有教学价值，因为效率低，很少实际使用。归并排序（Merge sort）则是一种被广泛使用的排序方法。
它的基本思想是，将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。
以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下：

有了merge函数，就可以对任意数组排序了。基本方法是将数组不断地拆成两半，直到每一半只包含零个元素或一个元素为止，然后就用merge函数，将拆成两半的数组不断合并，直到合并成一整个排序完成的数组。

快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。
快速排序算法步骤

参考：
常用排序算法总结(一)
阮一峰-算法总结