试图弄清楚为什么 Hoare 快速排序可以正常工作。基本上我无法向自己证明我们不能创建一个会导致 Hoare 排序算法失败的数组。证明不必是 100% 数学。我只是想相信算法有效。
在下面的代码中，我重写了算法的某些部分以使我更清楚（基本思想保持不变）。
void quickSort(int[] arr, int start, int end) {
int pivotIndex = partition(arr, start, end);
if (start < pivotIndex - 1) quickSort(arr, start, pivotIndex - 1);
if (end >= pivotIndex) quickSort(arr, pivotIndex, end);
}
int partition(int[] arr, int leftIndex, int rightIndex) {
int pivot = arr[(leftIndex + rightIndex) / 2];
while (true) {
while (arr[leftIndex] < pivot) leftIndex++;
while (arr[rightIndex] > pivot) rightIndex--;
if (leftIndex == rightIndex) return leftIndex + 1;
if (leftIndex < rightIndex) {
swap(arr, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
if (leftIndex > rightIndex) return leftIndex;
}
}
我对该功能100％确定：
- 函数应该将数组分成两个子数组
- 低- 包含小于或等于枢轴的元素
- high - 包含大于或等于枢轴的元素
- 分区完成后，leftIndex不能大于rightIndex超过 1。换句话说：leftIndex - rightIndex 仅等于 0 或 1。
- 函数总是返回高子数组中第一个元素的第一个索引
我完全不明白的是：
第一个问题：
为什么如果代码
if (leftIndex < rightIndex) {
swap(arr, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
已经执行，并且在leftIndex等于rightIndex 之后，这并不意味着数组已经成功分区，我们可以返回leftIndex + 1吗？为了澄清我的想法，请看下面的代码：
int partition(int[] arr, int leftIndex, int rightIndex) {
int pivot = arr[(leftIndex + rightIndex) / 2];
while (true) {
while (arr[leftIndex] < pivot) leftIndex++;
while (arr[rightIndex] > pivot) rightIndex--;
// remove line from here
//if (leftIndex == rightIndex) return leftIndex + 1;
if (leftIndex < rightIndex) {
swap(arr, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
// move it here. If I do that, code stop working and sort array in a wrong way
//sorce array: [6, 3, 12, 10, 3, 8, 5, 8, 11, 2, 9]
//final array: [2, 3, 3, 5, 6, 8, 8, 9, 10, 12, 11] - 12 and 11 at wrong places
if (leftIndex == rightIndex) return leftIndex + 1;
if (leftIndex > rightIndex) return leftIndex;
}
}
第二个问题：
让我们想象一下以下场景。假设枢轴值为 10，并且以下代码已成功执行：
01 while (arr[leftIndex] < pivot) leftIndex++;
02 while (arr[rightIndex] > pivot) rightIndex--;
03 if (leftIndex == rightIndex) return leftIndex + 1;
之后，假设leftIndex和rightIndex在索引X和value = 6的元素处停止，即arr[X] -> 6。第 3 行将返回索引X + 1的值，比如说8。所以基本上我们会有子数组：
[..., ...] and [8, ..., 10, ...]
所以高子数组将包含小于枢轴的元素。是否可以创建这样的阵列来复制该场景？
