排序算法
#常见排序算法总结 排序代码，从小伙伴Mr-Jason-Sam搬运。
-
当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
-
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n^2）；
-
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
-
排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；反之则不稳定的。
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较。
①稳定的排序算法：冒泡排序、直接插入排序、二分插入排序、归并排序、基数排序。
②不是稳定的排序算法：快速排序、希尔排序、堆排序、直接选择排序。
| 排序方法 | 平均复杂度 | 最坏复杂度 | 最好复杂度 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n²) | O(1) | 稳定 |
| 直接插入排序 | O(n²) | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(nlog2(n)) | O(nlog2(n)) | O(nlog2(n)) | O(n) | 稳定 |
| 二分排序 | O(n²) | O(n²) | O(n) | O(n) | 稳定 |
| 直接选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 快速排序 | O(nlog2(n)) | O(n²) | O(nlog_2(n)) | O(1) | 不稳定 |
| 希尔排序 | O(nlog2(n))~O(n²) | O(n^1.3) | O(n²) | O(log2(n))~O(n) | 不稳定 |
| 堆排序 | O(nlog2(n)) | O(nlog2(n)) | O(nlog2(n)) | O(1) | 不稳定 |
- 选择排序算法准则：
每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。一般而言，需要考虑的因素有以下四点：
①待排序的记录数目n的大小；
②记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
③关键字的结构及其分布情况；
④对排序稳定性的要求。
- 设待排序元素的个数为n.
①当n较大，则应采用时间复杂度为O(n*logn)的排序方法：快速排序、堆排序或归并排序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序：如果内存空间有要求但没有稳定性要求；
归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
②当n较大，内存空间允许，且要求稳定性：归并排序
③当n较小，可采用直接插入或直接选择排序。
直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序：当元素分布有序，如果不要求稳定性，选择直接选择排序。
④一般不使用或不直接使用传统的冒泡排序。
