线性排序算法的复杂度低，如桶排序、计数排序、基数排序。但是它们对排序的数据都有比较苛刻的要求，应用不是非常广泛。如果数据特征比较符合这些排序算法的要求，应用这些算法，会非常高效，线性时间复杂度可以达到O（n）。
桶排序和计数排序的排序思想是非常相似的，都是针对范围不大的数据，将数据划分为不同的桶来实现排序。基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较地位。而且每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数排序来完成每一位的排序工作。
线性排序算啊的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。
如果对小规模数据进行排序，可以选择时间复杂度是O（n方）的算法；如果对大规模数据进行排序，时间复杂度是 O（nlogn）的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是O（nlogn）的排序算法来实现排序函数。
Java中使用堆排序实现排序函数，C语言中使用快速排序实现排序函数。但是使用归并排序的却不多，即使归并排序最坏的情况时间复杂度都是O(nlogn)，但是它并不是原地排序算法，它的空间复杂度为O（n）。
优化快速排序
快速排序在最坏情况下，复杂度为O（n方），即数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度会退化为O（n方）。实际上这种O（n方）时间复杂度出现的主要原因还是因为我们分区点选的不够合理。
最理想的分区点是： 被分区点分开的两个分区中，数据的数量差不多。
如果很粗暴地直接选择第一个或者最后一个数据作为分区点，不考虑数据的特点，肯定会出现在某些情况下，排序最坏情况时间复杂度为O（n方）。为了提高排序算法的性能，我们也要尽可能地让每次分区都比较平均。
常见的分区方法：
- 三数取中法
我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这3个数的中间值为分区点。这样每隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。
- 随机法
随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的非常糟糕，所有平均情况下，这样选的分区点是比较好的。
举例分析Glibc 排序函数
Glibc中的 qsort() 从名字上看很像是基于快速排序算法实现的，实际上它并不仅仅使用了快排这一种算法。
qsort() 会优先使用归并排序来排序输入数据，因为归并的时间复杂度比较稳定O（nlogn），所以对于小数据量的排序，比如 1KB、2KB 等，归并排序额外需要 1KB、2KB 的内存空间，这个问题不大。
如果数据量太大，如排序 100MB 数据，qsort() 会改用快速排序算法来排序。qsort() 使用的选择分区点的方法就是“三数取中法”。关于递归太深会导致堆栈溢出问题，qsort() 是通过自己实现一个堆上的栈，手动模拟递归来解决的。
另一方面，qsort() 并不仅仅用到了归并排序和快速排序，它还用到了插入排序。在快速排序的过程中，当要排序的区间中，元素的个数小于等于4时，qsort() 就退化为插入排序，不再继续用递归来做快速排序，因为在小规模数据面前，O(n方) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长，这一点需要考虑除了高阶之外的复杂度系数。
对于小规模数据的排序，O（n方）的排序算法并不一定比O（nlogn）排序算法执行的时间长。对于小数据量的排序，我们选择比较简单，不需要递归的插入排序算法。
在 qsort() 插入排序的算法实现中，使用哨兵来简化代码。虽然哨兵可能只是少做一次判断，但是毕竟排序函数是非常常用，非常基础的函数，性能的优化要做到极致。