排序优化——如何实现一个通用的、高性能的排序函数
2018-10-23 本文已影响0人
seniusen
几乎所有的编程语言都会提供排序函数，比如 C 语言的 qsort()， C++ STL 中的 sort()，这些排序函数是如何实现的呢？
1. 如何选择合适的排序算法？
如果要实现一个通用的高效率的排序函数，我们应该选择那种排序算法呢？
-
各种排序算法的特点如下所示。
-
线性排序算法的时间复杂度比较低，适用场景特殊，因此不适合作为通用的排序函数。
-
小规模数据可以选择时间复杂度为
的算法，大规模数据选择时间复杂度为
的算法则会更加高效。为了兼顾任意规模的数据，一般会首选复杂度为
-
归并排序虽然最好情况、最坏情况和平均情况下时间复杂度都可以做到
，排序的时候需要的额外空间和源数据一般大，空间消耗过高。
2. 如何优化快速排序？
快速排序最坏情况下时间复杂度退化为
-
实际上，这种
-
理想的分区点应该是，被分区点分开的两个区间，数据的数量差不多。
2.1. 分区点优化问题
-
三数取中法。从待排序数据首、尾、中分别取出一个数，然后对比大小，以这三个数的中间值作为分区点。
-
如果排序数据比较多，可能要“五数取中”或者“十数取中”。
- 随机法。每次从要排序的区间随机选择一个元素作为分区点，这种情况下，就可以避免每次分区点都选得非常糟糕。
2.2. 堆栈溢出问题
快速排序是利用递归来实现的，当递归的的深度过深时，就会导致堆栈溢出。
- 限制递归深度。当递归次数超过我们设定的阈值时，就停止递归。
- 在堆上模拟函数调用栈。手动模拟递归压栈出栈过程，解除系统栈大小的限制。
3. C 语言的 qsort() 函数？
-
qsort 优先使用归并排序，在数据规模比较小的时候，以空间换时间。
-
当数据规模比较大时，qsort 会改为快速排序，以三数取中法来选取分区点。
-
qsort 通过在堆上模拟函数调用栈来解决堆栈溢出问题。
-
当快速排序区间内元素小于等于 4 时，qsort 退化为插入排序。因为在小数据规模下，
获取更多精彩，请关注「seniusen」!
seniusen
