排序算法常考点
一、各个排序算法的最好最坏情况场景（排序结果从小到大），期望的排序结果是{1，2，3，4，5}
| 排序方法 | 最好情况 | 最坏情况 |
| 冒泡排序 | O(n) 完全有序，例如{1，2，3，4，5} | O(n^2) 完全反序，例如{5，4，3，2，1} |
| 简单选择排序 | O(n^2) 正序有序，交换0次，但是每次都要找到最小元素，因而只是减少了交换次数 | O(n^2) |
| 直接插入排序 | O(n) 完全有序，例如{1，2，3，4，5} | O(n^2) 完全反序，例如{5，4，3，2，1} |
| 希尔排序 | O(nlogn)~O(n^2) 和步长有关 | O(n^1.3) |
| 堆排序 | O(nlogn) | O(nlogn) |
| 归并排序 | O(nlogn) | O(nlogn) |
| 快速排序 |
O(nlogn) 均匀分布，每次都将序列分为两个部分 例如{2，1，4，5，3} | O(n^2) 序列基本有序，例如{1，2，3，4，5}，{5，4，3，2，1} |
二、对空间复杂度的考察
归并排序空间复杂度为O(n)，快排为O(logn)，其余都是O(1)
三、对稳定性的考察
稳定排序：冒泡排序、插入排序、归并排序、选择排序（链表实现为稳定，数组实现为不稳定）
不稳定排序：希尔排序、快速排序、堆排序
注：在《算法》第四版217页上作者说，有很多办法可以将任意排序算法变成稳定的，但是，往往需要额外的时间或者空间。