在quicksort(hoare)中遇到无限循环,但我似乎没有找到问题
Encountering an infinite loop in quicksort(hoare), but I don't seem to find the issue
所以,我写了一个快速排序算法和一个霍尔分区算法。不知何故,当我尝试 运行 main () 中的示例案例时,它在 quickSort(test, 0,3) 上挂起。似乎有一个无限循环。我不知道如何修复它,因为这两个函数单独看来都很好。
我试过调试,但我对 c 还很陌生。我注意到 quickSort(test,0,3) 递归调用自身。所以我知道这个问题与高而不是下降有关。但我从一张大学幻灯片中提取了示例伪代码来构建函数,一切似乎都一致。
void printArray(int A[], int high) {
for (int i=0; i<=high; i++) {
printf("%d ", A[i]);
}
}
int partitionHoare(int A[], int low, int high) {
int pivot=A[low];
int left = low-1;
int right= high+1;
while (1){
while (1){
left++;
if (A[left]>=pivot) break;
}
while (1){
right--;
if (A[right]<=pivot) break;
}
if (left<right) {
int temp=A[left];
A[left]=A[right];
A[right]=temp;
}
else return left;
}
}
void quicksort(int A[], int low, int high){
if (low<high){
int middle=partitionHoare(A,low, high);
quicksort(A, low,middle-1);
quicksort(A, middle, high);
}
}
void main (){
int test[]={64,81,24,42,90,30,9,95};
quicksort(test,0,7);
printArray(test,7);
我实际上希望测试数组按如下方式打印出来:
“9、24、30、42、64、81、90、95”
您的 quicksort()
功能存在逻辑缺陷:
void quicksort(int A[], int low, int high){
if (low<high){
int middle=partitionHoare(A,low, high);
quicksort(A, low,middle-1);
quicksort(A, middle, high);
}
}
它不保证递归会终止。
具体来说,如果在某个长度大于 1 的子数组中,第一个元素最少且不重复,则 partitionHoare()
将 return 等于 [=13 的值=] 而不修改数组。在这种情况下,对左子数组的递归调用将不执行任何操作,但对 right 子数组的递归调用将准确地重复当前参数。什么都没有改变,同样的事情肯定会再次发生,而且会无限期地发生。
在这种情况下,您可以通过在 quicksort()
中测试是否 middle == low
来打破无限递归,但这不会给您正确的排序。
这里的一个常见解决方案是双重的:
- 确保分区函数将主元值交换到它报告的主元索引。这肯定是该值的正确最终位置。
- 递归时,从两个子数组中排除主元索引(我们知道其值是正确的),这样每个子问题肯定小于父问题问题。
将分区更改为 return 右侧(而不是左侧)。将两个递归调用更改为 |快速排序(A,低,中); | quicksort(A, middle+1, high);.这将与 wiki 文章的示例完全匹配:
https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
您可能想要更改 "middle" 的名称。 Wiki 示例将其称为 p 表示分区拆分索引(而不是表示主元索引),因为使用 Hoare 分区方案,主元和等于主元的元素可能会在左分区 and/or 的末尾结束右分区的开始。
所以,我写了一个快速排序算法和一个霍尔分区算法。不知何故,当我尝试 运行 main () 中的示例案例时,它在 quickSort(test, 0,3) 上挂起。似乎有一个无限循环。我不知道如何修复它,因为这两个函数单独看来都很好。
我试过调试,但我对 c 还很陌生。我注意到 quickSort(test,0,3) 递归调用自身。所以我知道这个问题与高而不是下降有关。但我从一张大学幻灯片中提取了示例伪代码来构建函数,一切似乎都一致。
void printArray(int A[], int high) {
for (int i=0; i<=high; i++) {
printf("%d ", A[i]);
}
}
int partitionHoare(int A[], int low, int high) {
int pivot=A[low];
int left = low-1;
int right= high+1;
while (1){
while (1){
left++;
if (A[left]>=pivot) break;
}
while (1){
right--;
if (A[right]<=pivot) break;
}
if (left<right) {
int temp=A[left];
A[left]=A[right];
A[right]=temp;
}
else return left;
}
}
void quicksort(int A[], int low, int high){
if (low<high){
int middle=partitionHoare(A,low, high);
quicksort(A, low,middle-1);
quicksort(A, middle, high);
}
}
void main (){
int test[]={64,81,24,42,90,30,9,95};
quicksort(test,0,7);
printArray(test,7);
我实际上希望测试数组按如下方式打印出来: “9、24、30、42、64、81、90、95”
您的 quicksort()
功能存在逻辑缺陷:
void quicksort(int A[], int low, int high){ if (low<high){ int middle=partitionHoare(A,low, high); quicksort(A, low,middle-1); quicksort(A, middle, high); } }
它不保证递归会终止。
具体来说,如果在某个长度大于 1 的子数组中,第一个元素最少且不重复,则 partitionHoare()
将 return 等于 [=13 的值=] 而不修改数组。在这种情况下,对左子数组的递归调用将不执行任何操作,但对 right 子数组的递归调用将准确地重复当前参数。什么都没有改变,同样的事情肯定会再次发生,而且会无限期地发生。
在这种情况下,您可以通过在 quicksort()
中测试是否 middle == low
来打破无限递归,但这不会给您正确的排序。
这里的一个常见解决方案是双重的:
- 确保分区函数将主元值交换到它报告的主元索引。这肯定是该值的正确最终位置。
- 递归时,从两个子数组中排除主元索引(我们知道其值是正确的),这样每个子问题肯定小于父问题问题。
将分区更改为 return 右侧(而不是左侧)。将两个递归调用更改为 |快速排序(A,低,中); | quicksort(A, middle+1, high);.这将与 wiki 文章的示例完全匹配:
https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
您可能想要更改 "middle" 的名称。 Wiki 示例将其称为 p 表示分区拆分索引(而不是表示主元索引),因为使用 Hoare 分区方案,主元和等于主元的元素可能会在左分区 and/or 的末尾结束右分区的开始。