时空复杂度：
冒泡排序：时间O(n^2)，额外空间O(1)
插入排序：时间O(n^2)，额外空间O(1)
选择排序：时间O(n^2)，额外空间O(1)
基数排序：时间O(k*n)(k=logN_max)，额外空间O(n)(临时存储)+O(B)(记数，B为基的大小)
记数排序：时间O(n+k)，额外空间O(k)
希尔排序：时间O(n*logn^2)，额外空间O(1)
快速排序：时间O(n*log(n))，额外空间O(logn)(递归栈)
归并排序：时间O(n*log(n))，额外空间O(n)(临时数组)+O(logn)(递归栈)
堆排序： 时间O(n*log(n))
使快速排序退化的例子：
n, n-1, n-2, n-3.......3,2,1，快速排序具有O(n^2)的复杂度。
优化方法：随机选择划分元素，而不是固定选择最左面的元素。
对归并来说，一个很不理想的例子：
1,2,3，…… , n
对有序序列还是需要O(nlogn)的时间复杂度。
优化方法：找到序列的连续自增段，把这样的自增段进行合并。
稳定排序和不稳定排序
稳定的排序算法：冒泡排序、插入排序、基数排序、记数排序、归并排序
非稳定排序算法：希尔排序、选择排序、快速排序、堆排序
实际上稳定排序可以实现成非稳定的，看具体的实现过程。有些同学误以为自己写了一个冒泡排序就是稳定的，注意比较的时候是">=" 还是">"。
内部排序与外部排序
http://zh.wikipedia.org/zh/%E5%A4%96%E6%8E%92%E5%BA%8F
内部排序：内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
外部排序：外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。最常用的外部排序是多路归并排序。对于外部排序，影响速度的最主要因素为访问磁盘的次数，所以设计外部排序算法时，尽可能减少访问磁盘的次数。
对于外部排序多路归并算法的时间复杂度进行简要分析。
设有n个数，分成k段，之后利用m路归并 。
t1 = n*log(n/k) 每段分别排序 n*log(n/k)。
t2 = n*logk 每趟对n个数合并（每个数每趟只操作一次），一共logk趟，
t3 = n * (T_read + T_write) * logk 从文件中读取和写入数字花费的时间，
设每读取一个数的耗时为T_read,每次写一个数耗时为T_write，
T(n) = t1 + t2+t3 = n*log(n/k) + n*logk + n*(T_read+T_write)*logk ，其中logk是以m为底的。
所以，为了减少访问磁盘的次数，必须增大基m，但是m并不是越大越好，如果越大，则在m个数中选择最大值会越慢，所以一般都选m=9。
逆序数问题
对于序列 x1,x2,x3.......xn
若存在i>j,且满足x[i] < x[j]，则称(x[i],x[j])构成一个逆序对, 一个序列所有的逆序对的数目叫做这个序列的逆序数。
例如序列 ：5 4 3 2 1
逆序数为 1+2+3+4 = 10
利用归并排序可以快速的求得一个序列的逆序数。
寻找第K大数算法
问题1：给出一个序列，求这个序列第K大的数(离线)
比较通用的算法：
(1) 利用快速排序的划分。每次可以省去一部分的数进行查找。
设下一次的查找百分比为q<1，
时间 T(n) = n + T(n*q）
= n + n*q + T(n*q^2)
= n + n*q + n*q^2 + T(n*q^3)
......
= n(1 + q + q^2 + q^3 + ......)
= n(1*(1-q^k)/(1-q))
当q=1/2时， T(n) = 2n = O(n)。
这种方法最坏情况下的时间复杂度是O(n^2)。
那么有没有能够保证最坏时间复杂度是O(n)的算法吗？有
(2) 最坏时间下是O(n)复杂度的算法
http://en.wikipedia.org/wiki/Selection_algorithm 或参见<<算法导论>> P190-P191
针对普通的划分和随机化划分的缺点，对选择划分数进行改进：选择中位数的中位数进行划分。
假设函数Find(A, k, n)返回的是A数组中第k大的元素，新的查找算法如下：
1：将输入数组的n个元素划分为n/5组，每组5个元素，至多有一个组的元素数目小于5。
2：寻找n/5个组的每个组的中位数。对每个组的5个元素利用插入排序，之后选择中位数。
3: 对第2步找到的n/5个中位数递归调用Find函数，找出其中位数x。
4：利用中位数x对输入数组进行划分。并得出x的排位。
5：如果第四步得到的x的排位为k，则返回x。如果x的排位大于k，则在低区进行递归查找，否则在高区进行查找。
因为x是中位数，除去x本身所在的组和那个元素数目小于5的组不算，大于x的元素数目至少为3*(1/2)*(n/5 - 2) = 3*n/10 - 6。
同理小于x的元素数目至少为3*n/10 - 6。那么第4步最多有n-(3*n/10-6) = 7*n/10+6个元素参加下次的递归查找。
设Find(A, k, n)花费时间为T(n)。
则T(n) = t1 + t2 + t3 + t4 + t5。
t1 = O(n) （分成n/5组）
t2 = O(n) （每组进行选择可以看做O(1)时间花费）
t3 = T(n/5) （对n/5个中位数递归选择）
t4 = O(n) （根据x进行划分）
t5 = T(7*n/10 + 6) （下一次递归选择）
T(n) = T(n/5) + T(7*n/10 + 6) + O(n)
最后可推算出T(n)=O(n)，但是个人认为常数比较大。
K非常小时情况下的选择第K大元素算法:
利用冒泡或者选择排序，时间复杂度O(K*n)。