快速排序和霍尔分区

Question

我很难将使用Hoare分区的QuickSort翻译成C代码，并且无法找到原因。我正在使用的代码如下所示：

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

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r;
    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;
    }
}

另外，我不太明白为什么HoarePartition会起作用。有人能解释一下它为什么可行，或者至少给我一个相关文章的链接吗？

我看过一个分区算法的逐步演示，但我对它没有直观的感觉。在我的代码中，它甚至似乎并没有起作用。例如，给定这个数组：

13 19  9  5 12  8  7  4 11  2  6 21

它将使用枢轴13，但最终会得到该数组

 6  2  9  5 12  8  7  4 11 19 13 21 

它将返回j，即a[j] = 11。我曾以为从那一点开始并往前的数组应该具有比枢轴更大的值，但这在这里不是真的，因为11 < 13。

以下是Hoare分区的伪代码（来自CLRS第二版），如果有用的话：

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  return   j 

谢谢！

编辑：

这个问题的正确C代码将会是：

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

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r;
    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;
    }
}

- Ofek Ron

---

是的，我有，编辑了原始答案。 - Ofek Ron

我认为你编辑了原始问题。 - H H

检查一下你的数据样本，你从12个元素变成了11个（缺失了13个）。这不可能。 - H H

请按照以下链接翻译有关编程的内容：http://www.umiacs.umd.edu/~joseph/classes/enee641/assign5-solution.pdf。只返回翻译后的文本。 - Ofek Ron

请澄清一下，“CLRS，第二版”是什么？请提供该书的标准引用或链接。 - Al Kepp

我不明白为什么对于两个元素它不能工作？如果（end-start<2）返回； - codey modey

Answer 1

回答“为什么Hoare划分方法有效”的问题：

让我们将数组中的值简化为仅三种：小于主元值的L值、等于主元值的E值和大于主元值的G值。

我们还将数组中的一个特定位置命名为s，并且当该过程完成时j指针所在的位置就是s。我们是否提前知道位置s是哪个位置？不，但我们知道某个位置将符合这个描述。

有了这些术语，我们可以稍微不同地表达划分过程的目标：将单个数组拆分为两个较小的子数组，使它们相对彼此而言“未排序错误”。如果满足以下条件，即满足“未排序错误”要求：

1. “低”子数组，从数组的左端开始到包括s为止，不包含任何G值。 2. “高”子数组，从s后面立即开始并继续向右端，不包含任何L值。

只需要做到这些即可。我们甚至不需要担心在任何给定的过程中E值会落在哪个位置。只要每个过程相对于彼此正确地获得子数组，后续过程将处理任何子数组内存在的任何混乱。

现在让我们从另一方面回答问题：划分过程如何确保s左侧没有G值，s右侧没有L值？

嗯，“在s右侧的值集合”与“当j指针移动到s之前，j指针经过的单元格集合”相同。 而“包括s在内的左侧值集合”与“j到达s之前i指针经过的值集合”相同。

这意味着任何“错位”的值都将在循环的某个迭代中位于两个指针之一下。（为方便起见，假设是j指针指向L值，但对于i指针指向G值，它的工作方式完全相同。）当j指针停留在一个错放的值时，i指针将在哪里？ 我们知道它将是：

1. 在“低”子数组的位置，L值可以毫无问题地放置;
2. 指向一个既可以是E值也可以是G值的值，它可以轻松替换j指针下的L值。（如果不是E或G值，它就不会停在那里。）

请注意，有时i和j指针实际上都会停在E值上。 当发生这种情况时，即使没有必要，值也将被交换。 但这不会造成任何伤害。我们之前说过E值的放置不能导致子数组之间的错位排序。

因此，总结一下，Hoare分区之所以有效，是因为：

1. 它将数组分成较小的子数组，这些子数组相对于彼此而言不是错位排序的；
2. 如果你一直这样做，对子数组进行递归排序，最终未排序的数组将不复存在。

- afeldspar

---

当 j 指针指向一个错误的值时，i 指针会在哪里？我们知道它将是：难道 i 会越过 j 的可能性吗？ - codey modey

“i会不会有可能越过j？”是的，i和j在某个时刻要么会相遇，要么会停留在同一个值上。但当这两种情况中的任何一种发生时，条件（i < j）将失败，程序将返回值j。 - afeldspar

Answer 2

我认为这段代码存在两个问题。首先，在你的快速排序函数中，我觉得你想要重新排列这些行。

 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分区算法（链接中引用），该算法可扩展地处理相等的键。

希望这可以帮到您！

- templatetypedef

---

不要在 j=r+1 上做任何操作。从调用模式可以看出，这里使用了真正的 C [inclusiveStart, ExclusiveEnd) 约定。 - H H

@Henk Holterman- 你确定吗？我在我的机器上测试了一下，它明显使用了包含端点；如果你提供一个由十个元素组成的数组并指定范围[0,9]，它会正确地对其进行排序。 - templatetypedef

@Ofek Ron- 经过这个更改，代码在我的机器上可以运行。你是如何指定要排序的范围的端点的？ - templatetypedef

如果你将 Hoare 步骤中返回 j+1 和迭代该范围结合起来，那么我可以看到它会无限循环。我不确定为什么我们得到了不同的值，因为当我在我的机器上运行这个程序并使用 Valgrind 运行时，没有报告任何问题。我们一定是在做某些微妙的不同之处... - templatetypedef

我会把最终的代码放在原问题中，这是我们比较结果的唯一方式。 - Ofek Ron

Answer 3

你的最终代码有误，因为j的初始值应该是r + 1而不是r。否则，你的分区函数总是会忽略最后一个值。

实际上，HoarePartition之所以有效，是因为对于任何包含至少2个元素（即p < r）的数组A[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. “partition part”仅是伪代码的翻译。（请注意返回值为j）

2. 对于递归部分，请注意基本情况的检查（end <= start而不是end <= start + 1，否则您将跳过[2 1]子数组）

- VMatrix1900

Answer 4

首先，您误解了Hoare的分区算法，可以从C语言翻译代码中看出。由于您将枢轴视为子数组的最左边元素，因此发生了误解。

我会解释一下您是如何将最左边的元素视为枢轴的。

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

这里的p和r代表可以作为更大数组（子数组）的一部分进行分区的数组的下限和上限。

所以我们开始时将指针（标记）初始化为指向数组之前和之后的端点（仅仅是因为使用了do while循环）。因此，

i=p-1,

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

现在根据分区，我们希望将枢轴左侧的每个元素小于或等于枢轴，并且右侧大于枢轴。

因此，我们将移动“i”标记，直到找到大于或等于枢轴的元素。同样，“j”标记也是如此，直到找到小于或等于枢轴的元素。

现在，如果 i < j，则交换这两个元素，因为它们都位于数组的错误部分。所以代码将是：

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'位置。

因此，现在分区后的数组从“开始到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);
}

- user7011329

Answer 5

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;
    }
}

- Hrishikesh Mishra

Answer 6

你的上一个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]大或者i == r。 所以我们必须交换以保证分区的特性。

- xxx7xxxx

---

CLRS 提出了 Lomuto 分区方案，而不是 Hoare。 - plasmacel

Answer 7

1. 将枢轴移动到第一位。（例如，使用三个中位数。对于小输入大小，切换到插入排序。） 2. 分区，

• 重复交换当前最左边的1和当前最右边的0。
  0 - cmp（val，pivot）== true，1 - cmp（val，pivot）== false。
  如果不是左小于右，则停止。
• 之后，将枢轴与最右边的0交换。

- qeatzy