一个快速排序程序

很讨厌不少教材上排序时两边向中间的扫描的方法，感觉很麻烦。看见《算法导论》上是单向扫描的分区方法，感觉实现起来很简单。这里和《算法导论》上的只有一点不同，基准数选了第一个数（其实没什么区别）。

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;

class QSorter{
    vector<int> data;

    void QS(vector<int>&, int, int);
    int Partition(vector<int>&, int, int);
public:
    void QSort_DM();
    void GenNum(int);
    QSorter(){ srand(time(NULL)); }
    QSorter(int n){ srand(time(NULL)); GenNum(n); }
    void OutData();
};

void QSorter::OutData(){
    cout<<"Data:";
    for(int i=0; i<(int)data.size(); i++)
        cout<<data[i]<<" ";
    cout<<endl;
}

void QSorter::GenNum(int n){
    for(int i=0; i<n; i++)
        data.push_back(rand()%200);
}

void QSorter::QS(vector<int>& v, int low, int high){
    if(low<high){
        int pivot=Partition(v, low, high);
        QS(v, low, pivot-1);
        QS(v, pivot+1, high);
    }
}

int QSorter::Partition(vector<int>& v, int low, int high){
    int x=v[low];   //第一个数是枢轴
    int i=low;      //比枢轴小的左部分最后一个数的下标

    for(int j=low+1; j<=high; j++)
        if(v[j]<x){
            i++;
            swap(v[i], v[j]);
        }
    //找到比枢轴小的数就把它放第i个数后，i+1扩大左部分
    //循环结束时是中左右结构
    swap(v[i], v[low]);
    return i;//和左区第一个数换位，形成左中右结构
}

void QSorter::QSort_DM(){
    QS(data, 0, data.size()-1);
}

int main()
{
    QSorter s1(10);
    s1.OutData();
    s1.QSort_DM();
    s1.OutData();
    return 0;
}

快排的思想也很好理解，每次把比基准数小的放左边，大的放右边，每次分割区间都形成左（小于基准）中（基准数）右（大于基准）的结构。最后传给递归函数的子区间大小为1时，排序结束。

两侧扫描的分区法有一个大神讲的非常棒。