排序算法注意点：
插入类排序：1:直接插入排序O(n^2)
2:折半插入排序O(n^2)
3:希尔排序 O(n乘以log以2为底,n的对数)
空间复杂度都是O(1)
交换类排序：1：冒泡排序O(n^2)，空间复杂度O(1)
2：快速排序O(n乘以log以2为底,n的对数)，空间复杂度O(log以2为底,n的对数)
选择类排序：1：简单选择排序O(n^2),空间O(1)
2：堆排序O(n乘以log以2为底,n的对数)，空间复杂度O(1)
二路归并排序：O(n乘以log以2为底,n的对数)，空间复杂度O(n)
基数排序:时间O(d(n+rd)) d:关键字个数，n:元素数，rd:关键字的取值范围
空间O(rd)
注：对于数值类排序，只能从低位到高位进行基数排序，能有序，（高到低，不行）
1：平均情况下，(快，希，归，堆) ->时间复杂度 O(n乘以log以2为底,n的对数)
其余O(n^2),基数排序O(d(n+rd)) d:关键字个数，n:元素数，rd:关键字的取值范围
2：空间复杂度，快->O(log以2为底,n的对数)
归->O(n)
基数->O(rd)
其他->O(1)
3：时间复杂度，直插与冒泡容易(有序)变成O(n)
4：不稳定排序->(快，希，选，堆)
5：经一趟排序，能保证一个元素到达最终位置:a交换类（冒泡，快速）
b选择类（选，堆）
6：排序，元素比较次数和原始序列无关:a选择排序
b折半插入排序
另外，（归并，堆，基数）时间复杂度与起始无关
7：排序趟数（所有数都被处理一次为一趟）与原始序列有关--->交换类：冒/快
排序算法总结
原文：http://blog.csdn.net/ndzjx/article/details/42460523
