java - 使用枢轴元素对数组进行分区的算法

Question

我试图解决一些 java 编程书籍中的以下编程练习

Write method that partitions the array using the first element, called a pivot. After the partition, the elements in the list are rearranged so that all the elements before the pivot are less than or equal to the pivot and the elements after the pivot are greater than the pivot. The method returns the index where the pivot is located in the new list. For example, suppose the list is {5, 2, 9, 3, 6, 8}. After the partition, the list becomes {3, 2, 5, 9, 6, 8}. Implement the method in a way that takes at most array.length comparisons.

我已经实现了解决方案，但它需要的不仅仅是array.length 比较。

这本书本身有解决方案，但不幸的是它完全错误(不适用于某些输入)。我已经看到了 this 的答案类似的问题，并了解 Quicksort 算法的“征服”部分，但在此算法中，值使用中间值进行分区，但在我的例子中，需要使用第一个数组值作为基准。

Answer 1

这是链接答案中的枢轴例程(改编自 source here )。

    int split(int a[], int lo, int hi) {
        // pivot element x starting at lo; better strategies exist
        int x=a[lo]; 

        //  partition
        int i=lo, j=hi;
        while (i<=j) {
            while (a[i]<x) i++;
            while (a[j]>x) j--;
            if (i<=j) swap(a[i++], a[j--]);
        }

        // return new position of pivot
        return i;
    }

本算法中元素间比较的次数为n或n+1；因为在每个主循环迭代中，i 和 j 以 c 个单位靠得更近，其中 c 是在每个内部 while 循环中执行的比较次数。看看那些内部循环 - 当它们返回 true 时，i 和 j 将靠近 1 个单位。如果它们返回 false，那么在主循环结束时，i 和 j 将因为交换而靠近 2 个单位。

此 split() 可读性强且简短，但它也有一个非常糟糕的最坏情况(即，枢轴在两端结束；点击第一个链接查看结果)。如果数组已经向前或向后排序，就会发生这种情况，这实际上非常频繁。这就是其他枢轴位置更好的原因:如果您选择 x=a[lo+hi/2]，最坏情况将不太常见。更好的是 do like Java ，并花一些时间寻找一个好的支点，以避开最坏的情况。如果您点击 Java 链接，您将看到一个更复杂的枢轴例程，它可以避免在有许多重复元素时做额外的工作。