本博文摘自伍迷老师的《大话数据结构》，想学数据结构的，大大的推荐此书...
事实上，目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。因此我们就来从多个角度来剖析一下提到的各种排序的长与短。
我们将7种算法的各种指标进行对比，如表9‐10‐1所示。
表9‐10‐1
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 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) 不稳定
从算法的简单性来看，我们将7种算法分为两类：