八大排序算法

八大排序算法

直接插入排序

动画演示

原理

在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。

但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

希尔排序

简介

希尔排序是按其设计者希尔的名字命名的，该算法由希尔1959年公布。他对普通插入排序的时间复杂度进行分析，得出了以下结论：

1

普通插入排序的时间复杂度最坏情况下为O(N2)，此时待排序列为逆序，或者说接近逆序

2

普通插入排序的时间复杂度最好情况下为O(N)，此时待排序列为升序，或者说接近升序

若是能先将待排序列进行一次预排序，使待排序列接近有序（接近我们想要的顺序），然后再对该序列进行一次直接插入排序。因为此时直接插入排序的时间复杂度为O(N)，那么只要控制预排序阶段的时间复杂度不超过O(N2)，那么整体的时间复杂度就比直接插入排序的时间复杂度低了。

基本思想

先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…

当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成

问题

为什么要让gap由大到小？

答案

：gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数

选择排序

每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

如果我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍

堆排序

要学习堆排序，首先要学习堆的向下调整算法，因为要用堆排序，你首先得建堆，而建堆需要执行多次堆的向下调整算法。

堆的向下调整算法（使用前提）

若想将其调整为小堆，那么根结点的左右子树必须都为小堆

若想将其调整为大堆，那么根结点的左右子树必须都为大堆

向下调整算法的基本思想

从根结点处开始，选出左右孩子中值较大的孩子

让大的孩子与其父亲进行比较

若大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。

图示

如何排序

将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但是调整时被交换到最后的那个最大的数不参与向下调整。

完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下去，直到堆中只有一个数据时便结束。此时该序列就是一个升序。

冒泡排序

一个个将气泡冒出。冒泡排序一趟冒出一个最大（或最小）值。

快速排序

任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止

递归实现

Hoare版本

步骤

选出一个key，一般是最左边或是最右边的

定义一个L和一个R，L从左向右走，R从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要R先走；若选择最右边的数据作为key，则需要L先走）

3

在走的过程中，若R遇到小于key的数，则停下，L开始走，直到L遇到一个大于key的数时，将L和R的内容交换，R再次开始走，如此进行下去，直到L和R最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）

经过一次单趟排序，最终使得key左边的数据全部都小于key，key右边的数据全部都大于key。然后我们在将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，因为这种序列可以认为是有序的。

挖坑法

选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。

还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）

在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时L再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）

经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key。然后也是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

前后指针法

起始时，prev指针指向序列开头，cur指针指向prev+1

若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur指针越界，此时将key和prev指针指向的内容交换即可

经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作

非递归实现

1. 当我们需要将一个用递归实现的算法改为非递归时，一般需要借用一个数据结构，那就是栈。将Hoare版本、挖坑法以及后指针法的快速排序改为非递归版本，其实主体思想一致，只是调用的单趟排序的算法不同而已。2. 于是我们可以先将Hoare版本、挖坑法和前后指针法的单趟排序单独封装起来。然后写一个非递归的快速排序，在函数内部调用单趟排序的函数即可。

快速排序的两个优化

三数取中

可是谁能保证你每次选取的key都是正中间的那个数呢？当待排序列本就是一个有序的序列时，我们若是依然每次都选取最左边或是最右边的数作为key，那么快速排序的效率将达到最低

可以看到，这种情况下，快速排序的时间复杂度退化为O(N2)。其实，对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则则效率越高。

为了避免这种极端情况的发生，于是出现了三数取中：三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

小区间优化

我们可以看到，就算是上面理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以2倍的形式快速增长

为了减少递归树的最后几层递归，我们可以设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，而且待排序列的长度越长，该效果越明显

归并排序

将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序。

归并排序，从其思想上看就很适合使用递归来实现，并且用递归实现也比较简单。其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列，合并完毕后再将数据拷贝回原数组。

归并排序的非递归算法并不需要借助栈来完成，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序：

外排序

内排序

数据量相对少一些，可以放到内存中进行排序

数据量较大，内存中放不下，数据只能放到磁盘文件中，需要排序

计数排序

又叫非比较排序

该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。

举例

总结

绝对映射

count数组中下标为i的位置记录的是arr数组中数字i出现的次数

相对映射

count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数