排序算法
插入排序
直接插入排序
假设数组已经有序，插入一个新的元素，通过挪动其它元素的位置来保持数组有序。一开始，有序数组中只有一个元素，然后把剩余元素依次添加进来。
为了找到插入新元素的位置，需要 \(O(n)\) 次比较，而挪动剩余元素与实现有关。（因为是插入，所以链表比较合适）
折半插入排序
在有序的数组中查找新插入元素的大小可以采用二分查找。每次插入的比较次数与初始序列无关，都需要 \(O(n \log n)\) 次，这与直接插入排序不同。
冒泡排序
通过交换每次将一个数字归位。由于冒泡排序每次交换操作都意味着发现了一个逆序对，如果没有发现逆序对就说明已经有序，就可以结束排序。
简单选择排序
每次找到剩余元素中最小的元素，与第一个无序元素交换。
希尔排序
选取增量，分成多个子序列，分别进行插入排序。本质上是增大插入排序每个元素移动的位置，跳跃式接近最终位置。时间复杂度与选取的增量有关。
快速排序
每次选择一个基准数，将所有比它小的数放在左边，比它大的数放在右边，然后对左右两边递归。
堆排序
大顶堆是满足所有节点的值都大于等于其子节点值的完全二叉树，小根堆同理。先建立堆，然后排序。
- 建立堆的过程：
- 从最后一个非叶子节点（索引为 \(n/2-1\)）开始向上进行堆化操作，即确保以 \(i\) 为根的子树满足堆的性质。如果不满足，交换节点然后递归调整。
- 排序过程：
- 交换根节点和堆的最后一个元素，此时最大值已经归位，堆的大小减 1。
- 对新的堆进行堆化操作
- 重复上述步骤，直到堆的大小为 1。
可以快速找到前 k 大的元素（而无需整体排序）。
二路归并排序
将两个有序表组合成一个新的有序表。用一个辅助数组保存过程合并完成的有序子数组，最后拷回去。
基数排序
根据数字的每一位大小进行排序。不基于比较和移动排序。
外部排序
对于待排序的元素量很大，无法全部放到内存中进行排序的情况，使用外部排序。简单来说，就是分次读取一部分数据进行排序，然后再合并有序的部分，直到所有元素完成排序。由于这个任务天然地需要分块排序，使用归并排序是合适的。
由于外存的读写速度比起内存要慢得多，对于外部排序，首要目标是降低外存的读写次数。
考虑使用二路平衡归并
考虑优化以上方法，有两个思路：
- 增大归并路数：归并路数增大，一次从外存读取的数据段增加，需要读写的总次数就减少。然而，归并路数并不是越多越好。在排序过程中，每次我们需要从 \(k\) 个归并段的头部找到最小值，这需要 \(k-1\) 次比较，因此引入败者树优化这一过程。
- 减少归并段个数：增加初始归并段的长度，从而让初始归并段的数量减少，归并的次数也就减少，需要读写的总次数就减少。为了能够构造出比内存区容量更大的初始归并段，使用置换-选择排序。
败者树
将元素两两比较，更小的元素继续互相之间两两比较，直到找到最小值。记录在这个过程中的“败者”，即不够小的元素，可以形成一棵败者树。这样，每次加入新的元素后再找到最小值只需要 \(\log k\) 次比较。由于“冠军”，也就是最小值已经被我们拿走，放入归并序列中，就空出一个位置。我们将每次新插入的元素与败者们比较，由于其它元素的大小关系已知，只需要 \(\log k\) 次比较就能知道新的“冠军”。
置换-选择排序
朴素算法中，我们在缓冲区中塞满元素，就算构造了一个初始归并段。实际上，我们可以不断置换出缓存区中最小的元素（到初始归并段的末尾），然后继续加入其它元素。当缓存区中的元素均大于归并段末尾元素时，我们就需要新建一个初始归并段，重复以上过程。
使用了类似思想的 例题
最佳归并树
由于置换-选择排序得到的初始归并段长度可能不同，不同的归并策略可能导致归并次数不同，意味着 I/O 次数不同，因此引入最佳归并树。「最佳」两字已经暗示了使用哈夫曼树。
首先，I/O 的次数与归并树的关系是什么？事实上，I/O 次数 = 带权路径长度 * 2。这里，每个节点的权值是初始归并段所占的块数，即需要 I/O 的操作次数。随着归并树深度增加，上面进行的 I/O 操作又要重复计算，这与带权路径长度定义一致。
哈夫曼树的带权路径长度最小，我们只需要正常构建 k 叉哈夫曼树即可。但当初始归并段，也就是节点数量不满足构成一棵严格的 k 叉归并树时，我们需要添加权值为 0 的虚段，再进行构建。如果不添加虚段，某些节点可能会被提前归并，产生的节点就会被重复计算，最后结果就不是最优了。
虚段可以看作是长度为 0 的归并段。
那么，需要补充多少虚段呢？假设一棵 k 叉最佳归并树中，度为 \(k\) 的节点个数为 \(n_k\)，度为 0 的节点个数为 \(n_0\)（即叶子节点，初始归并段），总节点个数为 \(n\)：
- \(n=n_0+n_k\)（总节点数 = 叶子节点数+度为 k 的节点数）
- \(kn_k=n-1\)（总度数 = 总节点数 - 1。由于除了根节点，每个节点都会与父节点有一条边）
消去 n 得到：\(n_k=(n_0-1)/(k-1)\)，\(n_k\) 须为正整数，即：\((n_0-1) \mod (k-1) = m\)。记结论，叶子节点数 -1 对归并路数 -1 取模。
- 如果 \(m=0\)，无需添加虚段
- 如果 \(m\neq 0\)，需添加 \(k-m-1\) 个虚段。