脚本宝典收集整理的这篇文章主要介绍了排序优化——如何实现一个通用的、高性能的排序函数,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
几乎所有的编程语言都会提供排序函数,比如 C 语言的 qsort(), C++ STL 中的 sort(),这些排序函数是如何实现的呢?
1. 如何选择合适的排序算法?
如果要实现一个通用的高效率的排序函数,我们应该选择那种排序算法呢?
- 各种排序算法的特点如下所示。
- 线性排序算法的@R_594_1304@比较低,适用场景特殊,因此不适合作为通用的排序函数。
- 小规模数据可以选择时间复杂度为 $O(n^2)$ 的算法,大规模数据选择时间复杂度为 $O(nLOGn)$ 的算法则会更加高效。为了兼顾任意规模的数据,一般会首选复杂度为 $O(nlogn)$ 的算法来实现排序函数。
- 归并排序虽然最好情况、最坏情况和平均情况下时间复杂度都可以做到 $O(nlogn)$,但它不是原地排序算法,空间复杂度为 $O(n)$,排序的时候需要的额外空间和源数据一般大,空间消耗过高。
2. 如何优化快速排序?
快速排序最坏情况下时间复杂度退化为 $O(n^2)$ ,我们怎样来避免这种情况的发生呢?
2.1. 分区点优化问题
-
三数取中法。从待排序数据首、尾、中分别取出一个数,然后对比大小,以这三个数的中间值作为分区点。
- 如果排序数据比较多,可能要“五数取中”或者“十数取中”。
-
随机法。每次从要排序的区间随机选择一个元素作为分区点,这种情况下,就可以避免每次分区点都选得非常糟糕。
2.2. 堆栈溢出问题
快速排序是利用递归来实现的,当递归的的深度过深时,就会导致堆栈溢出。
-
限制递归深度。当递归次数超过我们设定的阈值时,就停止递归。
-
在堆上模拟函数调用栈。手动模拟递归压栈出栈过程,解除系统栈大小的限制。
3. C 语言的 qsort() 函数?
- qsort 优先使用归并排序,在数据规模比较小的时候,以空间换时间。
- 当数据规模比较大时,qsort 会改为快速排序,以三数取中法来选取分区点。
- qsort 通过在堆上模拟函数调用栈来解决堆栈溢出问题。
- 当快速排序区间内元素小于等于 4 时,qsort 退化为插入排序。因为在小数据规模下, $O(n^2)$ 时间复杂度算法并不一定比 $O(nlogn)$ 的算法执行时间长。
获取更多精彩,请关注「seniusen」!
以上是脚本宝典为你收集整理的排序优化——如何实现一个通用的、高性能的排序函数全部内容,希望文章能够帮你解决排序优化——如何实现一个通用的、高性能的排序函数所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。