段晓忠

[摘要]排序算法是算法的入门知识，即如何使得记录按照要求排列的方法，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。文章分析了常见的排序算法及其使用场景。

[关键词]排序算法；经典思想；使用场景

[DOI]1013939/jcnkizgsc201619189

1常见排序算法思想分析

11冒泡排序

冒泡排序是最简单的排序之一，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O（n^2）。

12插入排序

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O（n^2）。

13快速排序

在实际应用当中快速排序确实是表现最好的排序算法。冒泡排序虽然高端，但其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面，同时也把大数沉到下面。快速排序是不稳定的，其时间平均时间复杂度是O（nlgn）。

14堆排序

堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意，如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。首先，实现堆排序需要解决两个问题：①如何由一个无序序列键成一个堆？②如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。

第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整为筛选。

从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。

15希尔排序

希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O（n），如果序列是基本有序的，使用直接插入排序效率就非常高。其基本思想是：先将整个待排记录序列分割成为若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可，因此希尔排序的效率要比直接插入排序高。

希尔排序的分析是复杂的，时间复杂度是所取增量的函数，在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O（n^13）。

16归并排序

归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易。其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列……倒着来看，其实就是先两两合并，然后四四合并……最终形成有序序列。空间复杂度为O（n），时间复杂度为O（nlogn）。

17桶排序

假设有一组长度为N的待排关键字序列K[1，…，n]。首先将这个序列划分成M个的子区间（桶）。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中（即桶数组B的下标 i），那么该关键字k就作为B[i]中的元素（每个桶B[i]都是一组大小为N/M的序列）。接着对每个桶B[i]中的所有元素进行比较排序（可以使用快排）。然后依次枚举输出B[0]，…，B[M]中的全部内容即是一个有序序列。

bindex=f（key）

其中，bindex 为桶数组B的下标（即第bindex个桶），k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1

18基数排序

基数排序又是一种和前面排序方式不同的排序方式，基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面……如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。

2结论

在前面的介绍和分析中文章提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。其实排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的，需要结合具体的需求和场景来选择甚至组合使用，才能达到高效稳定的目的。没有最好的排序，只有最适合的排序。

下面就总结一下排序算法的各自的使用场景和适用场合：

（1）从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。

（2）上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。

（3）基数排序的时间复杂度也可以写成O（d*n）。因此它最适用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。

（4）从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O（n^2）的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。

（5）上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。

参考文献：

[1]李宝艳，马英红排序算法研究[J].电脑知识与技术：学术交流，2007（8）.

[2]梁利刚，易超，杨绣丞，等静态排序算法设计与分析[J].计算机应用与软件，2012（3）.