目录
排序的其他相关知识点和源码分享可以参考之前的博客：
《数据结构与算法基础-学习-30-插入排序之直接插入排序、二分插入排序、希尔排序》，
《数据结构与算法基础-学习-31-交换排序之冒泡排序、快速排序》，
《数据结构与算法基础-学习-32-选择排序之简单选择排序、堆排序》，
| 方法名 | 时间复杂度最好情况 | 时间复杂度最坏情况 | 时间复杂度平均情况 | 空间复杂度 | 稳定性 |
| 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 二分插入排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n) | O(n^2) | 猜想O(n^1.3) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(n * log2^n) | O(n^2) | O(n * log2^n) | O(n * log2^n) | 不稳定 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n * log2^n) | O(n * log2^n) | O(n * log2^n) | O(1) | 不稳定 |
| 归并排序 | O(n * log2^n) | O(n * log2^n) | O(n * log2^n) | O(n) | 稳定 |
| 基数排序 | O(n + m) | O(k * (n + m)) | O(k * (n + m)) | O(n + m) | 稳定 |
在此时间复杂度下的排序算法有快速排序、堆排序、归并排序，其中快速排序最优。
在此时间复杂度下的排序算法有直接插入排序、二分插入排序、冒泡排序、简单选择排序，其中二分插入排序最优。
王卓老师讲的分析中没有加入二分插入排序，所以以直接插入排序为最优，而二分插入排序在查找的效率上优于直接插入排序，移动上一样，所以我认为二分插入排序的平均情况下优于直接插入排序。
王卓老师讲的确实好，真心的感谢老师。
在此时间复杂度下的排序算法只有基数排序，独大。
直接插入排序和冒泡排序的时间复杂度可以到达最优情况O(n)。
快速排序的时间复杂度可以到达最差情况O(n^2)。
简单选择排序、堆排序、归并排序的时间复杂度不会因为序列中的关键字分布而改变，也就是说数据是否有序，并不影响这个几个算法的时间效率。