快速排序算法实现

Question

我没有明白我在实施快速排序算法时出错的地方。下面是代码：

#include <bits/stdc++.h>
using namespace std;

int part(vector<int> &arr,int i,int j)
{

   int pivot=i;
    i++;


        while(i<j)
            {

            while(arr[i]<arr[pivot])
                i++;
            while(arr[j]>arr[pivot])
                j--;

            if(i<j)
                swap(arr[i],arr[j]);           


        }

        swap(arr[j],arr[pivot]);
        return j;


}


void quickSort(vector <int> &arr,int p,int r) {

    if(p<r)
        {


        int t=part(arr,p,r);


        quickSort(arr,p,t-1);  

        quickSort(arr,t+1,r);


    }




    }




int main()
{
    int n;
    cin >> n;

    vector <int> arr(n);
    for(int i = 0; i < (int)n; ++i) {
        cin >> arr[i];
    }

    quickSort(arr,0,arr.size()-1);

    for(int i=0;i<arr.size();i++)
        cout<<arr[i]<<" ";
    cout<<endl;

    return 0;
}

我正在提供输入 7 5 8 1 3 7 9 2

但输出为： 2 1 3 7 5 8 9

谁能指出我哪里错了。

Answer 1

如果我没记错的话，

中的条件

if(i<j)
    swap(arr[i],arr[j]);

函数中的part不正确；它应该检查数组值 arr[i] 和 arr[j] 而不是 i 和 j 的关系来决定是否要交换数组条目。

Answer 2

在 "part" 函数中，您将在最后进行交换，即使值已经存在也是如此。只需在交换前检查值：

int part(vector<int> &arr, int i, int j)
{
    int pivot = i;
    i++;
    while (i < j)
    {
        while (arr[i] < arr[pivot])
            i++;
        while (arr[j] > arr[pivot])
            j--;

        if (i < j)
            swap(arr[i], arr[j]);
    }
    if (arr[j] < arr[pivot]) {
        swap(arr[j], arr[pivot]);
    }
    return j;
}

快速排序算法实现

QuickSort Algorithm implementation

algorithm

quicksort