问题 QuickSort和Hoare分区

我相信这段代码存在两个问题。首先，在你的Quicksort功能中，我想你想重新排序

 int q=HoarePartition(a,start,end);
 if (end<=start) return;

所以你有这样的：

 if (end<=start) return;
 int q=HoarePartition(a,start,end);

但是，你应该做的比这更多;特别是这应该读

 if (end - start < 2) return;
 int q=HoarePartition(a,start,end);

原因是如果您尝试分区的范围大小为零或一，则Hoare分区无法正常工作。在我的CLRS版本中，这里没有提到;我不得不去 这本书的勘误页面 找到这个。这几乎可以肯定是“访问超出范围”错误所遇到的问题的原因，因为在不变的情况下，您可能会立即从阵列中运行！

至于Hoare分区的分析，我建议首先手动追踪它。还有一个更详细的分析 这里。直观地说，它的工作原理是从范围的两端向另一端增长两个范围 - 一个在左侧，包含小于枢轴的元素，另一个在右侧包含大于枢轴的元素。这可以稍微修改以产生Bentley-McIlroy分区算法（在链接中引用），该算法可以很好地扩展以处理相等的密钥。

希望这可以帮助！

你的最终代码是错误的，因为它的初始值 j 应该 r + 1 代替 r。否则，您的分区函数始终忽略最后一个值。

实际上，HoarePartition适用于任何阵列 A[p...r] 它包含至少2个元素（即 p < r），每一个元素 A[p...j] 是 <= 每个元素 A[j+1...r] 当它终止。 所以主要算法重复出现的下两个段是 [start...q] 和 [q+1...end]

所以正确的C代码如下：

void QuickSort(int a[],int start,int end) {
    if (end <= start) return;
    int q=HoarePartition(a,start,end);
    QuickSort(a,start,q);
    QuickSort(a,q + 1,end);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r+1;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);
        if  (i < j) 
            swap(&a[i],&a[j]);
        else 
            return j;
    }
}

更多说明：

1. 分区部分只是伪代码的翻译。 （注意返回值是 j）

2. 对于递归部分，请注意基本情况检查（end <= start 代替 end <= start + 1 否则你会跳过 [2 1] 子阵列）

你最后的C代码工作。但这并不直观。 现在我幸运地正在学习CLRS。 在我看来，CLRS的伪代码是错误的。（在2e） 最后，我发现改变一个地方是对的。

 Hoare-Partition (A, p, r)
 x ← A[p]
     i ← p − 1
     j ← r + 1
 while  TRUE
        repeat   j ←  j − 1
            until     A[j] ≤ x
    repeat   i ←  i + 1
            until     A[i] ≥ x
    if  i < j
              exchange  A[i]  A[j]
    else  
              exchnage  A[r]  A[i]  
              return   i

是的，添加交换A [r] A [i]可以使它工作。 为什么？ 因为A [i]现在大于A [r] OR i == r。 所以我们必须交换以保证分区的功能。

1. 将枢轴移至第一位。 （例如，使用三个中值。切换到小输入大小的插入排序。）
2. 划分，
   • 重复交换当前最左边的1与当前最右边的0。
     0 - cmp（val，pivot）== true，1 - cmp（val，pivot）== false。
     如果没有离开<停止。
   • 之后，交换枢轴最右边的0。

首先，你误解了Hoare的分区算法，可以从c中的翻译代码看出， 因为你认为枢轴是子阵列最左边的元素。

我会解释你将最左边的元素视为枢轴。

int HoarePartition (int a[],int p, int r) 

这里p和r表示数组的下限和上限，它也可以是要分区的更大数组（子阵列）的一部分。

所以我们从最初指向数组终点之前和之后的指针（标记）开始（简单地说是使用do while循环的bcoz）。因此，

i=p-1,

j=r+1;    //here u made mistake

现在按照分区我们希望枢轴左边的每个元素小于或等于pivot，大于pivot的右侧。

因此，我们将移动'i'标记，直到我们得到大于或等于枢轴的元素。类似'j'标记，直到我们发现元素小于或等于pivot。

现在如果我<j我们交换元素bcoz这两个元素都在数组的错误部分。所以代码将是

do  j--; while (a[j] <= x);                 //look at inequality sign
do  i++; while (a[i] >= x);
if  (i < j) 
    swap(&a[i],&a[j]);

现在如果'i'不小于'j'，那意味着现在交换中没有元素，所以我们返回'j'位置。

所以现在分区后半部分的数组是从'start to j'

上半部分是从'j + 1到结尾'

所以代码看起来像

void QuickSort(int a[],int start,int end) {
    int q=HoarePartition(a,start,end);
    if (end<=start) return;
    QuickSort(a,start,q);
    QuickSort(a,q+1,end);
}

在Java中直接实现。

public class QuickSortWithHoarePartition {

    public static void sort(int[] array) {
        sortHelper(array, 0, array.length - 1);
    }

    private static void sortHelper(int[] array, int p, int r) {
        if (p < r) {
            int q = doHoarePartitioning(array, p, r);
            sortHelper(array, p, q);
            sortHelper(array, q + 1, r);
        }
    }

    private static int doHoarePartitioning(int[] array, int p, int r) {
        int pivot = array[p];
        int i = p - 1;
        int j = r + 1;

        while (true) {

            do {
                i++;
            }
            while (array[i] < pivot);

            do {
                j--;
            }
            while (array[j] > pivot);

            if (i < j) {
                swap(array, i, j);
            } else {
                return j;
            }
        }

    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}