快速排序

原文链接

# 选取枢纽元
int partition(vector<int> &vi, int low, int up)
{
    int pivot = vi[up];
    int i = low-1;
    for (int j = low; j < up; j++)
    {
        if(vi[j] <= pivot)
        {
            i++;
            swap(vi[i], vi[j]);
        }
    }
    swap(vi[i+1], vi[up]);
    return i+1;
}

# 递归
void quickSort(vector<int> &vi, int low, int up)
{
    if(low < up)
    {
        int mid = partition(vi, low, up);
        //Watch out! The mid position is on the place, 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(vi, low, mid-1);
        quickSort(vi, mid+1, up);
    }
}

# 适配器
void qSort(vector<int> &vi)
{
    quickSort(vi, 0, vi.size()-1);
}

# 主函数
int main()
{
    int a[] = {3,5,7,9,2,3,1,0,7,5,4};
    vector<int> va(a, a+11);

    cout<<"Before quicksort:n";
    for(auto x:va)
        cout<<x<<" ";
    cout<<endl;

    qSort(va);

    cout<<"After quicksort:n";
    for(auto x:va)
        cout<<x<<" ";
    cout<<endl;
    system("pause");
    return 0;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 [email protected]