插入排序

插入排序包含直接插入排序、折半插入排序和希尔排序。
直接插入排序:

折半插入排序:
折半插入只不过是将直接插入排序中从后向前寻找改为二分查找，减少了比较的次数。但是元素移动的次数并未减少，所以折半插入排序相对直接插入排序只是在常数意义上改善了复杂度。

希尔排序:

交换排序

交换排序包含冒泡排序和快速排序。
冒泡排序:
从前向后两两比较，若为逆序交换元素位置，直到序列结束。第i次冒泡总能将第i大的元素就位，所以最多n-1趟冒泡就能将所有元素排序。

有两种情况可以优化：

void bubble_sort(int *e,int lo, int hi)
{
    while (lo < hi) {
        hi = bubble(e,lo,hi);
    }
}

int bubble(int *e, int lo, int hi)
{
    int last = lo;
    while (++lo < hi) {
        if (e[lo-1] > e[lo]) {
            last = lo;
            swap(e[lo-1] , e[lo]);
        }
    }
    // 返回最后更新位置，下次只需冒泡到这里，并且作为标志证明前缀不是完全有序
    return last;
}

快速排序:

下面示例讲解如何寻找轴点：

选择排序

选择排序包含简单选择排序和堆排序。

堆排序：
堆排序的原理是将所有元素放入堆中，然后依次取最大或最小的元素即可完成排序，不过堆排序的巧妙之处在于，它不需要额外分配空间。

归并排序

合并过程，就是比较两组元素的首元素大小，依次取首元素最小的元素放入相应位置，因为合并后的元素有可能覆盖掉第一组元素，所以要先复制一份，这也是归并排序空间复杂度为的原因。

基数排序(桶排序)

其实就是先按个位排序，然后按十位排序，再按百位排序。基数排序的顺序很重要，一定要先排权重低的，后排权重高的，因为后面的排序会将前面的排序覆盖掉。比如说最后一次排序是按个位排的，那么结果就会按个位排序，最后一次按百位排的，结果就会按百位排序。

内部排序算法比较

1. 若n较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。
2. 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
3. 若n较大，则应采用时间复杂度为的排序方法：快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为， 则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一 起使用。先利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。
4. 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要的时间。
5. 若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。
6. 当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

外部排序

然后将排好序的小段归用归并排序。

对于外部排序，I/O访问速度要远小于内存的访问速度，所以要增加速度，主要需要减少I/O的访问。我们发现每一次归并都需要访问所有的元素，所以减少I/O的最好办法就是减少归并的次数，即增加归并路数。例如上图中2路归并，将所有数据访问了3遍，如果改为8路归并，只需访问所有数据一次。

然而我们不能无限的增加归并路数m，因为：

增加m会使总的比较次数增加。

败者树

败者树是一颗完全二叉树。我认为叫做“亚军树”更为形象，因为二叉树的非叶节点保存了当前分支“第二小的”，所以每次选最小的只需要一路向上和“亚军”比就行了。所以比较次数为树的高度，即，比较次数可以化为：

比较次数与m无关，所以在内存允许的情况下可以无限增加m，以减少I/O访问次数。

置换选择排序

从公式中可知减小初始归并段个数r,也可以减少总比较次数，也就是要增加归并段长度。基于内部排序，归并段最长也就是内存的长度，而置换选择排序可以在排序的同时给出超过内存长度的归并段。

算法思想：
1）从待排序文件FI输入w个记录到工作区WA；
2）从内存工作区WA中选出其中关键字取最小值的记录，记为MINIMAX；3）将MINIMAX记录输出到FO中；
4）若FI未读完，则从FI输入下一个记录到WA中；
5）从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小的关键字记录，作为新的MINIMAX；

最佳归并树

归并段划分好之后，接下来是归并中的“合并”过程。与内部排序的归并排序不同的是，这里的归并段是不等长的，谁先合并谁后合并会有性能差异，相当于下面这道题：

【2012统考真题】设有6个有序表A,B,C,D,E,F,分别含有10,35,40,50,60和200个数据元素，各表中的元素按升序排列。要求通过5次两两合并，将6个表最终合并为1个升序表，并使最坏情况下比较的总次数达到最小。请回答下列问题：
1）给出完整的合并过程，并求出最坏情况下比较的总次数。
2）根据你的合并过程，描述n(n≥2)个不等长升序表的合并策略，并说明理由。

这个合并过程可以由哈夫曼树优化。

例如：初始归并段有12个，长度分别为4，4，4，4，5，5，5，5，5，6，6，7，采用5路归并。

首先，要计算一下需要补充几个虚段。

k叉树有公式，整理得，取余数,可知多出来几个归并段。

要添加的虚段个数 = k-u-1，因为这个新组成的分支要去代替树中的一个节点，而哪个节点原本就有一个归并段，所以要减1。