20、排序算法
1、直接插入排序（这里以从小到大排序为例）
◆要注意的是，前提条件是前i-1个元素是有序的，第i个元素依次从第i-1个元素往前比较，直到找到一个比第i个元素值小的元素，而后插入，插入位置及其后的元素依次向后移动。
◆当给出一队无序的元素时，首先，应该将第1个元素看做是一个有序的队列
而后从第2个元素起，按插入排序规则，依次与前面的元素进行比较，直到找到一个小于他的值，才插入。示例如下图所示:
下图中，59依次向前比较，先和68比较，再和57比较，发现57比他小，才插入。
**第一轮：**从第二位置的 6 开始比较，比前面 7 小，交换位置。
**第二轮：**第三位置的 9 比前一位置的 7 大，无需交换位置。
**第三轮：**第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。
**第四轮：**第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。
…
就这样依次比较到最后一个元素。
2、希尔排序（适合于数据比较多的、大数据）
◆希尔排序又称“缩小增量“排序是对直接插入排序方法的改进。
◆希尔排序的基本思想是:
先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
◆具体做法是:先取一个小于n的整数d1 作为第一个增量，把文件的全部记录分成d1个组，将所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序;然后取第二个增量d2(d2<d1)，重复上述分组和排序工作，依此类推，直至所取的增量di=1(di<di-1<…<d2<d1)，即所有记录放在同一组进行直接插入排序为止。
◆按上述，希尔排序实际是为了解决大数据的排序问题，当待排序的数据很多时，使用直接插入排序效率很低，因此，采取分组的方法，使问题细化，可以提高效率，适用于多数据。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 48 | 37 | 64 | 96 | 75 | 12 | 26 | 48_ | 54 | 03 |
如上有10个数字，编号 1-10，当增量序列为 5、3、1时，也就是编号1的数字（48）和 编号 6的数字（12）（因为增量为5,1 + 5 = 6）为同一个组。（1,6,11…，因为编号总共为10，所以是2个数字为一组）
同理编号2的数字 37 和 编号7的数字 26 为一组。
编号3的数字 64 和 编号 8的数字 48_ 为一组。
编号4的数字 96 和 编号9的数字 54 为一组。
编号 5的数字 75 和 编号 10的数字 03 为一组。
所以分成了 5 组。然后分别对每组进行插入排序。
所以第一组 48 和 12 就调换了个位置，即此时 12 编号为 1,48编号为6.
同理，48_ 的编号变为了 3,64的编号变为了8
54的编号变为了4,96的编号变为了9
03的编号变为了5，75的编号变味了10，于是得到，第一趟排序结果：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 12 | 26 | 48_ | 54 | 03 | 48 | 37 | 64 | 96 | 75 |
然后按照 增量序列 5、3、1 的 3 进行分组：
即：编号1的12和编号4的54、编号7的37、编号10的75为一组（1、4、7、10）
编号2的26和编号5的03、编号8的64为一组（2、5、8）
（3、6、9）编号的为一组
然后每组进行插入排序，排序后位置调换，得到第二组排序结果：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 12 | 03 | 48_ | 37 | 26 | 48 | 54 | 64 | 96 | 75 |
然后按照增量序列为 5、3、1 的 1 进行分组：
即 编号（1,2,3,4,5,6,7,8,9,10） 所有数字为一组。进行插入排序，从而得到最终结果。
不管前面的增量是多少，最后一轮的排序的增量一定为1.
3、简单选择排序
◆n个记录进行简单选择排序的基本方法是:通过n-i(1≤i≤n)次关键字之间的比
较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n 时所有记录有序排列。
◆按上述，本质就是每次选择出最小的元素进行交换，**主要是选择比较过程（n-i次比较），而交换过程只有一次。**示例如下
比如上述4个数字里先找出最小的 52，然后这个最小值与4个数字里的第1个数字的位置进行交换。
然后，在剩下的数字 68，59, 57三个数字中找到最小的 57，然后与这三个数字中的第1个数字 68 交换位置。
然后再比较剩余的 59,68找出最小的，判断是否交换位置。
最后就得到了最后的排序结果。
4、堆排序
左侧称之为小根堆（比如一个完全二叉树，孩子（左右）结点都大于根节点），右侧称之为大根堆（比如一个完全二叉树，孩子结（左右）点都小于根节点）。大根堆用于排成从大到小；小跟堆用于排成从小到大。
由上图可知，首先将给出的数组按完全二叉树规则建立，而后，找到此完全
二叉树的最后一个非叶子节点(也即最后一颗子树)，比较此非叶子节点和其
两个孩子结点的大小，若小，则与其孩子结点中最大的结点进行交换;依据此
规则再去找倒数第二个非叶子节点，这是只有一层的情况，当涉及到多层次时因此，又要进行变换。
第一步，按照序列(55,60,40,10,80,65,15,5,75)按照层次遍历建立一个完全二叉树。（即从上到下、从左到右。）
第二步，此时还不是大根堆，只是建立了一个完全二叉树。所以需要调整满足：左右子结点大于根节点。
**此时需要先找出最后一个非叶子结点。**首先，这里的非叶子节点有55、60、40、10，最后一个非叶子结点就是10。
然后比较左右子节点大小，比非叶子节点大，就调换位置，于是10下去，75上去了。
第三步，找倒数第二个非叶子节点，这里找到 40，比较，然后65上去；
第四步，找倒数第三个非叶子节点，这里找到60，比较，然后80上去。
第五步，找倒数第四个非叶子结点，这里找到55，比较，然后80上去。
此时还没有结束，因为55下去之后，75和60都比55大，此时还需要继续调整、变换，比如 55 下去，75换上去。然后对比是否符合。
然后整体查看树是否满足，不满足的再局部进行调整。
所以整体上来说，堆排序是先进行从小到上的比较、变换；然后再从上到下进行局部调整（防止从小到上比较、变换时，把小的数字换下来，导致左右子结点都比根节点大）。（这里以大根堆为例的）
这里还以大根堆举例：
◆建立初始堆后，开始排序，每次取走堆顶元素(必然是最大的)，而后将堆
中最后一个元素移入堆顶，而后按照初始建堆中的方法与其孩子结点比较大小，依次向下判断交换成为一个新的堆，再取走堆顶元素，重复此过程。
◆堆排序适用于在多个元素中找出前几名的方案设计，因为堆排序是选择排序，而且选择出前几名的效率很高。
下图为大根堆的示意图：就是不断的调整堆，使其最终满足大根堆。
5、冒泡排序
◆n个记录进行冒泡排序的方法是:
首先将**第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，**然后比较第二个记录和第三个记录的关键字依此类推，直至第n-1个记录和第n个记录的关键字比较过为止。上述过程称为一趟冒泡排序，其结果是关键字最大的记录被交换到第n个记录的位置上。
然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n-1个记录的位置上。最多进行n-1趟所有记录有序排列。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。
◆示例给的是从后往前排序，也是可以的，需要从最后两个元素开始进行比较，将较小的元素交换到前面去，依次进行比较交换。比较是为了交换，交换次数很多。区分冒泡排序和简单选择排序。
冒泡：像水里的泡泡一样，一直网上冒。
比如上图按照 从小到大排序，得到结果：（这里从后往前排序为例）
第一步：先比较59、52，然后 52 和 59 交换。
第二步：比较 68、52，然后交换 68 和 52。
第三步：比较 57、52，然后交换 57 和 52。
然后类推…
相较于简单选择排序而言，冒泡排序有以下不同：
1、简单选择排序是多次比较，1次交换（比较出最小的和第一个进行交换）
2、冒泡排序是一次比较、一次交换，多次比较，多次交换（相邻两个数字比较、交换）
6、快速排序（分而治之，分治法）
◆快速排序是将n个记录分成两块，再递归，实际分成两块的方法如图所示:设定一个基准为57，设定两个指针high=1，low=n，从low指向的第n个元素开始，与基准值进行比较，若小于基准值，则与基准进行交换low–，此时，转而从high指向的第1个元素开始和基准值进行比较，若大于基准值，则和基准值进行交换，此时，又转而从low一指向的值和基准进行比较，重复上述过程。
◆要注意的是:每次都是和基准值进行比较，因此最终是以基准值为中间，将队列分成两块。只有当和基准值发生了交换，才变换high和low指针的计数，否则会一直low–下去。
◆上图中，最终以57为界，左边都是小于57的元素，右边都是大于57的元素，完成一次快速排序，接着对两块再分别进行递归即可。
比如上述数字，
第一次以57为基准，最后得到左侧都小于57，右侧都大于57.这是第一趟快速排序。
第一次比较时，是先比较最后一个元素（从第n个元素开始），此时19小于57，则 low指针执行 low–，然后 19和57交换位置，而 high 指针指向（除原来57的第一个元素，也就是现在除去19的第一个元素68），然后开始比较 68 和 57,68大于57，然后交换 68和57的位置，此时又会比较 low–指向的位置（第n-1）,即比较 24 和 57，小于 57，则 low-- 继续，然后交换 57和24的位置，转而又会从前面的 high 指针指向的 59，继续比较…如此重复…（只要发生了交换，就转换指针low和high，即转换方向，进行比较，没有交换就继续当前指针，不转换方向）
所以这里的基准值最好是接近于中位数。一般以待排序的第一个元素为基准值。
然后对左边的数据和右侧的数据进行快速排序，比如左侧以19为基准，右侧以96为基准。
然后不断递归，直到满足从小到大的序列。
7、归并排序
◆所谓“归并”，**是将两个或两个以上的有序文件合并成为一个新的有序文件。**归并排序的一种实现方法是把一个有n个记录的无序文件看成是由n 个长度为1的有序子文件组成的文件，然后进行两两归并，得到[n/2]个长度为2或1的有序文件，再两两归并，如此重复，直至最后形成包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
◆要仔细理解上述过程，一般归并排序都是用来合并多个线性表的，对单列数据，二路归并排序可以对元素进行两两合并，示例如下:
◆对第三次归并，将52与28比较，28小，放入新表头，52再与33比较，33放入新表，52再与72比较，52放入新表，57再与72比较，57放入新表…
1、第一次时，两路归并 则，两个为一组，比如[57、68]一组，[59、52]一组，然后每组内部比较大小，进行排序，于是得到结果：
[57,68],[52,59],[28,72],[33,96] 每组内都按照从小到大排序了。
2、然后会将第一次的结果，还按两路归并，即[57,68],[52,59]为一组，
则为[57,68,52,59]，
[28,72],[33,96]为一组，
则为[28,72,33,96]
3、然后对于上面进行组内排序，于是得到[52,57,59,68]、[28,33,72,96]
4、然后将上面两组按 两路归并 合为一组，然后组内排序，得到最终结果。
8、基数排序（了解即可）
基数排序是基于多个关键字来进行多轮排序的，本质也是将问题细分，如图例子，分别按个位、十位、百位的大小作为关键字进行了排序，最终得出结果：
9、内部排序算法总结
(1)若待排序的记录数目n较小，可采用直接插入排序和简单选择排序。由于
直接插入排序所需的记录移动操作较简单选择排序多，因此当记录本身信息量较大时，用简单选择排序方法较好。
(2)若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序。
(3)当n 很大且关键字的位数较少时，采用链式基数排序较好。
(4)若n较大，则应采用时间复杂度为0(nlogn)的排序方法，例如快速排序、堆排序或归并排序。
如果两个相等的元素A和B在排序前A在B的前面，但在排序后B在A的前面，那么这种排序算法就是不稳定的。
1、直接插入：
从前开始，后前比较，相邻对调，小的排前，前方无序（从小到大排序）
先从第二位开始，后一位的数字与前一位的数字比较、交换，一直到这个数字不需要交换为止。然后再继续下一位数字的比较、交换。
前方无序：当前在前的相对小的数字，只是跟后方相邻的数字相对较小，不一定比更后面还没排序的数字小。
n个数可能为n次比较、交换，所以 时间 n2，相邻所以空间为1。
数字相等不交换即可，所以稳定。
2、简单选择：
从后开始，最小前置，位置对调，小的最前，前方有序，比较剩余（从小到大排序）
先从最后一位开始，找出最小的数字，将最小的数字与第1位的数字交换位置；然后在剩余的 n-1 个数字里，再从最后一位开始，找出最小的数字，将最小的数字与剩余的 n-1 个数字里的第1位，也就是当前所有数字的第2位交换位置…依次类推。
前方有序：最小的、第2小的、第3小的…都已经在第1位、第2位、第3位…有序排列了，只需要逐渐在后面无序的数字里找到最小的再排到前面有序的后面即可。
n个数可能为n次比较，1次交换，所以 时间 n2，相邻所以空间为1。
数字相等，与最前交换可能有问题（两个数字哪个与第一个交换成了问题），所以不稳定。
3、冒泡排序：
从后开始，后前比较，相邻对调，小的排前，比较剩余（从小到大排序）
n个数可能为n次比较、交换，所以 时间 n2，相邻所以空间为1。
数字相等，可以不交换，所以稳定。
4、希尔排序：
增量分组，组内直接插入排序，位置编号对调，最后增量为1，最后全量直接插入排序（从小到大排序）
时间复杂度 n1.3，组内直接插入，所以空间为1
数字相等，跨组交换，组较多，序列可能变化，不稳定。
5、快速排序：
一个基准值，交换则变向（low、high），一分为二。左右继续，直至完全有序。
折半查找，就是 logn，n 个数字就是 nlogn 空间；每次一个基准值，所以空间是 nlogn。
左右分组，相等数字可能变化，不稳定。
6、堆排序：
以序建堆（完全二叉树），非叶子节点与其左右孩子比较、交换，整体一遍，再局部微调。
二叉树二分，所以时间是nlogn，父子节点交换空间为1.
二分，则相等数字序列可能变化，所以不稳定。
7、归并排序：
N 个数据，每2（3、4、5等）个为一组，组内排序；排好序的组，再每2（3、4、5等）个组合并为一个大组，再组内排序…直至合并为完整的一个组，再最后一次组内排序。
二分，所以时间是nlogn，两表合并一个新表，需要n空间
二分，则相等数字序列可能变化，所以不稳定。
8、基数排序：
基于关键字排序。稳定。
直接插入：
第一次比较： 1 与 1 比较，不交换
第二次比较：第2个1 与 2 比较，不交换
第三次比较：2 与 4 比较，不交换
第四次比较：4 与 7 比较，不交换
第五次比较：7 与 5 比较，交换
第六次比较：4 与 5 比较，不交换，结束。
一共 6 次比较。
归并：需要看是几路合并，两路合并，就是两两为一个数组。
两路归并：
第一遍：
第一次：1 与 1 比较，不交换
第二次：2 与 4 比较，不交换
第三次：7 与 5 比较，交换
第二遍：
[1,1,2,4] 一组，[5,7]一组。
第一个1与2 比较 不交换。
第二个1与2比较 不交换
第三遍：
[1,1,2,4,5,7] 一组。
第一个1与5比较，不交换
第二个1与5比较，不交换
2与5比较，不交换
4与5比较，不交换
一共 3+2+4 = 9 次比较。
堆：
先建立完全二叉树：
先最后一个非子节点进行比较：
左侧的1 与 4 、7 比较，这里比较 2 次（1与4比较，4与7比较，得到最大的7），7 对调。得到：
此时比较了2次。
然后比较 2 的非叶子节点，比较 2 和 5，交换，得到：
这里比较了1次。
然后比较1的非叶子节点，即1和7、5比较（1与7比较，7与5比较，得到最大的），交换7到顶部。得到：
这里比较了2次。
整体调了一遍，还需要进行局部比较、调整：
比较非叶子节点的1和其左右节点，即1和4、1比较（1和4，4与叶子节点1比较，得出最大的4），然后交换4。得到：
这里比较了2次。
此时4换上去了，则还需要比较其与其父节点的关系，即比较 7 和 4、5（7和4比较、7和5比较，得到最大的4），不需要交换。至此结束。得到：
这里比较了2次。
因此一共比较了 9 次。
快速排序：
先以第1个数字基准进行排序：即以1为基准：
先1与最后的5比较，不交换。
再1与倒数第二的7比较，不交换。
再1与倒数第三的4比较，不交换。
再1与倒数第四的2比较，不交换。
再1与倒数第五的1比较，不交换。
这里比较了5次。
然后再以剩余的五个数字[1,2,4,7,5] 中的第1个数字为基准，即以1为基准：
同理：1与5比较，不交换；1与7比较，不交换；1与4比较，不交换；1与2比较，不交换；
这里比较了4次。
然后再以剩余的4个数字[2,4,7,5]中的第1个数字为基准，即以2为基准：
同理：2 与5比较，不交换；2与7比较，不交换；2与4比较，不交换；
这里比较了3次。
然后再以剩余的3个数字[4,7,5]中的第1个数字为基准，即以4为基准：
同理：4与5比较，不交换；4与7比较，不交换。
这里比较了2次。
然后再以剩余的2个数字[7,5]中的第1个数字7为基准：
同理：7与5比较，交换。结束。
这里比较了1次。
所以总共比较了：5 + 4 + 3 + 2 + 1 = 15次。
所以答案为 A，B。直接插入排序，比较6次。
