algorithm - 修改此快速排序以始终使用最后一个元素作为基准

Question

我有以下 Quicksort总是选择子序列的第一个元素作为它的主元:

void qqsort(int array[], int start, int end) {
    int i = start; // index of left-to-right scan
    int k = end; // index of right-to-left scan

    if (end - start >= 1) { // check that there are at least two elements to sort 
        int pivot = array[start]; // set the pivot as the first element in the partition
        while (k > i) { // while the scan indices from left and right have not met, 
            while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first element greater than the pivot
                i++;
            while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first element not greater than the pivot
                k--;
            if (k > i) // if the left seekindex is still smaller than the right index, swap the corresponding elements
                swap(array, i, k);              
        }
        swap(array, start, k); // after the indices have crossed, swap the last element in the left partition with the pivot 
        qqsort(array, start, k - 1); // quicksort the left partition
        qqsort(array, k + 1, end); // quicksort the right partition
    } else { // if there is only one element in the partition, do not do any sorting 
        return;
    }
}

现在如您所见，此算法始终将第一个元素作为基准:int pivot = array[start];

我想修改这个算法，让它总是使用最后一个元素而不是子序列的第一个元素，因为我想分析这两个实现的物理运行时间。

我尝试将行 int pivot = array[start]; 更改为 int pivot = array[end]; 但算法随后输出了一个未排序的序列:

//Changes: int pivot = array[end]; 
unsorted: {5 4 3 2 1}
*sorted*: {1 2 5 4 3}

为了测试另一个枢轴，我也尝试使用子序列的中心元素，但算法仍然失败:

//Changes: int pivot = array[(start + end) / 2]; 
unsorted: {5 3 4 2 1}
*sorted*: {3 2 4 1 5}

---

谁能帮我正确理解这个算法，并告诉我我需要做哪些改变才能成功地让这个实现始终选择子序列的最后一个元素作为基准？

Answer 1

问题的原因

问题是你使用了int k = end; .使用 int i = start; 很好当您将枢轴元素作为数组中的第一个元素时，因为您在循环中的检查将略过它( array[i] <= pivot )。但是，当您使用最后一个元素作为基准时，k 停在结束索引处并将基准切换到分区左半部分的位置。您已经遇到麻烦了，因为您的枢轴很可能位于左侧分区内的某处，而不是边界处。

解决方案

要解决此问题，您需要设置 int k = end - 1;当您使用最右边的元素作为枢轴时。您还需要更改将枢轴交换到左右分区之间边界的行:

swap(array, i, end);
qqsort(array, start, i - 1);
qqsort(array, i + 1, end);

你必须为此使用 i 因为 i 将在右分区的最左边元素结束(然后可以与最右边元素中的枢轴交换并且它将保留顺序)。最后，您需要更改 k >= i至 k > i在减少 k 的同时，数组 [-1] 索引错误的变化很小。这在以前是不可能发生的，因为此时 i 总是至少等于 i+1。

应该这样做。

旁注:

这是一个写得不好的快速排序，我不建议从中学习。它有一些无关的、不必要的比较以及其他一些我不会浪费时间列出的错误。我建议在 this presentation 中使用快速排序塞奇威克和宾利。