2019独角兽企业重金招聘Python工程师标准>>> 
排序
比较常见的排序算法有：快速排序，选择排序，冒泡排序，计数排序，希尔排序，堆排序，桶排序，外部排序，基数排序。
本博就各个算法的实现特点和适用的特点进行描述
计数排序：
给定一个数组A,数组A中数据的大小有上限和下限。添加两个辅助数组B,C,先将C数组初始化为0，然后遍历A数组，C[ A[ i ] ]++。这样就 可以统计A数组中每个元素值得个数，然后将他们放入C[ A[ i ] ]中，接着为了排序的方便，我们进行如下处理 C[ i ] = C[ i ] + C[ i - 1 ]。这样我们可以通过C [ A[ i ] ]的值查A[ i ] 排第几。具体算法实现如下
Count_sort( A, B, C)
for i = 0 to k
C[i] = 0
for i = 0 to n
C[ A[ i ] ]++
for i = 1 to k
C[ i ] = C[ i - 1 ] + C[ i ]
for i = 0 to n
B[ C[ A[ i ] ] ] = A[ i ]
算法的时间复杂度为O( n )，空间复杂度为O( k + n )。我觉得这个算法的核心是再申请了2个数组，一个长度为k,另一个长度为n.然后统计每个元素的数目，接着对元素进行排序。这个算法的事件复杂度非常低，非常适合于数组元素在某一范围内排序。
计数排序的一个例子http://poj.org/problem?id=1007
插入排序：
插入排序的思想是前n个数已经有序，第n+1个数字加进来的时候的时候只需要考虑插入到前n个数字之中，我想这大概是插入排序的名字的来源吧。
上代码：
void insert_sort(int *a, int n)
{
int i, j, temp;
for (i = 1; i < n; i++)
{
temp = a[i];
for (j = i - 1; j >=0 && temp < a[j]; j--)
a[j + 1] = a[j];
a[j + 1] = temp;
}
} 代码还算比比较清爽吧，数组的第一个元素自然有序，就一个嘛，然后依次插入后边的元素，一次插入一个，每次插入的时候比较和temp的大小，如果比temp大，那么for循环推出，把a[i]放在数组的j + 1位置，插入排序对链表尤其有用。