修改此Quicksort以始终使用最后一个元素作为轴

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}

为了测试另一个数据透视表,我也尝试使用子序列的center元素,但算法仍然失败:

//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;将pivot元素作为数组中的第一个元素时使用它是很好的,因为循环中的检查将略过它(array[i] <= pivot).但是,当您使用最后一个元素作为数据透视表时,k将停止在结束索引上,并将数据透视切换到分区左半部分的位置.你已经遇到了麻烦,因为你的枢轴很可能位于左侧分区内而不是边界处.

解决方案

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

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

你必须使用i来实现这一点,因为我将最终在右边分区的最左边的元素(然后可以与最右边元素中的枢轴交换,它将保留顺序).最后,你需要更改k >= i为k > i减少k的while,否则数组[-1]索引错误的变化很小.之前不可能发生这种情况,因为此时我总是至少等于i + 1.

应该这样做.

边注:

这是一个写得不好的快速入口,我不建议学习.它有一些无关紧要的,不必要的比较以及其他一些我不会浪费时间列出的错误.我建议在Sedgewick和Bentley的演示文稿中使用quicksorts .