例如,当数组是数组中的最高或最低值时.
对于使用2个指针快速排序,1变为左端到右侧,另一个进入右端向左,当在相对于所述枢轴查找元素出来的地方的指针停止,当两个已停止,它们交换元件,并继续在那个位置上.但是,为什么以及如何使用Quicksort O(n ^ 2)进行错误的枢轴选择？
一个糟糕的枢轴选择如何使Quicksort O(n ^ 2)？
假设你总是选择最小的元素作为你的支点.quicksort的顶级迭代将需要n-1进行比较,并将数组拆分为两个子数组:一个是size 1,另一个是size n-1.第一个已经排序,并且您将quicksort递归地应用于第二个.拆分第二个将需要n-2比较.等等.
总的来说,你有(n-1) + (n-2) + ... + 1 = n * (n-1) / 2 = O(n^2)比较.