第一章 排序

排序是应用广泛的数据处理方法，本章详细地介绍了插入排序、交换排序、选择排序和归并排序。最后从时间空间以及稳定性能上面对排序方法进行了总结。
其中，插入排序分为直接插入排序，折半插入排序和希尔排序。
其中，交换排序分为冒泡排序和快速排序。
其中，选择排序分为简单选择排序和堆排序。
其中，归并排序

一. 插入排序

1. 直接插入排序

例：[59, 12, 77, 64, 72, 69, 46, 89, 31, 65, 9]
解：第一轮：12 对比 59，需要交换。交换完成的矩阵为[12, 59, 77, 64…
第二轮：77 对比 12，不动；77 对比 59，不动。矩阵不变。
第三轮：64 对比 12，不动；64 对比 59，不动；64 对比 77，需要交换。交换完成的矩阵为[12, 59, 64, 77, 72, 69, 46, 89, 31, 65, 9]。
依此类推。

2. 折半插入排序

例：[59, 12, 77, 64, 72, 69, 46, 89, 31, 65, 9]
解：第一轮：12对比59，需要交换。交换完成的矩阵为[12, 59, 77, 64…
第二轮：与上一轮数组相比，77与59，77大，故77在59右边，矩阵不变。
第三轮：与上一轮数组相比，64与59，64大，故64在59右边，与77相比…
第四轮：与上一轮数组相比，72与64相比，大，右，与77相比，小，故

第n轮：设区域首元素为low，尾元素为high。
将待插入区域的首元素设置为a[low],末元素设置为a[high]，则比较时将待插入元素与a[m],其中m=(low+high)/2相比较。
do{
if(新元素<a[m])
选择a[low]到a[m-1]为新的插入区域(即high=m-1)
else
选择a[m+1]到a[high]为新的插入区域（即low=m+1)
}while(low>high)
3、将此位置之后所有元素后移一位，并将新元素插入a[high+1]。

这里假定排序为[12,46,31,59,64,69,72,77,89,65,9]，以65为例，
下标为9，mid=(0+9)/2=4.5≈4，故将65与64比较，在右，故
65必定在5-9下标内，mid=(5+9)/2=7，故将65与77比较，在左，故
65必定在5-6下标内，mid=(5+6)/2=5，故将65与69比较，在左，故
65会在下标为5的位置。

3. 希尔排序

例：[59, 12, 77, 64, 72, 69, 46, 89, 31, 65, 9]
解：第一轮：以步长为 5 开始分组，分组情况如下：
|59,12,77,64,72|
|69, 46, 89, 31, 65|
|9|。
分组结果如下：
|9,12,77,64,72|
|59, 46, 89, 31, 65|
|69|。
第二轮：以步长为 3 开始分组，分组情况如下：
|9, 12, 77|
|64, 72, 69|
|46, 89, 31|
|65, 9|。
分组结果如下：
|9, 12, 77|
|46, 72, 69|
|64, 89, 31|
|65, 9|。
第三轮：以步长为 1 开始分组，此时是简单插入排序。

二. 交换排序

1. 冒泡排序

例：[59, 12, 77, 64, 72, 69, 46, 89, 31, 65, 9]
解：第一轮：
[59, 12, 77, 64, 72, 69, 46, 89, 31, 65, 9]
[12, 59, 77, 64, 72, 69, 46, 89, 31, 65, 9]
[12, 59, 77, 64, 72, 69, 46, 89, 31, 65, 9]
[12, 59, 64, 77, 72, 69, 46, 89, 31, 65, 9]
[12, 59, 64, 72, 77, 69, 46, 89, 31, 65, 9]
[12, 59, 64, 72, 69, 77, 46, 89, 31, 65, 9]
[12, 59, 64, 72, 69, 46, 77, 89, 31, 65, 9]
[12, 59, 64, 72, 69, 46, 77, 89, 31, 65, 9]
[12, 59, 64, 72, 69, 46, 77, 31, 89, 65, 9]
[12, 59, 64, 72, 69, 46, 77, 31, 65, 89, 9]
[12, 59, 64, 72, 69, 46, 77, 31, 65, 9, 81]
第二轮：
[12, 59, 64, 72, 69, 46, 77, 31, 65, 9, 81]

2. 快速排序

例：[59, 12, 77, 64, 72, 69, 46, 89, 31, 65, 9]
解：选定基准值 key=arr[0]=59 为分界点。初始状态：start=0, end=10, key=59。
第一轮：从右向左找到 a[end] 小于 key 的值：end=10, a[end]=9；从左向右找到 a[start] 大于 key 的值：start=2, a[start]=77。将他俩进行交换。交换完成的矩阵为：[59, 12, 9, 64, 72, 69, 46, 89, 31, 65, 77]
第二轮：从右向左找到 a[end] 小于 key 的值：end=8, a[end]=31；从左向右找到 a[start] 大于 key 的值：start=3, a[start]=64。将他俩进行交换。交换完成的矩阵为：[59, 12, 9, 31, 72, 69, 46, 89, 64, 65, 77]
第三轮：从右向左找到 a[end] 小于 key 的值：end=6, a[end]=46；从左向右找到 a[start] 大于 key 的值：start=4, a[start]=72。将他俩进行交换。交换完成的矩阵为：[59, 12, 9, 31, 46, 69, 72, 89, 64, 65, 77]
第四轮：从右向左找到 a[end] 小于 key 的值：end=4, a[end]=46；此时 end=start=4，故本轮循环结束，key 与 end进行交换。交换完成的矩阵为：[46, 12, 9, 31, 59, 69, 72, 89, 64, 65, 77]
以 59 为分界点，左边的序列为 [46, 12, 9, 31]；右边的序列为 [69, 72, 89, 64, 65, 77]；

三. 选择排序

1. 简单选择排序

基本思想如下：
1）找到最小的数，与第一个数进行交换。
2）除去该数，找到最小的数，与第二个数进行交换。
3）以此类推，会进行n-1轮。

例：[5,2,1,8,3,4,6,7]
解：第一轮：找到最小数1，与第一个数交换
第二轮：找到除1的最小数2，与第二个数进行交换/原位，不用交换
第三轮：找到除1，2的最小数3，与第三个数进行交换…

2. 堆排序

堆排序是一种完全二叉树，分为大根堆和小根堆。
小根堆中最小元素出现在堆顶，根节点的值小于或等于其孩子结点；
大根堆中最大元素出现在堆顶，根节点的值大于或等于孩子结点；
如：序列[2,5,8,16,30,16,20,45,60]为小根堆，[90,50,80,16,30,60,70,10,2]是大根堆。

四. 归并排序

例：[9,4,6,2,1,7]
第一轮：分裂，[9,4,6] 和 [2,1,7]。
第二轮：分裂，[9,4] 和 [6]，[2,1] 和 [7]。
第三轮：分裂，[9]，[4] 和 [6] 与 [2] 和 [1]，[7]。
第四轮：合并，[4,9] 和 [6]，[1,2] 和 [7]。
第五轮：合并，[4,6,9] 和 [1,2,7]。
第六步：合并，[1,2,4,6,7,9]。

核心思想：分治。
对半分，对半分，对半分，分到不可再分为止。
逐层归并。如[9,4,6,]分为[9,4]和[6]；[9,4,6,8] 可以分为[9,4]和[6,8]。

五. 排序总结