迹忆客 专注技术分享

本篇给大家介绍几种软件工程中常用的排序算法

所有排序算法的核心的代码都在《常用排序算法核心代码》有介绍

1. 插入排序

插入排序的基本思想就是：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中，直到全部记录插入完成为止。

对于插入排序的概念以及其原理大家可以参考《排序算法的学习之路——插入排序（概念篇）》

插入排序细分可以分成三种情况。

直接插入排序——《排序算法学习之路——直接插入排序》

折半插入排序——《排序算法学习之路——折半插入排序》

表插入排序  ——《排序算法学习之路——表插入排序》

2. 希尔排序

希尔排序是按照该算法的设计者的名字希尔 命名的，其产生是希尔在插入排序的基础上改进的，可以说是一种特殊的插入排序。

下面先介绍一下插入排序的性质：

首先，插入排序算法对于已经有序的数据进行操作的时候，效率很高，可以达到线性排序的效率。

其次，插入排序进行排序的时候，每一趟排序只能移动一个数据。所以说这样的排序方法相对来说效率又比较低。

基于此性质，希尔排序的设计者发明了希尔排序算法，其基本思想是：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，分割子序列的方法就是设定一个增量，待当下的每个子序列有序的时候，将增量减一半（除 以2，取整），再次进行子序列的排序。依次进行，待整个序列中的记录基本上有序的时候，再对全体记录进行依次直接插入排序，此时增量减为1，因为直接插入 排序在元素基本有序的情况下（根据上述第一点，接近最好的情况），效率是很高的。

具体实现大家可参考《排序算法学习之路——希尔排序》

3. 归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一 个有序表，称为二路归并。

归并排序最常用的实现方式是借助递归函数来实现，当然递归函数底层借助的也是栈的机制。所以说实现归并排序的方法也可以使用栈而不使用递归。

具体实大家可参考《排序算法学习之路——归并排序》 和 《排序算法学习之路——归并排序（非递归实现）》

4. 快速排序

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

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
其实现步骤如下

1 、从数列中挑出一个元素，称为 “基准”（这个基准的找出方式有很多，在这里我们就默认使用第一个元素作为基准）
2、 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3、从第二步中得到的基准的中间位置将数组分成两部分，递归地（recursive）把小于基准值元素的子序列和大于基准值元素的子序列排序。
4、重复第二步，直到子序列的数值个数为1

同样的其常用的实现方式是使用递归函数来实现。所以说也可以使用非递归的方式也就是借助栈来实现。

具体实现大家可以参考《排序算法学习之路——快速排序》 和 《排序算法学习之路————快速排序（非递归实现）》

5. 堆排序

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

从上面的定义的最后一句话中我们同样可以得出两个概念——大顶堆、小顶堆。

所谓大顶堆就是子节点的键值或索引总是小于它的父节点。通过大顶堆得出的序列是递增的。

所谓小顶堆就是子节点的键值或索引总是大于它的父节点。通过小顶堆得出的序列是递减的。

下面我们来看一下堆排序的思想

利用小顶堆堆顶记录的是最大关键字这一特性，使得每次从无序中选择最大记录变得简单。

其基本思想为(大顶堆)： 1)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； 2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2...n- 1]<=R[n]; 3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元 素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。 操作过程如下： 1)初始化堆：将R[1..n]构造为堆； 2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。 因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

具体步骤和实现大家可以参考《排序算法学习之路——堆排序》

6. 选择排序

选择排序是一种简单直观的排序算法。其基本思想是在未排序的序列中选择一个最大（或最小）元素放到末尾（注意：这里是未排序序列的末尾，可以认为是有序序列的起始位置）。

其实现步骤如下

1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3）重复第二步，直到所有元素均排序完毕。

详细介绍和代码实现大家可以参考《排序算法学习之路——选择排序》

7. 冒泡排序

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

冒泡排序的步骤

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3）针对所有的元素重复以上的步骤，除了最后一个。
4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

详细介绍和代码实现大家可以参考《排序算法学习之路——冒泡排序》

8. 基数排序——LSD

基数排序（Radix Sort）：是一种非比较型的整数排序算法。

基数排序的基本原理是，按照整数的每个位数分组。在分组过程中，对于不足位的数据用0补位。

上面就是本人在学习排序算法中学习的算法，当然这些并不完整。后续会持续更新算法，希望大家持续关注。

基数排序按照对位数分组的顺序的不同，可以分为LSD基数排序和MSD基数排序。

LSD基数排序，是按照从低位到高位的顺序进行分组排序。例如：1,2,3,4,5,6,7,8,9,10第一次分组后为 10,1,2,3,4,5,6,7,8,9。

首先我们看LSD基数排序是如何进行的

对于序列中的每个整数的每一位都可以看成是一个桶，而该位上的数字就可以认为是这个桶的键值。这句话应该怎么理解呢，我们来看这样的一个序列

170, 45, 75, 90, 802, 2, 24, 66

这是一个整数序列，我们知道，对于每个整数的每一位上的值肯定是介于0和9之间的。因此，要想对这个序列进行LSD排序，那就必须有10个桶。这10个桶的索引分别就是0——9这十个数。对于LSD基数排序来说，每一次分组过程就是将相应的整数放进相应的桶中。

拿第一次分组来说吧，对于每个整数要按照个位上的数进行分组。那么我们看170，其个位为0，所以说170应该放进0这个桶中。然后以此类推 45放在5这个桶中。

所以上述序列的第一次分组后，各个整数所在的桶如下

0: 170, 090
1: 空
2: 802, 002
3: 空
4: 024
5: 045, 075
6: 066
7–9: 空

然后再将这些数依次收集起来，第一次分组再组合以后的序列为

170, 90, 802, 2, 24, 45, 75, 66

接着就是针对十位上的数进行分组入桶，入桶的情况如下

0: 802, 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 170, 075
8: 空
9: 090

再次整理起来以后为下面的序列

802, 2, 24, 45, 66, 170, 75, 90

最后再次进行第三次（百位上的数）分组入桶

0: 002, 024, 045, 066, 075, 090
1: 170
2–7: 空
8: 802
9: 空

整理起来以后，我们发现整个序列已经是有序的了

2, 24, 45, 66, 75, 90, 170, 802

详细介绍和代码实现大家可以参考《排序算法学习之路——基数排序（LSD）》

9. 基数排序——MSD

MSD基数排序是从最高位开始对序列进行分组，到最低位为止。但是其实现过程是和LSD基数排序不同的，排序过程中需要用到递归函数。

待排序序列

170, 45, 75, 90, 2, 24, 802, 66

我们看到，这里面的最大的数是3位数。所以说我们开始从百位对这些数进行分组

0: 045, 075, 090,002, 024, 066
1: 170
2-7: 空
8: 802
9: 空

从这里开始就和LSD基数排序有差别了。在LSD基数排序中，每次分好组以后开始对桶中的数据进行收集。然后根据下一位，对收集后的序列进行分组。而对于MSD，在这里不会对桶中的数据进行收集。我们要做的是检测每个桶中的数据。当桶中的元素个数多于1个的时候，要对这个桶递归进行下一位的分组。

在这个例子中，我们要对0桶中的所有元素根据十位上的数字进行分组

0: 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 075
8: 空
9: 090

按照上面所说，我们应该再递归的对每个桶中的元素根据个位上的数进行分组。但是我们发现，现在在每个桶中的元素的个数都是小于等于1的。因此，到这一步我们就开始回退了。也就是说我们开始收集桶中的数据。收集完成以后，回退到上一层。此时按照百位进行分组的桶变成了如下的形式

0: 002, 024, 045,066, 075, 090
1: 170
2-7: 空
8: 802
9: 空

然后我们在对这个桶中的数据进行收集。收集起来以后序列如下

2, 24, 45, 66, 75, 90, 170, 802

整个MSD基数排序就是按照上面的过程进行的。

详细介绍和代码实现大家可以参考《排序算法学习之路——基数排序（MSD）》

上面就是本人在学习排序算法中学习的算法，当然这些并不完整。后续会持续更新算法，希望大家持续关注。