时间戳

首页 > 解决方案 > 为什么在快速排序中对左侧分区进行排序时包含枢轴元素？

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

问题描述

我正在从著名的《Cracking the Coding Interview 》一书中给出的实现中学习 Quicksort 。我知道分区函数选择中间元素作为枢轴并返回右分区刚刚开始的索引（包括），因此 quickSort 函数接下来将在右分区上递归执行快速排序，即quickSort(arr, index, right)。到目前为止还不错。

问题是左分区现在也包含已经排序的枢轴元素（恰好在索引 - 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);
    }

}

标签： javaalgorithmsortingquicksort

解决方案

该partition函数不一定返回枢轴的索引。实际的枢轴值可能在它的左边或右边。这真的取决于何时遇到和交换它。这可能发生在一段时间之前left并right相互交叉。

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

如果要partition返回枢轴值的索引，则应在循环开始之前将枢轴值交换到当前分区的一侧，并在循环结束后将其交换回原位-然后您就知道了它的索引。在这种情况下，您可以在递归调用中排除它。由于枢轴值因此被排除在循环之外（除非它是重复的），因此应在每次更改leftand时检查循环条件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);
    }
}

从递归调用中排除 at 值的目标好处是index额外交换枢轴值的成本和对循环条件的更多评估。

推荐阅读