第五章 排序
插入排序
对需要排序的数组A，首先开辟一个同样大小的数组B；遍历A中元素，对当前元素X，将它插入到它在数组B中应在的位置。最坏情况下复杂度$O(N^{2})$。
希尔排序
首先设置一个增量序列${h_{k}}(h_{k+1}<h_{k})$，每轮要使得数组中间隔为$h_{k}$的元素有序；排序方式为从左向右地为相隔为$h_{k}$的元素在逆序时进行交换。最坏情况下复杂度$O(N^{2})$。
堆排序
首先构造堆，复杂度为O(N)。然后不断删除根节点，注意到堆有len与size两个属性，在删除时只需要将len减1，而数组的长度实际上并没有变小；
于是，在删除一次根节点后，就会空出一个位置，而这个位置上正好可以放上刚删除的根节点，在将堆中所有元素都删除之后(len为0而size不变)，存储堆的数组上就是原堆中元素的降序排列。
如果要得到堆中元素的升序排列，则构造一个最大堆即可！
堆排序的时间复杂度为$O(N\cdot log(N))$
归并排序
分治法的典型应用。最坏情况下复杂度为$O(N\cdot log(N))$；
归并排序算法的基本操作是合并两个已排序的数组：记两个数组为A、B，算法还需一个输出数组C，其中size(C)=size(A)+size(B)；
初始有三个计数器atr、btr、ctr均置为0；每次将A[atr]、B[btr]中较小者复制到数组C中；如A[atr]小于B[btr]，则将A[atr] 复制到数组C，然后atr加1，ctr加1；若A[atr]大于B[btr]，同理；当其中一个数组的元素全部复制到数组C后，只需要将另一个数组剩余元素复制到数组C即可！
介绍了如何合并两个已排序的数组，再介绍归并排序。对一个需要排序的数组，先递归地将数组的左半部分与右半部分归并排序，然后再将这两个排好序的子数组合并；可以看到：递归触底时，待排序的子数组只有一个元素，自然是排好序的，然后反弹，排好序的子数组不断合并，最终得到整个排好序的数组。
空间复杂度：事实上，只需要开辟一个同样大小的数组空间，就能满足递归全程的数组使用；
快速排序
使用快速排序算法quicksort将数组S排序由如下四步组成：
- 若S中的元素不超过两个，则返回；
- 取S中任一元素v，作为枢纽元；
- 将S-{v}分为两个集合$S_{1}=\{x\in S|x\leq v\}$、$S_{2}=\{x\in S|x>v\}$；
- quicksort($S_{1}$)后继v，再后继quicksort($S_{2}$)即可得到排好序的数组S；
枢纽元
枢纽元的选取最安全的做法是每轮随机选取，可这种做法需耗费大量时间。退求其次，使用”三数中值分割法”，即每次选取左端、中间、右端三个元素的中位数作为枢纽元。这可以排除最坏情形。
分割
具体分割$S_{1}$与$S_{2}$的办法为：将枢纽元与数组最后一个元素交换，low指向第一个元素、high指向倒数第一个元素；
low向右移动，直到遇到大于枢纽元的元素、而high向左移动，直到遇到小于枢纽元的元素；然后交换low、high所指元素；然后low、high继续这样向右/向左移动，直到high<low，再将low所指向的元素与最后一个元素交换，即完成分割过程。
桶式排序
若输入的数据由小于M的正整数组成，那么可对其使用桶式排序；使用一个长度为M的数组C，读入X时，将C[X]加1；读完数据后，扫描数组C，将N打印C[N]次即得到排序的输入数据。