Java快速排序如何将中间元素与pivot交换

Question

我正在尝试使用Java实现快速排序算法。我创建了我的配分函数，如下所示：

int [] quickPartition(int[] array, int low, int high){

    int  pivot = array[low], end_mark = high, start_mark = 1, temp;

    while (start_mark != end_mark) {
        if (array[start_mark] > pivot) {
            while (end_mark != start_mark) {
                if (array[end_mark] < pivot) {
                    temp = array[end_mark];
                    array[end_mark] = array[start_mark];
                    array[start_mark] = temp;

                    break;
                }
                end_mark--;
            }
        }
        start_mark++;
    }

    return array;
}

array[low]是我的轴，end\u标记是数组的最后一个元素，start\u标记是轴后的第一个元素

第一个同时循环从开始循环到结束，寻找比支点大的下一个数字。当找到时，第二个循环从数组的末端开始，朝着开始寻找小于枢轴的下一个数字。如果满足这两个条件，就会发生交换。但是，如果这两个循环索引（starindex和endindex）相遇，则会退出而循环。

样本数组：[54,26,93,17,77,90,31,44,55,20]
返回：[54,26,20,17,44,31,90,77,55,93]

如您所见，相关元素已经分区。然而，最后一步涉及交换枢轴（54）和（31），以便所有大于54的元素都在右边，小于54的元素都在左边。如何交换31和54，但在这一点上（start_index==end_index），同时循环已经停止？请注意，如果您交换的同时循环之外的值31将丢失。

Answer 1

我很感激你想从错误中学习，所以我不会给你答案，而是给你每次迭代的步骤。请注意，合并排序要求在每次迭代后至少有一个元素位于其正确的排序位置。

步骤1：如果您按升序排序，并且您的轴是第一个元素，那么您的第一个指针（例如，i）需要找到小于轴的元素（所有等于或大于轴的元素都应该位于轴的右侧）

STEP2：当你发现第一个元素小于支点（由i指向），你需要从i 1迭代到高（调用迭代器指针j），并用每个小于i的元素交换数组[i]。

STEP3：用i交换支点。

在step3（一次迭代）的末尾，之前由i指向的元素（现在由枢轴指向）处于正确的排序位置。在这种情况下，枢轴将位于索引0处，其中包含数组的最少元素。

重复这些步骤，即再次调用快速分区函数，但现在为low=1

您的代码的问题是您从未交换过枢轴。此外，您永远不会试图找到比轴大的最小元素，这就是步骤2所做的。只需找到一个大于轴的元素

Answer 2

在外部while循环结束时，array[start_mark]将是第一个数字

此外，如果轴是数组中的最小值，则此代码将生成ArrayOutOfBoundsException：end_标记将减小，直到end_标记==start_标记==1。然后start_标记将变为2，并且外部while循环条件将不满足。将外部while循环的条件设置为start_标记

int  pivot = array[low], end_mark = high, start_mark = 1, temp;
while (start_mark < end_mark) {
    if (array[start_mark] > pivot) {
        while (end_mark != start_mark) {
            if (array[end_mark] < pivot) {
                temp = array[end_mark];
                array[end_mark] = array[start_mark];
                array[start_mark] = temp;

                break;
            }
            end_mark--;
        }
    }
    start_mark++;
}
temp = array[start_mark-1];
array[start_mark-1] = pivot;
array[low] = temp;
return array;