[算法] 排序

1. 选择排序

首先，找到数组中最小的那个元素，
其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。
再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。
如此往复，直到将整个数组排序。

特点：
1）运行时间和输入无关。
2）数据移动是最少的。

对于长度为N的数组，选择排序需要大约N^2/2次比较 和 N次交换。

2. 插入排序

通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其它已经有序的牌中的适当位置。在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。

对于随机排序的长度为N且主键不重复的数组，平均情况下插入排序需要_{N^2/4次比较以及}N^{2/4次交换。最坏情况下需要~N}2/2次比较和~N^2/2次交换，最好情况下需要N-1次比较和0次交换。

插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。

3. 希尔排序

希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。

希尔排序更高效的原因是它权衡了子数组的规模和有序性。

4. 归并排序

5. 快速排序