最近在看《算法导论》，首先在这推荐一下这本书，写的确实很精彩
。
《算法导论》的第二部分分析了多种排序算法。包括插入排序、归并排序、堆排序、快速排序以及线性排序的几个算法。
下面简要总结一下。
对于输入规模为n的数组。插入排序的复杂度为O(n^2)。
归并排序、堆排序、快速排序的复杂度为O(n㏒n);
线性排序的复杂度为O(n)
1.插入排序的性能和输入元素的的序列有很大的关系，如果输入已排序的序列，则复杂度是线性的，若输入是逆序的则是O(n^2)的。
2.堆排序用到了优先队列（优先队列是一种用来维护由一组元素构成的集合S的数据结构）。
3.快速排序的关键是主元的选取(pivot)。在排序过程中元素被分成四部分：小于等于主元的序列、大于主元的序列、未比较的序列、主元。
当未比较的序列未空时，再分别对小于等于主元的序列进行排序、对大于主元的序列进行排序。
以上三种排序都是原地排序。所谓的原地排序(in-place)是指这些元素是在原数组中重排序的，在任何时刻，至多其中的常数个数字是存储在数组之外的。
4.归并排序是将原数组划分成子序列，对子序列进行排序，然后将排序好的子序列合并到一起从而使得原序列重排。
归并排序不是原地排序，它需要额外的内存资源。
以上四种是比较常用的排序，对于输入序列没有特殊的要求，并且都是比较排序，也就是说通过比较各个元素而进行的排序。它们的时间复杂度最好为O(n㏒n);
下面介绍能在时间内完成的排序。
1.计数排序
适用条件：输入序列中的元素取值在一个范围之内0-k
基本思想:对于每一个元素确定比它小的的元素的个数。
排序A序列，将结果放入B中，元素的取值范围为0-k
伪代码如下：
Count-sort(A,B,k)
for i=0 to k
do C[i]=0
for j=1 to length(A)
do C[A[j]] = C[A[j]]+1;计算A[j]的个数。
for i=1 to k
do C[i] = C[i-1]+C[i];计算小于和等于i的元素个数
for j=length(A) downto 1
do B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]]-1;
我们可以明显看到计数排序不是原地排序。同时计数排序是稳定的（即相同的元素输入和输出的相对位置不变。）