16

我很难将带有 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;
    }
}
4

7 回答 7

9

要回答“为什么 Hoare 分区有效？”的问题：

让我们将数组中的值简化为三种： L值（小于枢轴值）、E值（等于枢轴值）和G值（大于枢轴值）。

我们还将给数组中的一个位置一个特殊的名称；我们将此位置称为s，它是过程完成时j指针所在的位置。我们是否提前知道s是哪个位置？不，但我们知道某些位置将符合该描述。

使用这些术语，我们可以用稍微不同的术语来表达分区过程的目标：它将单个数组分成两个较小的子数组，这些子数组彼此之间没有错误排序。如果满足以下条件，则满足“未错误排序”的要求：

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

这就是我们真正需要做的。我们甚至不需要担心E值在任何给定的传递中结束。只要每次传递都使子数组彼此正确，以后的传递就会处理任何子数组中存在的任何无序。

那么现在让我们从另一边来解决这个问题：分区过程如何确保s或其左侧没有G值，并且s右侧没有L值？

好吧，“s 右侧的值集”与“ j指针在到达s之前移动过的单元格集”相同。并且“s 左侧并包含s的值的集合”与“ j到达s之前i指针移动过的值的集合”相同。

这意味着在循环的某些迭代中，任何放错位置的值都将位于我们的两个指针之一之下。（为方便起见，假设它是指向L值的j指针，尽管它与指向G值的i指针完全相同。）当j指针位于错位的值上时，i指针会在哪里？我们知道它将是：

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

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

因此，总而言之，Hoare 分区之所以有效，是因为：

  1. 它将一个数组分成更小的子数组，这些子数组彼此之间没有错误排序；
  2. 如果您继续这样做并递归地对子数组进行排序，那么最终数组中将没有任何未排序的东西。
于 2014-07-26T15:34:41.253 回答
5

我相信这段代码有两个问题。对于初学者，在您的快速排序功能中，我认为您想重新排序行

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

希望这可以帮助！

于 2011-08-25T23:05:30.173 回答
3

Your final code is wrong, since the initial value of j should be r + 1 instead of r. Otherwise your partition function always ignore the last value.

Actually, HoarePartition works because for any array A[p...r] which contains at least 2 elements(i.e. p < r), every element of A[p...j] is <= every element of A[j+1...r] when it terminates. So the next two segments that the main algorithm recurs on are [start...q] and [q+1...end]

So the right C code is as follows:

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

More clarifications:

  1. partition part is just the translation of the pseudocode. (Note the return value is j)

  2. for the recursive part, note that the base case checking (end <= start instead of end <= start + 1 otherwise you will skip the [2 1] subarray )

于 2016-05-23T16:38:42.090 回答
2

首先你误解了Hoare的划分算法，这可以从c中的翻译代码中看出，因为你认为pivot是子数组的最左边的元素。

生病解释你考虑最左边的元素作为枢轴。

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

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

所以我们从最初指向数组端点前后的指针（标记）开始（只需 bcoz 使用 do while 循环）。因此，

i=p-1,

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

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

所以我们将移动“i”标记，直到我们得到大于或等于枢轴的元素。并且类似地'j'标记，直到我们找到小于或等于枢轴的元素。

现在如果 i < 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到j'

上半部分是从 'j+1 到 end'

所以代码看起来像

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);
}
于 2017-02-20T06:44:25.027 回答
2

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;
    }
}
于 2017-04-09T08:48:14.083 回答
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。所以我们必须交换来保证一个分区的特性。

于 2013-10-18T14:08:39.263 回答
0
  1. 将枢轴移到第一个。（例如，使用三的中位数。为小输入大小切换到插入排序。）
  2. 分割，
    • 反复交换当前最左边的 1 和当前最右边的 0。
      0 -- cmp(val, pivot) == true, 1 -- cmp(val, pivot) == false。
      如果不左 < 右则停止。
    • 之后，将枢轴与最右边的 0 交换。
于 2017-01-14T14:52:34.710 回答