如何在快速排序中设置枢轴

Question

我只是更新了我的代码，它可以工作，但是当我运行它时出现了一些问题。我放了一些 "cout" 来调试我的 partiton 部分，但我不知道为什么它总是将 0 设置为 pivot。（pivot 应该是我输入的最后一个数字）

这是我的代码

    int partiton(vector<int> &a, int low, int up)
{
      int pivot = a[up];
      int i = low-1;
      for (int j = low; j < up; j++)
      {
            if(a[j] <= pivot)
            {
                  i++;
                  swap(a[i], a[j]);
            }
      }
      swap(a[i+1], a[up]);
      cout<<"pivot: ";
      cout<<pivot<<" "<<endl;
      return i+1;
}

void quickSort(vector<int> &a, int low, int up)
{
      if(low < up)
      {
            int mid = partiton(a, low, up);
            //watch out! The mid position is on the palce, so we don't need to consider it again
            //That's why below is mid-1, not mid! Otherwise it will occur overflow error!
            quickSort(a, low, mid-1);
            quickSort(a, mid+1, up);
      }
}

void quickSort(vector<int>&, int, int);

int main()
{
    vector<int> A;

    int numbers;

    while(cin>>numbers)
    {
        A.push_back(numbers);
    }

    int low = 0;
    int up = A.size();

    cout<<"No sorted numbers: ";

    for(int i; i < up; i++)
    {
        cout<<A[i]<<" ";
    }
    cout << endl;

    quickSort(A, low, up);

    cout<<"Has sorted numbers: ";

    for(int i; i < up; i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}

Answer 1

您的问题的解决方案是在 partition 和 quickSort 函数的定义中将 int a[] 更改为 vector<int> a。所以 int partiton(vector<int> a, int low, int up) 和 void quickSort(vector<int> a, int low, int up) 应该足以编译无错误代码。

编译器希望调用的函数的参数类型与函数声明中的类型相同，或者至少声明的参数类型必须能够自动解析（换句话说，推导或绑定）到特定函数调用的相应参数类型。编译器无法将 vector 绑定到 int a[] 类型，因此出现错误。

如何在快速排序中设置枢轴

how to set the pivot in quick sort

c++

quicksort