java – 修改后的quicksort是否可以成为O(n)最佳案例？

发布时间：2020-12-15 08:46:19 所属栏目：Java 来源：网络整理

导读：一般认为快速排序的最佳情况是O(nlogn),因为阵列每次分区大约一半.还有人说最坏的情况是n ^ 2阶,假设数组已经排序. 我们不能通过设置一个名为swap的布尔值来修改quicksort吗？例如,如果第一遍的位置没有初始交换,那么我们可以假设数组已经排序,因此不再对数

一般认为快速排序的最佳情况是O(nlogn),因为阵列每次分区大约一半.还有人说最坏的情况是n ^ 2阶,假设数组已经排序.

我们不能通过设置一个名为swap的布尔值来修改quicksort吗？例如,如果第一遍的位置没有初始交换,那么我们可以假设数组已经排序,因此不再对数据进行分区.

我知道修改后的冒泡排序通过检查交换来使用它,允许最好的情况是O(n)而不是O(n ^ 2).这种方法可以应用于快速排序吗？为什么或者为什么不？

你的方法有一个错误……
例如,我们有一个这样的数组：
1243 5 678

我们的Pivot元素是5.第一次传递后没有交换(因为4和3都较小),但数组没有排序.所以你必须开始划分它,这导致n log n.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!