排序算法总结

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

一、 排序问题

1.1 排序问题的定义

排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。

设R为非空集合A上的二元关系，如果R满足自反性(对于每一个x?A，

(x,x)?R)，反对称性((x,y)?R&(y,x)?R?x?y)和传递性

((x,y)?R&(y,z)?R?(x,z)?R)，则称R为A上的偏序关系，记作?。如果

(x,y)?R，则记作x?y，读作“x小于等于y”。存在偏序关系的集合A称为

偏序集。（注意，这里的?不是指数的大小，而是指在偏序关系中的顺序性。x?y的含

义是：按照这个序，x排在y前面。根据不同的偏序定义，?有不同的解释。例如整除关系是偏序关系?，3?6的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系5?4是指在大于或等于关系中5排在4的前面，也就是说5比4大。）

在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个主键域key，key域的类型是某一个偏序集，记录的其他域称为数据。比较线性表中的两个元素Li和Lj的大小，实际上是比较Li.key和Lj.key的大小（这种比较当然也是偏序集中的比较）。举例而言，某公司的数据库里记 录了员工的数据，每一项纪录包括姓名，编号，年龄，工资等几个域，如果以编号为key域对员工记录排序，则是将员工记录按照编号排序；如果以工资为key域对员工记录排序，则是将员工记录按照工资高低排序；如果以姓名为key域对员工记录排序，则是以员工姓名的汉语拼音按照字典顺序排序。 1.2 排序问题的分类

如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做原地置换排序算法(in place sort)；如果排序后并不改变表中相同的元素原来的相对位置，那么这种排序算法叫做稳定排序算法(stable sort)。

排序问题一般分为内排序( internal sorting )和外排序( external sorting )两类： 内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中；

外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。 1.3 排序问题的计算复杂性

对排序算法计算时间的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。

为了对有n个元素的线性表进行排序，至少必须扫描线性表一遍以获取这n

个元素的信息，因此排序问题的计算复杂性下界为?(n)。

如果我们对输入的数据不做任何要求，我们所能获得的唯一信息就是各个元素的具体的值，我们仅能通过比较来确定输入序列的元素间次序。

即给定两个元素ai和aj，通过测试ai?aj,ai?aj,ai?aj,ai?aj,ai?aj中的哪一个成立来确定ai和aj间的相对次序。这样的排序算法称为比较排序算法。下面我们讨论一下比较排序算法在最坏情况下至少需要多少次比较，即比较排序算法的最坏情况复杂性下界。

我们假设每次比较只测试ai?aj ，如果ai?aj 成立则ai排在aj 前面，否则ai排在aj 后面。任何一个比较排序算法可以描述为一串比较序列:

(ai,aj),(ak,al),,(am,an),

表示我们首先比较(ai,aj)，然后比较(ak,al)，...，比较(am,an)，...，直到我们获取了足够的信息可以确定所有元素的顺序。显而易见，如果我们对所有的元素两

2两进行一次比较的话(总共比较了Cn次)，就一定可以确定所有元素的顺序。但是，

如果我们运气足够好的话，我们可能不必对所有元素两两进行一次比较。比如说对于有三个元素的线性表进行排序，如果我们先比较a1和a2，得到

a1?a2；然后比较a2和a3，得到a2?a3；则不必比较a1和a3，因为根据偏序集的传递性，必有a1?a3；但是如果a2?a3，我们还必须比较a1和a3才能确定a1和

a3的相对位置。如果我们适当的安排比较的次序的话，也可以减少比较的次数。这样我们可以用一棵二叉树表示比较的顺序，如下图所示：

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

图 二叉树表示比较的顺序

该树的每一个非叶节点表示一次比较，每一根树枝表示一种比较结果，每一个叶节点表示一种排列顺序。这样的一棵二叉树叫做决策树，它用树枝表示了每次决策做出的选择。如此我们可以将任何一个比较排序算法用一棵决策树来表示。

请注意上图只表明了对三个元素的一种比较算法，这种比较算法依次比较

(a1,a2),(a2,a3),(a1,a3)，一旦中间某步得到足够的信息就可以停止比较，但是当算法执行完后（三次比较后），一定可以确定三个元素间的次序。因此我们有理由将算法在最坏情况下的比较次数作为算法复杂性的度量，对于本例该算法在最坏情况下要进行C32次比较。

显然，一棵决策树中最高叶节点的高度就是该决策树对应的算法在最坏情况下所需的比较次数，而决策树中最低叶节点的高度就是该决策树对应的算法在最好情况下所需的比较次数。

我们的问题就变为：对于任意一棵决策树（任意一种比较排序算法），它的最高的树叶的高度是多少？这个高度就对应于比较排序算法所需的最多比较次数（在运气最坏的情况下）；换句话说，对于任何一个输入，该算法至少需要比较多少次就可以对元素进行排序。

我们发现，决策树的每个叶节点对应一个n个元素的排列，其中可能有重复的；但是由于决策树表明了所有可能遇到的情况，因而n个元素的所有排列都在决策树中出现过。n个元素共有n!种排列，即决策树的叶节点数目至少为n!。又因为一棵高度为h的二叉树（指二叉树的最高树叶高度为h）的叶节点数目最多为2h个（这时正好是满二叉树，即每个非叶节点都有两个子节点），因此n!?2h，得到h?log(n!)，其中log以2为底。根据Stirling公式有n!?(n/e)n，于是

h?nlog(n)?nlog(e)，即h??(nlog(n))。

这样我们就证明了对于任意一种利用比较来确定元素间相对位置的排序算法，其最坏情况下复杂性为?(nlog(n))。

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

在下文中我们将讨论几种比较排序算法，其中快速排序在平均情况下复杂性为

O(nlog(n))，最坏情况下复杂性为O(n2)；堆排序和合并排序在最坏情况下复杂性为O(nlog(n))，因此堆排序和合并排序是渐进最优的比较排序算法。

排序算法是否还能够改进呢？从前文我们知道，如果要改进排序算法的效率，就不能只利用比较来确定元素间相对位置。因此我们还需要知道元素的其他附加信息，光知道元素的大小信息是不够的。下文中我们介绍的计数排序，基数排序和桶排序是具有线性时间复杂性的排序算法，这些算法无一例外地对输入数据作了某些附加限制，从而增加已知的信息，因此可以不通过比较来确定元素间的相对位置。

1.4 常见排序算法

表 各排序算法的时间复杂度、空间复杂度及稳定性

类别 排序方法 直接插入 插入排序 时间复杂度 平均情况 最好情况 最坏情况 空间复杂度 辅助存储 稳定性 稳定 O(n2) O(nlog2n) O(n2) O(n) O(n) O(n2) O(nlog2n) O(1) O(1) 希尔排序 不稳定 直接选择 选择排序 O(n2) O(n2) O(nlog2n) O(1) O(1) 不稳定 堆排序 O(nlog2n) O(nlog2n) O(n2) O(n) 不稳定 交换排序 冒泡排序 快速排序 O(n2) O(1) 稳定 O(nlog2n) O(nlog2n) O(nlog2n) O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定 归并排序 O(n) 稳定 基数排序 O(d(r?n)) O(d(n?rd)) O(d(r?n)) O(rd?n) 稳定 二、直接插入排序法(插入排序)

2.1 算法思想

每次选择一个元素K插入到之前已排好序的部分A[1?i]中，插入过程中K依次由后向前与A[1?i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

A[x]的后面，插入前需要移动元素。

图 直接插入排序法思想

2.2 代码实现(C语言)

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

//参数：Array:待排序序列，n:序列长度，AscendFlag:升降排序标志位，true为升序 template //使用函数模板，方便适应各种类型数据的排序 bool InsertSort(DataType Array[],int n,bool AscendFlag = true) { if (Array == NULL || n < 1) //判断待排序序列的有效性 { return false; } int i,j; DataType temp; if (AscendFlag) //若为升序，进行升序排序 { for (i =1;i=0 && temp < Array[j]); Array[j+1] = temp; } } } else //若为降序，进行降序排序 { for (i =1;i Array[i-1]) { temp = Array[i]; j = i-1; 注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

} } } } return true; do { Array[j+1] = Array[j]; j--; }while (j>=0 && temp > Array[j]); Array[j+1] = temp; 2.3 算法时间复杂度

最好的情况下：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)。

最坏的情况下：逆序有序,这样每一个元素就需要比较n次，共有n个元素，

2因此实际复杂度为O(n)。 2O(n)。 平均情况下：

2.4 稳定性

稳定性，就是有两个相同的元素，排序先后的相对位置是否变化，主要用在

排序时有多个排序规则的情况下。在插入排序中，K1是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面(没有必要插到K1的前面，这样做还需要移动！！)，因此，插入排序是稳定的。、

三、希尔排序算法(插入排序)

3.1算法思想

希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。它的基本思想是先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量(d2?d1),重复上述的分组和排序,直至所取的增量dt?1(dt?dt?1??d2?d1),即所有记录放在同一组中进行直接插入排序为

止。 该方法实质上是一种分组插入方法。 例如：将 n 个记录分成d个子序列：

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

{R[0]{R[1]R[d]R[1?d]R[2d]R[1?2d]R[kd]}R[1?kd]}

{R[d?1]{R[2d?1]{R[3d?1]

{R[(k?1)d?1]}

图 希尔排序示例

说明：d?5 时，先从A[d]开始向前插入，判断A[d?d]，然后A[d?1]与

A[(d?1)?d]比较，如此类推，这一回合后将原序列分为d个组。<由后向前> 3.2代码实现(C语言)

//参数：Array:待排序序列，n:序列长度，AscendFlag:升降排序标志位，true为升序 template bool ShellSort(DataType Array[],int n,bool AscendFlag) { if (Array == NULL || n < 1) //判断待排序序列的有效性 { return false; } int i,j; int d = n/2; //d的初值取为n/2 DataType temp; while (d > 0) { for (i=d;i

{ j = i - d; while(j >= 0) { if (AscendFlag) { if (Array[j] > Array[j+d]) //将Array[j]与Array[j+d]交换 { temp = Array[j]; Array[j] = Array[j+d]; Array[j+d] = temp; } } else { if (Array[j] < Array[j+d]) //将Array[j]与Array[j+d]交换 { temp = Array[j]; Array[j] = Array[j+d]; Array[j+d] = temp; } } j = j-d; } //递减增量d } d = d/2; } return true; 3.3算法时间复杂度

最好情况：由于希尔排序的好坏和步长d的选择有很多关系，因此，目前还没有得出最好的步长如何选择(现在有些比较好的选择了，但不确定是否是最好的)。所以，不知道最好的情况下的算法时间复杂度。

最坏情况下：O(N*logN)，最坏的情况下和平均情况下差不多。 平均情况下：O(N*logN)。 3.4稳定性

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(方便记忆：一般来说，若存在不相邻元素间交换，则很可能是不稳定的排序。)

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

四、冒泡排序算法(交换排序)

4.1算法思想

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

//参数：Array:待排序序列，n:序列长度，AscendFlag:升降排序标志位，true为升序 template bool BubbletSort(DataType Array[],int n,bool AscendFlag = true) { if (Array == NULL || n < 1) //判断待排序序列的有效性 { return false; } int i,j; bool IsChanged = false; //发生交换标识 DataType temp; for (i = 0;i < n;i++) { IsChanged = false; for (j = n-1;j >= i;j--) { if (AscendFlag) { if (Array[j+1]Array[j]) { temp = Array[j+1]; Array[j+1] = Array[j]; Array[j] = temp;

本文来源：https://www.bwwdw.com/article/zj7t.html