algorithm - 快速排序整数数组练习

Question

所以我有这个数组{3,1,4,1,5,9,2,6,5,3,5}

我正在使用三中值法来获取枢轴。

所以在这种情况下，这里的中位数介于左、中、右之间:3、9、5。所以是 5

我做的第一件事是确保枢轴位于最左侧。现在，我将小于 5 的数字保留在左侧，并将大于 5 的数字移到数组的最右侧。最终结果是:{3,1,4,1,2,3|5|5,9,6,5}

现在对左右子数组进行快速排序。

{3,1,4,1,2,3} 的中位数为 3，重新排列后我得到 {1,1,2,3,4}

{5,9,6,5} 的中位数为 5，我得到 {5,5,9,6} 作为排序相等和更大数字的结果向右。但是这个子数组不像第一个子数组那样排序。它只有在 median 为 6 时才有效。那么它哪里出错了？谢谢。

Answer 1

您必须再次对 {|5|5,9,6}(或 {5|5|,9,6})的右子数组进行排序。中位数为 6，结果将为 {5,6,9}(或 {6,9})。

另请注意，具有许多重复键的朴素快速排序会降低到二次时间复杂度。有一些方法可以检测等于主元的键并将它们从递归排序的子数组中排除。