提问人：IronicRayquaza 提问时间：10/4/2023 最后编辑：user207421IronicRayquaza 更新时间：10/4/2023 访问量：88
快速排序的这个片段有什么问题？[关闭]
What is wrong with this snippet for quick sort? [closed]
问：
#include <iostream>
using namespace std;
int f(int a[],int low,int high){
int pivot,i,j,t;
if(low<high){
pivot=a[low];
i=low+1;
j=high;
while(i<pivot && j>pivot){
while(a[i]<=pivot){
i++;
}
while(a[j]>pivot){
j--;
}
}
if(i<j){
t=a[i];
a[i]=a[j];
a[j]=t;
a[low]=a[j];
a[j]=pivot;
f(a,low,j-1);
f(a,j+1,high);
}
}
}
int main(){
int a[100],i,n,low,high;
cout<<"Enter size of array"<<endl;
cin>>n;
cout<<"Enter elements in array"<<endl;
for(i=0;i<n;i++){
cin>>a[i];
}low=0;
high=n-1;
f(a,low,high);
cout<<"Sorted array:"<<endl;
for(i=0;i<n;i++){
cout<<a[i]<<" ";
}
return 0;
}
我在这里需要什么更正？
我遵循了快速排序的算法并编写了这段代码。但是，它无法打印正确的排序数组。我彻底检查了所有的迭代和循环，但没有发现错误。请帮忙。
答：
2赞
Sam Varshavchik
10/4/2023
#1
显示的代码中存在多个逻辑错误。
pivot=a[low];
i=low+1;
j=high;
正如我们在这里所观察到的，是数组中的一个值，而 和 是索引。pivotij
while(i<pivot && j>pivot){
在这里，这最终会将数组中的值与数组中值的索引进行比较。这在逻辑上没有意义。在任何排序算法中，数组中的值与同一数组的索引没有逻辑关系。
在典型的快速排序实现中，这可能只是 ，但在这里也是错误的，原因将变得显而易见。让我们假设这是您的意图，然后继续：i<j
while(a[i]<=pivot){
i++;
}
这可能会在数组的末尾运行，从而导致未定义的行为。如果为了论证，数组有两个值，都是零。 是 ，因此，在初始化后：both 和 will 为 1，并且将为 0。low0highijpivot
由于此循环迭代一次，并且在下一次迭代中成为未定义的行为（当然没有）。a[1] <= 0whilea[2]a[2]
其他边缘条件也会导致第二个 while 循环产生未定义的行为，但这是一个可以作为家庭作业的 excersize。
我彻底检查了所有的迭代和循环，但没有发现错误。
错误在于，作为快速排序算法核心的透视逻辑在逻辑上存在缺陷。这里没有可以修复的单个错误。显示的大多数逻辑都是不正确的，需要从头开始重写，非常小心，并严格遵循有效的快速排序算法逻辑，一步一步。
下一个：快速排序的分段错误
评论
while(i<pivot && j>pivot){- here 和 是索引，但是一个值。ijpivotf(a,low,j-1);std::stringint