几乎所有的编程语言都会提供排序函数，比如C语言中的qsort()，C++ STL中的sort()、stable_sort()，还有Java语言中的Collections.sort()。在平常的开发中我们也都是直接调用这些现成的排序函数来进行使用，但是这些函数是怎么实现的我们并不是很清楚。
这节课就要学习这些排序函数的底层实现利用了哪种排序算法。
1如何选择合适的排序算法
下图中使我们学过的排序算法的一个总结：
我们来分析一波~
对于线性排序算法计数排序、桶排序、基数排序，虽然它们的时间复杂度比较低，但是它们适用场景比较特殊，对数据要求比较高，如果我们要写一个通用的排序函数，肯定是不适合的，所以通用的排序函数一般不会选择用线性排序算法来实现。
时间复杂度为O(n^2)的排序算法适用于小规模数据排序，时间复杂度为O(nlogn)的排序算法适用于大规模数据排序，一般情况下为了兼顾任意数据的排序，都会首选用时间复杂度是O(nlogn)的排序算法来实现排序函数。
因此通用的排序函数一般还是选择时间复杂度为O(nlogn)的排序算法来实现，而时间复杂度为O(nlogn)的排序算法有归并排序、快速排序，还有堆排序（后面会讲）等等。其中堆排序和快速排序应用都比较多，比如Java语言采用堆排序实现排序函数，C语言使用快速排序实现排序函数。
我们发现使用归并排序的情况其实并不多，这是为什么捏？
明明快排在最坏情况下的时间复杂度是O(n^2)，而归并排序可以做到平均情况、最坏情况下的时间复杂度都是O(nlogn)，这不是很棒棒吗？但是它有一个很拖后腿的点：它不是原地排序算法，空间复杂度是O(n)，夸张点讲，如果要排序100MB的数据，除了数据本身之外，排序算法还要额外再占用100MB的内存空间，空间耗费就翻倍了。
OK，分析完之后，我们知道快速排序和堆排序应用比较多，快速排序是我们前面学过的，今天就主要来说说它。刚刚有说到，快速排序在最坏情况下的时间复杂度是O(n^2)，那么我们该如何解决这个“复杂度恶化”的问题呢？
2如何优化快速排序
先来说说为什么最坏情况下快速排序的时间复杂度是O(n^2)。
当要排序的数据原本就是有序的或者接近有序的时候，每次分区点都选择最后一个数据，排序算法就会变得非常糟糕，时间复杂度就会退化为O(n^2)。
搬运一下之前的结论：
实际上，这种O(n^2)时间复杂度出现的主要原因还是我们分区点选的不够合理。
我们知道，理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
那么如何选择一个合适的分区点呢？
下面简单介绍两个方法：
1.三数取中法
我们从区间的首、尾、中间，分别取出一个数，然后对比它们的大小，取这3个数的中间值作为分区点。如果要排序的数组比较大的话，“三数取中”可能就不够用了，我们可以“五数取中”或者“十数取中”。
2.随机法
每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选得很差的情况，平均情况下这种选分区点的方法还是不错的。
快速排序使用递归实现的，而用递归就要警惕堆栈溢出。为了避免快速排序里递归过深而堆栈过小导致堆栈溢出，我们有两种解决办法：1.限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。2.在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程。这样就没有了系统栈大小的限制。
3C语言中的qsort()分析
为了对如何实现衣蛾排序函数有更直观的感受，下面我们拿C语言中的qsort()函数来分析一下。
qsort()会优先使用归并排序来对输入数据进行排序，因为归并排序的空间复杂度是O(n)，所以对于小数据量的排序问题不大，而且现在计算机的内存都挺大的，我们很多时候更多的是追求速度。这就是我们之前提过的，用空间换时间。
但是如果数据量太大，qsort()就会改为用快速排序算法来排序，并且它选择分区点的方法是“三数取中”法。而且qsort()自己实现了一个堆上的栈，手动模拟递归，解决了递归太深会导致堆栈溢出的问题。
实际上，它还用到了插入排序。在快速排序的过程中，当要排序的区间中元素个数小于等于4时，qsort()就会变成使用插入排序，不再继续用递归来做快速排序。因为在小规模数据面前，O(n^2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。
并且，qsort()用到了哨兵来简化代码提高执行效率，虽然哨兵只是少做以此判断，但是毕竟排序函数时非常常用、非常基础的函数，性能的优化要做到极致。
4内容小结
今天我们了解了如何实现一个工业级的通用的、高效的排序函数，我们大部分排序函数都是采用O(nlogn)时间复杂度的排序算法来实现，但是为了尽可能地提高性能会做很多优化。优化策略包括但不限于：合理选择分区点、避免堆栈溢出等等。最后我们还分析了C语言的qsort()函数的底层实现原理。
