线性排序 O(n) 排序优化
桶排序，计数排序，基数排序的时间复杂度是线性的，之所以能做到线性的时间复杂度主要是因为这些算法是非基于比较的排序算法，都不涉及元素之间的比较操作。
桶排序
核心思想是将要排序的数据分到几个有序的桶中，每个桶里的数据再单独进行排序。桶内排完序后，再将每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。%20%20%E6%8E%92%E5%BA%8F%E4%BC%98%E5%8C%96/987564607b864255f81686829503abae.jpg)
时间复杂度分析：如果要排序的数据有n个，把它们均匀地划分到m个桶内，每个桶里就有k=n / m个元素。每个桶内部使用快速排序，时间复杂度为O(k logk)。m个桶排序的时间复杂度就是O(m k logk),因为k=n / m,所以整个桶排序的时间复杂度就是O(n log(n / m))。当桶的个数m接近数据个数n时，log(n / m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。
桶排序对要排序数据的要求是非常苛刻的：首先要排序的数据需要很容易能划分成m个桶，并且桶与桶之间有着天然的大小顺序。这样每个桶内数据都排序完之后，桶与桶之间的数据不需要进行排序。其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为O(nlogn)的排序算法了。
桶排序比较适合用在外部排序中。
计数排序
计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大时，比如最大值为k，就可以将数据划分为k个桶，每个桶内的数据值都是相同的，省掉了桶内排序的时间。
比如高考成绩排序，考生的满分是750，最小是0，就可以分为751个桶，根据考生成绩，将50万考生划分到751个桶中，桶内的数据都是分数相同的学生，所以并不需要再进行排序，只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了50万考生的排序，因为只涉及扫描遍历操作，所以时间复杂度是O(n)。
计数排序的名字计数有何而来呢？比如8个考生分数在0-5之间。%20%20%E6%8E%92%E5%BA%8F%E4%BC%98%E5%8C%96/adc75672ef33fa54b023a040834fcbc9.jpg)
C[6]内存储的不是考生，而是对应的考生的个数。将C[6]数组顺序求和。%20%20%E6%8E%92%E5%BA%8F%E4%BC%98%E5%8C%96/dd6c62b12b0dc1b3a294af0fa1ce371f.jpg)
C[k]里存储小于等于分数k的考生个数。%20%20%E6%8E%92%E5%BA%8F%E4%BC%98%E5%8C%96/1d730cb17249f8e92ef5cab53ae65784.jpg)
这种利用另外一个数组来计数的实现方式非常巧妙，这也是为什么这种排序算法叫计数排序的原因。
计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要在其不改变相对大小的情况下，转化为非负整数。
基数排序
%20%20%E6%8E%92%E5%BA%8F%E4%BC%98%E5%8C%96/df0cdbb73bd19a2d69a52c54d8b9fc0c.jpg)
对于每一位的排序的算法需要是稳定的。可以使用桶排序或者计数排序，其中桶排序中每个桶不能用快排而要用归并排序。
基数排序对要排序的数据是有要求的，需要可以分割出独立的‘位’来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。
选择合适的排序算法
%20%20%E6%8E%92%E5%BA%8F%E4%BC%98%E5%8C%96/1f6ef7e0a5365d6e9d68f0ccc71755fd.jpg)
其中默认桶排序是不稳定的。
排序优化，实现高性能的排序函数
线性排序算法的时间复杂度较低，但是适用场景比较特殊。所以如果要写一个通用的排序函数,不能选择线性排序算法。
如果对小规模数据进行排序,可以选择时间复杂度是o(n2)的算法;如果对大规模数据进行排序,时间复杂度是 o(nlogn)的算法更加高效。所以,为了兼顾任意规模数据的排序,一般都会首选时间复杂度是o( nlogn)的排序算法来实现排序函数。
然而归并排序使用的并不多，虽然其稳定O(nlogn)，但是由于其不是原地排序算法，空间复杂度是O(n)，所以并没有得到很多的使用。
优化快速排序
最坏的情况下快排的时间复杂度是O(n2),如果数据原来就是有序或者接近有序的，每次分区点都选择最后一个数据，那么快速排序算法就会变得非常糟糕，时间复杂度就会退化为O(n2)，出现的主要原因是我们分区点选的不够合理。理想的分区点是，被分区点分开的两个分区中，数据的数量差不多。为了提高排序算法的性能，要尽可能地让每次分区都比较平均。
三数取中法
我们从区间的首、尾、中间,分别取出一个数,然后对比大小,取这3个数的中间值作为分区点。这样每间隔某个固定的长度,取数据岀来比较,将中间值作为分区点的分区算法,肯定要比单纯取某一个数据更好。但是,如果要排序的数组比较大,那“三数取中”可能就不够了,可能要“五数取中”或者“十数取中”。
随机法
随机法就是每次从要排序的区间中,随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好,但是从概率的角度来看,也不大可能会出现每次分区点都选的很差的情况,所以平均情况下,这样选的分区点是比较好的。时间复杂度退化为最糟糕的O(n2)的情况,出现的可能性不大。
快速排序是用递归来实现的。我们在递归那一节讲过,递归要警惕堆栈溢出。为了避免快速排序里,递归过深而堆栈过小,导致堆栈溢岀,我们有两种解决办法:第一种是限制递归深度。一旦递归过深,超过了我们事先设定的阈值,就停止递归。第二种是通过在堆上模拟实现一个函数调用栈,手动模拟递归压栈、岀栈的过程,这样就没有了系统栈大小的限制。
举例分析排序函数
比如qsort()函数，会优先使用归并排序来处理小数据量的排序。使用空间来换时间，当数据量太大，就会改用快速排序算法来排序。选取分区点的方法便是三数取中法。对于递归太深导致堆栈溢出的问题，是通过自己实现一个堆上的栈，手动模拟递归来解决的。qsort()并不仅仅用到了归并排序和快速排序，还用到了插入排序。在快速排序的过程中，当要排序的区间中，元素的个数小于等于4时，qsort()就退化为插入排序，在小规模数据前，O(n2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。