快速排序C++实现

算法思想来自《算法导论》

#include <iostream>
#include <vector>
#include <cstdlib>
#include <random>
#include <ctime>
const int SIZE = 10;
using namespace std;
//Data swap function
void swap(int &p,int &q)
{
    int temp = p;
    p=q;
    q=temp;
}

//Partition function
template <typename T>
int Partition(vector<T> & arr,int p,int r)
{
    T x = arr[r];
    int i = p -1;
    for (int j = p; j < r;j++)
    {
        if(arr[j] <= x)
        {
            i = i+1;
            swap(arr[i],arr[j]);
        }
    }
    swap(arr[i+1],arr[r]);
    return (i+1);
}

//Quick sort
template <typename T>
void Quick_sort(vector<T> & arr,int nLow,int nHigh)
{
    if(nLow < nHigh)
    {
        int nIndex=Partition(arr, nLow, nHigh);
        Quick_sort(arr , nLow, nIndex-1);
        Quick_sort(arr , nIndex+1, nHigh);
    }
}

int main()
{
    vector<int> arr;
    srand((unsigned)time(0));

    for(int i = 0; i < SIZE;i++)
        arr.push_back((int)rand()%(10 * SIZE));

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

    Quick_sort(arr,0,SIZE-1);

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

    return 0;

}