sort()排序函数的实现

c语言中sort()排序函数的实现。

实际上它并不仅仅用了快排这一种算法。

如果你去看源码，你就会发现，sort()会优先使用归并排序来排序输入数据，因为归并排序的时间复杂度，最好、最坏、平均都是O(nlogn)，而快排的时间复杂度最坏为O(n2)，虽然归并排序的空间复杂度为O(n)，但对于小数据量的排序，比如1KB、2KB等，归并排序额外需要1KB、2KB的内存空间，这个问题不大。现在计算机的内存都挺大的，我们很多时候追求的是速度。还记得我们前面讲过的用空间换时间的技巧吗？这就是一个典型的应用。

但如果数据量太大，就跟我们前面提到的，排序100MB的数据，这个时候我们再用归并排序就不合适了。所以，要排序的数据量比较大的时候，qsort()会改为用快速排序算法来排序。那sort()是如何选择快速排序算法的分区点的呢？如果去看源码，你就会发现，sort()选择分区点的方法就是“三数取中法”。是不是也并不复杂？

还有我们前面提到的递归太深会导致堆栈溢出的问题，sort()是通过自己实现一个堆上的栈，手动模拟递归来解决的。我们之前在讲递归那一节也讲过，不知道你还有没有印象？实际上，sort()并不仅仅用到了归并排序和快速排序，它还用到了插入排序。在快速排序的过程中，当要排序的区间中，元素的个数小于等于4时，qsort()就退化为插入排序，不再继续用递归来做快速排序，因为我们前面也讲过，在小规模数据面前，O(n^2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。我们现在就来分析下这个说法。

我们在讲复杂度分析的时候讲过，算法的性能可以通过时间复杂度来分析，但是，这种复杂度分析是比较偏理论的，如果我们深究的话，实际上时间复杂度并不等于代码实际的运行时间。

时间复杂度代表的是一个增长趋势，如果画成增长曲线图，你会发现O(n2)比O(nlogn)要陡峭，也就是说增长趋势要更猛一些。但是，我们前面讲过，在大O复杂度表示法中，我们会省略低阶、系数和常数，也就是说，O(nlogn)在没有省略低阶、系数、常数之前可能是O(knlogn + c)，而且k和c有可能还是一个比较大的数。

假设k=1000，c=200，当我们对小规模数据（比如n=100）排序时，n2的值实际上比knlogn+c还要小。

knlogn+c = 1000 * 100 * log100 + 200 远大于10000

n^2 = 100*100 = 10000

所以，对于小规模数据的排序，O(n2)的排序算法并不一定比O(nlogn)排序算法执行的时间长。对于小数据量的排序，我们选择比较简单、不需要递归的插入排序算法。

还记得我们之前讲到的哨兵来简化代码，提高执行效率吗？在sort()插入排序的算法实现中，也利用了这种编程技巧。虽然哨兵可能只是少做一次判断，但是毕竟排序函数是非常常用、非常基础的函数，性能的优化要做到极致。