江苏龙网

  1. 主页 > 生活百科 > >

计算机入门必备算法——快速排序法( 二 )

快速排序法

2.3 运行时间
快速排序的运行时间在于你选择的基准值 。假设你一直都选择第一个元素作为基准值，且要处理的数组是有序的 。快速排序不检查数组元素的顺序，因此还是会尝试对其排序，但是这会有一个问题，每次选择第一个作为基准值，导致比基准值小的数组都是空的，使得调用栈非常高 。运行时间较长 。栈长表示为O(n) 。

计算机入门必备算法——快速排序法

文章插图
调用栈（最糟情况）
那有没有更好的办法呢？有的，我们可以参考二分查找的实现方法，每次选择中间的元素作为基准值，就会发现调用栈被减短了许多，不需要太多的递归调用，就会达到基线条件，最佳情况下栈长为O(logn) 。
计算机入门必备算法——快速排序法

文章插图
最佳情况
因此，在最糟糕的情况下（选择第一个为基准值）运行时间为O(n) 。在最佳情况下，运行时间仅为O(nlogn) 。




推荐阅读


上一篇：win11怎么退回win10？

下一篇：为什么电子烟忽然被“封杀”？