这个快速排序片段有什么问题吗？

Question

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

我需要什么更正？

我按照快速排序算法编写了这段代码。但是它无法打印正确的排序数组。我彻底检查了所有迭代和循环，但找不到错误。请帮忙。

Answer 1

所示代码中存在多个逻辑错误。

        pivot=a[low];
        i=low+1;
        j=high;

正如我们在这里观察到的，

pivot

是数组中的值，而

i

和

j

是索引。

while(i<pivot && j>pivot){

在这里，最终将数组中的值与数组中值的索引进行比较。这没有逻辑意义。在任何排序算法中，数组中的值与同一数组的索引没有逻辑关系。

在典型的快速排序实现中，这可能只是

i<j

，但这在这里也是错误的，原因将变得显而易见。让我们假设这就是您的意图，然后继续：

            while(a[i]<=pivot){
                i++;
            }

这可能会超出数组末尾，从而导致未定义的行为。为了论证，如果数组有两个值，都为零。

low

为

0

，

high

为1，因此初始化后：

i

和

j

都为1，

pivot

为0。

因为

a[1] <= 0

这个

while

循环迭代一次，并且在下一次迭代中

a[2]

变成未定义的行为（当然，没有

a[2]

）。

还有其他边缘条件也会导致第二个 while 循环也产生未定义的行为，但这是一个可以留作家庭作业的练习。

我彻底检查了所有的迭代和循环，但找不到错误。

错误在于，快速排序算法的核心——枢轴逻辑存在逻辑缺陷。