为什么在快速排序中对左分区进行排序时包含枢轴元素？

Question

我正在从名著 Cracking the Coding Interview 中给出的实现中学习 Quicksort。我知道分区函数选择中间元素作为基准，returns index 右分区刚刚开始（包括在内），因此 quickSort 函数接下来将递归执行 Quicksort右分区即 quickSort(arr, index, right)。目前还不错。

问题是左分区现在包含枢轴元素（正好在 index - 1 位置）并且已经排序所以为什么它不做 quickSort(arr, left, index - 2) 而不是 quickSort(arr, left, index - 1) 以跳过主元素。我尝试跳过枢轴，但有些元素没有正确排序，例如使用此数组：[29, 99, 27, 41, 66, 28, 44, 78, 87, 19, 31, 76, 58, 88, 83, 97, 12, 21, 44]

完整代码如下：

public class Quicksort {
    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left + (right - left) / 2]; // Pick a pivot point. Can be an element        
        
        while (left <= right) { // Until we've gone through the whole array
            // Find element on left that should be on right
            while (arr[left] < pivot) { 
                left++;
            }
            
            // Find element on right that should be on left
            while (arr[right] > pivot) {
                right--;
            }
            
            // Swap elements, and move left and right indices
            if (left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }
        return left; 
    }
    
    public static void quickSort(int[] arr, int left, int right) {
        int index = partition(arr, left, right); 
        if (left < index - 1) { // Sort left half
            quickSort(arr, left, index - 1);
        }
        if (index < right) { // Sort right half
            quickSort(arr, index, right);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = AssortedMethods.randomArray(20, 0, 6);
        AssortedMethods.printIntArray(arr); 
        quickSort(arr, 0, arr.length - 1);
        AssortedMethods.printIntArray(arr);
    }

}

Answer 1

partition函数不一定return枢轴的索引。实际的枢轴值可能在它的左边或右边。这实际上取决于遇到和交换的时间。这可能会在 left 和 right 相互交叉之前的某个时间发生。

因此，您不能跳过 index 处的值。

如果要partition到return枢轴值的索引，应在循环开始前将枢轴值交换到当前分区的一侧，并在循环开始后将其交换回原位循环结束——然后你就知道它的索引了。在这种情况下，您可以在递归调用中排除它。由于枢轴值因此被排除在循环之外（除非它是重复的），因此应在 left 和 right:

的每次更改时检查循环条件

public static int partition(int[] arr, int left, int right) {
    int mid = left + (right - left) / 2; 
    int pivot = arr[mid];
    int store = right--;
    swap(arr, mid, store);
    while (left <= right) {
        if (arr[left] < pivot) { 
            left++;
        } else if (arr[right] > pivot) {
            right--;
        } else if (left < right) {
            swap(arr, left, right);
            left++;
            right--;
        } else  {
            return left;
        }
    }
    swap(arr, left, store);
    return left;
}

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int index = partition(arr, left, right); 
        quickSort(arr, left, index - 1);
        quickSort(arr, index + 1, right);
    }
}

从递归调用中排除 index 处的值的目标好处是要付出额外交换枢轴值和更多循环条件评估的代价。

为什么在快速排序中对左分区进行排序时包含枢轴元素？

Why is the pivot element included while sorting the left partition in Quicksort?

java

algorithm

sorting

quicksort