快速排序算法优化策略

2021-03-15 06:59:23李驰
电脑知识与技术 2021年1期

李驰

摘要:为了解决经典快速排序算法在面对待排序数据事先有序,大量重复数据,递归层数过深以及排序稳定性等诸多问题时暴露出来的缺陷,从枢轴的合理选择、三路划分、与其他排序法结合和尾递归优化等多个方面分析和总结了优化经典快速排序算法的各种策略,在实际使用快速排序算法时具有一定的参考价值。

关键词: 快速排序;算法优化;枢轴;三路划分;排序稳定性;尾递归优化

中图分类号: TP311        文献标识码:A

文章编号:1009-3044(2021)01-0226-03

Abstract:In order to solve the problems exposed by the classical quick sort algorithm, such as ordered data in advance, a large number of repeated data, too many recursive layers,and sorting stability, etc, this paper analyzes and summarizes various strategies of optimizing classical quick sort algorithm from the aspects of reasonable selection of pivot, three-way division, combination with other sorting algorithm and tail recursive optimization, it has certain reference value in the actual use of quick sort algorithm.

Key words: quick sort; algorithm optimization;pivot; three-way division; sorting stability; tail recursive optimization

排序一直以來都是计算机科学中的一个重要研究问题,尤其是在程序设计的算法领域。许多专家学者都在努力找到综合效率最高的排序算法。衡量排序算法效率的指标包括时间复杂度、空间复杂度和是否稳定等。这些指标中最重要的当然是时间复杂度。虽然归并排序和堆排序的最好和平均时间复杂度也能够达到O(nlogn),但其常数因子较大,所以快速排序实际上是目前发现的最快的排序算法。但是这并不意味着快速排序就没有缺点。事实上,在待排序数据事先有序,或者有大量重复数据,或者排序要求稳定性时经典快速排序算法表现就比较糟糕。所以对于经典的快速排序进行优化就显得很有必要,本文就从各个不同的角度分析和总结了对经典快速排序的优化策略。

1 具体优化策略

1.1优化不必要的交换

经典的快速排序算法需要将作为枢轴的元素在每次扫描停顿时轮流与后面的和前面的元素不断地进行交换。……

登录APP查看全文