0、前提
- 只考虑内部排序
- 只讨论基于比较的排序
- 稳定性：任意两个相等的数据，排序后相对位置不发生改变
- 没有一种排序是任意情况下最好的
1、简单排序
冒泡排序 - Bubble Sort
时间复杂度：最好情况（已排好序）为O(n)；最坏情况（所有元素逆序）为O(n^2)
- A[] 当元素类型不是数组而是单向链表时依然很容易实现
- A[i] 和 A[i+1] 相等时不做交换保证了排序该算法是稳定的
插入排序 - Insertion Sort
类似于抓牌。从最后的位置依次向前扫描，如果发现了小于它的牌（或者已经到最前面了）就插在它后面。
时间复杂度：最好情况O(n)；最坏情况O(n^2)
也是稳定的
例：给定初始序列{34,8,64,51,32,21}，冒泡排序和插入排序分别需要多少次元素交换才能完成？
答：冒泡排序和插入排序都需要9次
时间复杂度下界 （简单排序）
对于下标i<j，如果A[i]>A[j]，则称(i,j)是一对逆序对（inversion）
{34,8,64,51,32,21}中包含了9个逆序对；
交换2个相邻的元素正好消去一个逆序对；
因此冒泡排序和插入排序都需要进行9次元素交换
插入排序：T(N,I) O(N+I)，I为逆序对的个数
如果序列时基本有序的，则插入排序简单且高效
要提高效率，必须每次消去不止一个逆序对，应每次交换相隔比较远的元素
2、希尔排序 - Shell Sort
利用插入排序的简单，克服插入排序每次只交换相邻两元素的缺点；
相隔d个元素做插入排序
既是上界也是下界，相当于真实复杂度
3、堆排序
堆排序是选择排序的优化版：
4、归并排序
是稳定的，但需要一个和A大水相同的额外数组
核心：两个有序子列的归并
最好情况与最坏情况相同
分而治之，对左半和右半分别排序，然后对这两个有序子列归并~
在这个统一接口中声明一个临时数组可以避免在递归中重复申请空间：
可以只申请一个长度为N的临时数组，第一层归并时从A归并到临时数组，第二层归并时从临时数组到A…
不同于Merge， 这里的Merge1归并不需要把排序好的数据复制回原来的数组
奇数时的最后一个序列只执行了复制操作
5、快速排序
与归并类似，快速排序也采用了分而治之的思想：
图中65是主元
最好情况：O(NlogN) ，每次选出的主元都是最中间大小的元素
最坏情况：O(N^2)，比如每次都选第0个元素：
已经不是囧了，而是递归的囧。。。
快速排序快的重要原因是确定主元并进行元素划分后主元的位置就不再移动
一种选择主元的方法
根据此时的大小关系，只需要考虑Left和Right中间的元素
子集划分
指针i、j指向Left、Right-1位置。依次移动i、j，向中间靠近，遇到位置不对的元素就停止，两边都停止后交换这两个位置不对的元素；重复这个过程直到i>j
最后交换i和Right-1，把Right-1调回中间
如果有元素正好等于pivot怎么办？
- 停下来做交换 ✓
- 不理它，继续移动指针
极端假设数组中元素都相同
停下来做交换虽然浪费时间，但是可以保证把数组拆分在中间的位置；
继续移动指针可以避免无谓的交换，但最终主元总会被放在端点。
选择停下来做交换可以O(N^2)避免提高复杂度
小规模数据的处理
由于使用递归实现，对于小规模的数据可能还不如插入排序快
在程序中定义一个阈值（Cutoff），当递归的数据规模充分小于这个阈值时，停止递归，直接调用简单排序（如插入排序）；
算法实现（glibc中qsort实现：qsort.c）
6、表排序
适用于对结构复杂的元素进行排序，待排元素移动的时间不能忽略不计；
在表排序中使用间接排序，不直接原始数据，而是移动指向他们的指针；
间接排序
定义一个指针数组作为“表”：
此时排序已经完成，但元素位置没有变化，如果一定要修改原数据的位置，再进行物理排序
物理排序
N个数字的排列由若干个独立的环组成
根据每一个环的方向，依次调换元素的位置
复杂度分析
最好情况：初始有序，不做交换
最坏情况：每个环包含2个元素，则有⌊N/2⌋个环，需要⌊3N/2⌋次元素移动
综上T=O(m*N)，m是每个元素复制需要的时间
7、基数排序
桶排序
时间复杂度O(M+N)
e.g.1
e.g.2
基数排序
基数排序是桶排序的升级版
<-主位 次位 ->
时间复杂度T=O(P*(N+B))，P是Pass次数，B是桶的个数
桶的个数少时，相当于线性复杂度
基数排序也可用于多关键字的排序，如扑克牌
显然，这里次位优先比主位优先更快
8、排序算法的比较
- 简单排序程序简单，都不需要额外空间。
- 冒泡排序和插入排序每次都是交换相邻的元素，速度慢；但不需要交换时可以不交换，因此是稳定的。
- 简单选择排序是跳着进行交换的，因此是不稳定的。
- 希尔排序的好坏很大程序上取决于增量序列的选择，d<=2。
- 堆排序和归并排序的理论时间复杂度是最好的。
- 堆排序的NlogN的常数较大，且不稳定。
- 快速排序的NlogN的常数较小，在实际应用中较快，但总是可以构造出一种情况使其是N^2；递归需要额外空间，且不稳定。
- 归并排序是稳定的，但需要额外的一倍空间。
- 基数排序在某些情况下比NlogN更快，近乎线性，这取决于用多少个桶和多少次的分配和收集；每个桶占用一定的额外空间。