QuickSort和Hoare分区
我很难将QuickSort与Hoare分区转换为C代码，但无法找到原因。 我正在使用的代码如下所示：
void QuickSort(int a[],int start,int end) { int q=HoarePartition(a,start,end); if (end 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 x); do i++; while (a[i] < x); if (i < j) swap(&a[i],&a[j]); else return j+1; } }
回答“为什么Hoare分区工作？”的问题：
让我们将数组中的值简化为三种： L值（小于透视值的值）， E值（等于透视值）和G值（大于透视值的值）。
我们还将为数组中的一个位置指定一个特殊名称; 我们将这个位置称为s ，它是程序结束时j指针所在的位置。 我们提前知道哪个位置是？ 不，但我们知道某个位置符合该描述。
使用这些术语，我们可以用稍微不同的术语表达分区过程的目标：它是将单个数组拆分成两个较小的子数组，这些子数组不会相互错误排序 。 如果满足以下条件，则满足“未错误排序”的要求：
- 从arrays的左端到包括s的“低”子arrays不包含G值。
- “高”子数组在s之后立即开始并继续到右端，不包含L值。
这才是我们真正需要做的。 我们甚至不需要担心E值在任何给定的传球中都会结束。 只要每个传递使子arrays相对于彼此正确，后来的传递将处理任何子arrays内存在的任何障碍。
那么现在让我们从另一方面解决这个问题：分区过程如何确保s或左边没有G值，而s的右边没有L值？
好吧，“ s右边的值集合”与“ j指针到达s之前移动的单元格集”相同。 并且“包括s的左侧的值集合”与“在j到达s之前i指针移动的值的集合”相同。
这意味着在循环的某些迭代中，任何错放的值都将位于我们的两个指针中。 （为方便起见，假设它是指向L值的j指针，尽管它对于指向G值的i指针的工作方式完全相同。）当指针位于错位值时， i指针在哪里？ 我们知道它将是：
- 在“低”子arrays中的某个位置， L值可以没有问题;
- 指向一个值为E或G的值，可以轻松替换j指针下的L值。 （如果它不是E或G值，它就不会停在那里。）
请注意，有时i和j指针实际上都会停止在E值上。 发生这种情况时，即使不需要，也会切换值。 但这并没有造成任何伤害; 我们之前说过， E值的放置不会导致子arrays之间的错误排序。
总而言之，Hoare分区的工作原理是：
- 它将一个数组分成较小的子数组，这些子数组相对于彼此没有错误排序;
- 如果你继续这样做并递归地对子数组进行排序，那么最终将没有任何内容未被排序。
我相信这段代码存在两个问题。 首先，在你的Quicksortfunction中，我想你想重新排序
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版本中，这里没有提到; 我不得不去书的勘误页找到这个。 这几乎可以肯定是“访问超出范围”错误所遇到的问题的原因，因为在不变的情况下，您可能会立即从arrays中运行！
至于Hoare分区的分析，我建议首先手动追踪它。 这里还有更详细的分析。 直观地说，它的工作原理是从范围的两端向另一端增长两个范围 - 一个在左侧，包含小于枢轴的元素，另一个在右侧包含大于枢轴的元素。 这可以稍微修改以产生Bentley-McIlroy分区算法（在链接中引用），该算法可以很好地扩展以处理相等的密钥。
希望这可以帮助！
你的最终代码是错误的，因为j的初始值应该是r + 1而不是r 。 否则，您的分区函数始终忽略最后一个值。
实际上，HoarePartition是有效的，因为对于包含至少2个元素（即p < r ）的任何数组A[p...r] ， A[p...j]每个元素都是<= A[j+1...r]每个元素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; } }
更多说明：
-
分区部分只是伪代码的翻译。 （注意返回值是
j） -
对于递归部分，请注意基本情况检查（
end <= start而不是end <= start + 1否则您将跳过[2 1]子arrays）
你最后的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。 所以我们必须交换以保证分区的function。
- 将枢轴移至第一位。 （例如，使用三个中值。切换到小输入大小的插入排序。）
- 划分，
- 重复交换当前最左边的1与当前最右边的0。
0 – cmp（val，pivot）== true，1 – cmp（val，pivot）== false。
如果没有离开<停止。 - 之后，交换枢轴最右边的0。
- 重复交换当前最左边的1与当前最右边的0。
首先，你误解了Hoare的分区算法，可以从c中的翻译代码中看出，因为你认为枢轴是子arrays的最左边元素。
我会解释你将最左边的元素视为枢轴。
int HoarePartition (int a[],int p, int r)
这里p和r表示数组的下限和上限，它也可以是要分区的更大数组（子arrays）的一部分。
所以我们从最初指向数组终点之前和之后的指针（标记）开始（简单地说是使用do while循环的bcoz）。因此，
i=p-1, j=r+1; //here u made mistake
现在按照分区我们希望枢轴左边的每个元素小于或等于pivot，大于pivot的右侧。
因此，我们将移动’i’标记，直到我们得到大于或等于枢轴的元素。 类似’j’标记，直到我们发现元素小于或等于pivot。
现在如果我 现在如果'i'不小于'j'，那意味着现在交换中没有元素，所以我们返回'j'位置。 所以现在分区后半部分的数组是从'start to j' 上半部分是从'j + 1到结尾' 所以代码看起来像
do j--; while (a[j] <= x); //look at inequality sign do i++; while (a[i] >= x); if (i < j) swap(&a[i],&a[j]);
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; } }