有人能给我解释一下这个快速排序算法吗？

Question

我对快速排序有点困惑。 例如，此算法取自programcreek。com使用中间元素作为轴心点：

public class QuickSort {
    public static void main(String[] args) {
        int[] x = { 9, 2, 4, 7, 3, 7, 10 };
        System.out.println(Arrays.toString(x));
 
        int low = 0;
        int high = x.length - 1;
 
        quickSort(x, low, high);
        System.out.println(Arrays.toString(x));
    }
 
    public static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0)
            return;
 
        if (low >= high)
            return;
 
        // pick the pivot
        int middle = low + (high - low) / 2;
        int pivot = arr[middle];
 
        // make left < pivot and right > pivot
        int i = low, j = high;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
 
            while (arr[j] > pivot) {
                j--;
            }
 
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
 
        // recursively sort two sub parts
        if (low < j)
            quickSort(arr, low, j);
 
        if (high > i)
            quickSort(arr, i, high);
    }
}

有人能解释一下底部的2个递归调用，以及为什么需要创建一个i和j变量来复制左右标记

另外，有人能解释一下使用中间元素的快速排序算法与使用第一个或最后一个元素作为轴心点的快速排序算法之间的区别吗？代码看起来有所不同，因为使用最后/第一个元素作为轴心点通常是使用分区方法而不是上面的代码编写的

谢谢

Answer 1

快速排序基于分而治之的方法，首先，我们取一个枢轴元素，将小于该枢轴元素的所有元素放在左侧，将大于该枢轴元素的所有元素放在右侧，然后，对于左侧快速排序（数组，低位，pivot-1），我们在枢轴的两侧递归执行相同的操作，对于右侧快速排序（数组，低位，pivot+1）

这是你第一个问题的答案

现在，选择中间元素或第一个元素作为轴有什么区别 当我们在排序后选择第一个元素作为轴时，当i大于j时，我们将轴元素（第一个元素）与j交换，以便我们选择作为轴的元素位于左侧，所有小于它的元素位于右侧

当我们选择中间元素作为枢轴，它已经在中间，所以不需要交换它。

Answer 2

这是霍尔分区方案的一个变体。“经典”霍尔分区方案在与pivot进行比较之前增加i，减少j。此示例和问题示例都在主函数中包含分区逻辑

void quickSort(int a[], size_t lo, size_t hi)
{
    int pivot = a[lo+(hi-lo)/2];
    int t;
    if(lo >= hi)
        return;
    size_t i = lo-1;
    size_t j = hi+1;
    while(1)
    {
        while (a[++i] < pivot);
        while (a[ j] > pivot);
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    QuickSort(a, lo, j);
    QuickSort(a, j+1, hi);
}

与pivot比较后，问题代码增加i，减少j

分区逻辑分割一个分区，使左侧<；=枢轴，右侧>；=支点pivot和等于pivot的元素可以在任意一侧的任何位置结束，并且在达到大小为1的子数组的基本大小写之前，可能不会在其排序位置结束

使用中间元素作为pivot的原因是，如果数组已经排序或反向排序，则选择第一个或最后一个元素作为pivot将导致最坏情况下的时间复杂度为O（n^2）。如果最后一个元素用于pivot，则此答案中的示例将失败（但问题示例不会）