①插入排序类：
（1）直接插入排序 （2）折半插入排序 （3）2-路插入排序（4）表插入排序（5）希尔排序
（稳定的排序）O(n2) （不稳定的排序）
②交换排序类：
（1）划分算法+快速排序 （2）冒泡排序
（不稳定的排序）O(nlogn)最坏情况：已经排好序 （稳定的排序）最坏情况下，比较次数为n(n-1)/2
③选择排序类：
（1）简单选择排序 （2）树形选择排序 （3）堆排序
（不稳定的排序）O(n2) （不稳定的排序）O(nlogn)
简单选择排序比较次数：O(n*n) 移动次数：O(n)
④归并排序类：
（1）合并两个已排序表+自底向上归并排序 （2）自顶向上合并排序
（稳定的排序）O(nlogn)
⑤基数排序
（1）多关键字排序（2）链式基数排序
（稳定的排序）O（d（n+rd））也可以写成O（d·n）
适用于n值很大而关键字较小的序列。若关健字大，而序列中“最高位关键字”均不同，可以先“最高关键字”变成小序列后直接插入排序。
元素移动次数和关键字初始排序无关。
⑥其他排序
枚举排序（计数排序）
排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n2)O(n)O(n2)O(1)稳定简单选择排序O(n2)O(n2)O(n2)O(1)不一定？直接插入排序O(n2)O(n)O(n2)O(1)稳定希尔排序O(nlogn)~O(n2)O(n1.3)O(n2)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n2)O(logn)~O(n)不稳定基数排序O(d*(n+rd))O(d*(n+rd))O(d*(n+rd))O(rd)稳定 计数排序，牺牲空间换时间。辅助空间为可能输入的最大的数O(MAX)， 平均情况，最好情况，最坏情况，都是O(MAX)，应该也是算在稳定里面 从算法的简单性来看：
简单算法：冒泡、简单选择、直接插入、基数
改进算法：希尔、堆、归并、快速
从平均情况来看：
堆归并，归并，快速都为O(nlogn) 胜过 希尔排序O(nlogn)~O(n2) 胜过 冒泡，简单选择，直接插入
O(nlogn) ：（1）快速排序 （2）堆排序 （3）归并排序 ， 平均下速度：堆 > 快速 > 归并 O(nlogn)~O(n2)：（1）希尔排序 ， 因dlta增量序列变化复杂度变化： O(n2) ：（1）直接插入排序 （2）冒泡排序 （3）简单选择排序 O(d*(n+rd)) ：（1）基数排序最好情况来看：
冒泡，直接插入O(n) 更优。即如果待排序序列总是基本有序，那么反而不应该考虑4种复杂的改进算法
最快情况来看：
堆排序、归并排序O(nlogn) 胜过 快速排序，及其他O(n2)
时间复杂度：
归并排序 和 堆排序 发挥稳定； 快速排序 时好时坏 ；冒泡排序 和 直接插入排序 在简单的，基本有序下表现好
稳定性：（一对数字不进行两次和两次以上比较）
稳定的排序：（1）冒泡排序（2）直接插入排序（3）归并排序（4）基数排序
不稳定的排序：（1）希尔排序（2）快速排序（3）堆排序
不一定：简单选择排序 具体介绍（介绍传送门）
从待排序记录个数上： 待排序个数 n 越小，简单排序更适合。 n 越大，改进的排序方法更适合。下表给出了当n的值在500到5000之间时，5种排序算法的平均比较次数的实验结果
选择排序 插入排序 自底向上归并 自顶向下归并 快速排序
nSelectionSortInsertionSortBottomUpSortMergeSortQuickSort500124 75062 7473852385262911000499 500261 2608682870415 69315001 124 250566 62714 08513 98428 17220001 999 0001 000 48819 39319 42634 02025003 123 7501 564 52225 95125 11152 51330004 498 5002 251 11231 24130 93055 39735006 123 2503 088 97137 10236 76267 13140007 998 0004 042 84242 88242 85979 432450010 122 7505 103 51351 61549 07198 635500012 497 5006 180 35856 88855 280106 178 综合来看，快速排序是性能最好的排序，，但不同场合我们要考虑不同的算法来应对。
