主要内容，总结前面的几种算法在各方面的性能。
如何选择合适的排序算法？
总结前面几种主要排序算法的性能差异。一些算法在一些指标上达到最优情况，还有一些算法的复杂度虽然相同，但在实践中的表现却有差异。
最理想的排序算法是 O(n logn) 时间、O(1)空间、稳定、最好还具有适应性。当然目前，还没找到这种算法。
| 最坏时间复杂度 | 平均时间复杂度 | 最好时间复杂度 | 是否稳定 | 是否是原地排序 | 适应性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | 是 | 是 |
| 插入排序 | O(n^2) | O(n^2) | O(n) | 是 | 是 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | 否 | 是 |
| 快速排序 | O(n^2) | O(nlogn) | O(nlogn) | 否 | 是 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | 是 | 否 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | 是 | 否 |
| 桶排序 | O(nlogn) | O(n) | O(n) | 是 | 否 |
| 基数排序 | O(k*n) | O(k*n) | O(k*n) | 是 | 否 |
适用情况比较
1 . 三个线性排序算法的时间复杂度低，但是适用场景特殊，所以通用的排序函数，不选择线性排序算法。
2 . 对小规模数据进行排序，可以选择时间复杂度是 O(n2) 的算法，如，冒泡排序和插入排序；
3 . 对大规模数据进行排序，选择时间复杂度是 O(nlogn) 的算法更加高效。
所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
时间复杂度为O(nlogn)的排序算法，目前有两个，快速排序和归并排序
快速排序
快速排序适合来实现通用的排序函数，但是，快速排序在最坏情况下的时间复杂度是 O(n^2)。
为什么最坏情况下快排的时间复杂度是 O(n^2)呢？
如果要排序的数据原来就是有序的或者接近有序的，而每次分区点都选择最后一个数据，那快排的性能就很不好，这时时间复杂度就为 O(n^2)。所以，这种 O(n^2) 时间复杂度出现的主要原因是因为分区点选择不够合理。
最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。若直接选择第一个或最后一个数据作为分区点，不考虑数据的特点，肯定就会出现最坏情况的时间复杂度。
几种常用的分区算法
1 . 三数取中法
从区间的首、尾、中间，分别取出一个数，然后对比这三个数的大小，取3数中的中间值作为分区点。每间隔某个固定的长度，取数据出来比较，将中间值作为分区点。这种思路肯定比单纯取某一个数据更好，但是，如果要排序的数组比较大，那“三数取中”可能就不够，需要扩大范围，“五数取中”或者“十数取中”。
2 . 随机法
随机法是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的 O(n^2) 的情况，出现的可能性不大。
快速排序用递归实现。递归需要警惕堆栈溢出。为了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，有两种解决办法：第一种是限制递归深度。一旦递归过深，超过了事先设定的阈值，就停止递归。第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。
举例分析排序函数
实际排序程序会采用多种算法的组合，即混成方法。
在一些复杂排序算法里，也需要处理较短序列的排序问题。快排和归并排序就是这方面的典型：
-
快速排序算法中，序列被划分为越来越短的片段。若序列已经很短，例如短于几个元素，快排还需要做几次递归调用（进栈、出栈）。这些赋值操作很耗时，表现在复杂度度描述中忽略了的常量因子。对于很短的序列，采用插入排序，效果很可能优于快速排序。
-
归并排序正好与快排相反，是从短的有序序列归并出越来越长的序列。从很多个各自包含一个元素的序列出发，通过几遍归并得到最终的有序序列，这其中需要做许多函数调用工作。与这几个元素做简单插入排序相比，归并排序消耗时间会更多。
在实际程序里的排序功能，特别是各自程序库里的排序函数，通常不是纯粹第采用一种算法，而是使用两种或两种以上方法的组合。常见的是归并排序和插入排序的组合，以及快速排序和插入排序的组合。
Python的内置排序算法
Python中的内置排序函数 sort 和表list类的对象的sort方法，两者共享同一个排序算法，是一种混成排序算法，叫作 Timsort(蒂姆排序)。
基本情况
蒂姆排序是一种基于归并技术的稳定排序算法，结合使用了归并排序和插入排序技术，最坏时间复杂度是O(nlogn)。它具有适应性，在被排序的数组元素接近排好序的情况下，它的时间复杂度可能远小于O(nlogn)，可能达到线性时间。在最坏情况下，它的需要n/2的工作空间，因此其空间复杂度是O(n)。
| 最坏时间复杂度 | 平均时间复杂度 | 最好时间复杂度 | 是否稳定 | 是否是原地排序 | 适应性 |
|---|---|---|---|---|---|
| 蒂姆排序 | O(nlogn) | O(nlogn) | O(n) | 是 | 否 |
蒂姆排序算法适合许多实际应用中常见的情况，特别是被排序的数据序列分段有序或者基本有序，但仍有些非有序元素的情况。人们通过许多试验，发现蒂姆排序在平均性能上超过快排，是目前实际表现最好的排序算法。虽然理论上，它并没有克服归并排序O(n)空间开销的弱点，但实际开发中经常不需要很大的额外空间，且现在计算机的内存都很大，很多时候追求的都是速度。
基本工作方式
蒂姆排序的优势是克服了归并排序没有适应性的缺陷，且又保持了其稳定性的特征。
1 . 考察待排序序列中非严格单调上升（后一个值大于等于前一个值）或严格单调下降（后一个值小于前一个值）的片段，反转其中的严格下降片段。
2 . 采用插入排序，对连续出现的几个短的上升排序序列，使整个序列变成一系列（非严格）单调上升的记录片段，每个片段都长于某个特定值。
3 . 采用归并产生更长的排序片段，控制这一归并过程，保证片段的长度尽可能均匀。归并中采用一些策略，尽可能地减少临时空间的使用。通过反复归并，最终得到排序序列
总结
1 . 如果序列中的数据基本有序而且序列长度n比较小，直接插入排序能很快完成排序，即具有适应性。这种情况下，冒泡排序也比较快。
2 . 简单排序算法多是稳定的，而大部分时间性能好的排序都不稳定，如快速排序（以及堆排序）等。
稳定性是具体算法实现的性质，采用同一种排序算法，有可能做出稳定的和不稳定的实现。但有些算法的实现可以很自然地做到稳定（如，插入排序，归并排序），另一些则需要附加的时间或空间开销（如，选择排序）
3 . 实际应用中，数据记录通常有一个主关键码，例如各种唯一标识码，如学号、身份证号、用户账户、商品订单号等。这种关键码一般都具有唯一性。如果要做的是按主关键码排序，所用排序方法是否稳定就无关紧要。
但在另一些应用中，经常需要把记录中的其他成分作为排序码使用，例如，按学生的姓名、籍贯、年龄、成绩等排序。在做这种排序时，应该根据问题所需慎重选择排序方法，经常需要用稳定算法。若用了不稳定的排序算法，可能就还需要对具有相同关键码的数据段再次排序。