快速排序

基本思想：在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单
元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。

在排序之前,先设定一个哨兵值,一般选择a[0],将其值赋给一个临时变量:x=a[0];然后开始左右移动下标i、j值；

直到（a[i]>=x且a[j]<=x）或（i>=j）停止.交换a[i]、a[j]的值

继续移动下标i、j值，直到（a[i]>=x且a[j]<=x）或（i>=j）停止.

交换a[p] 和 a[j]的值
 a[p] = a[j] ,a[j] = x

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;


//,产生m到n的随机数，把范围[m,n）改变到[0，X)，到最后再转移回去。三种情况
int Random(int m, int n)
{
        int pos, dis;
        if(m == n)
        {
            return m;
        }
        else if(m > n)
        {
            pos = n;
            dis = m - n + 1;
            return rand() % dis + pos;
        }
        else
        {
            pos = m;
            dis = n - m + 1;
            return rand() % dis + pos;
        }
}

int Partition(int a[],int p,int r)
{
    int i = p,j = r+1;
    int x = a[p]; //哨兵
    //将小于x的元素交换到左边区域，将大于x的元素交换到右边区域
    while(true)
    {
        while(a[++i] < x && i < r);
        while(a[--j] > x);
        if(i >= j) break;
        swap(a[i],a[j]);
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}

//在数组中随机选取一个元素作为划分基准，
//这样是划分基准的选择是随机的，从而可以期望划分是较对称的
int RandomPartition(int a[],int p,int r)
{
    srand((int)time(NULL));
    int i = Random(p,r);
    swap(a[p],a[i]);
    return Partition(a,p,r);
}

void QuickSort(int a[],int p,int r)
{
    if(p < r)
    {
        int q = RandomPartition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}

int main()
{
    int n,a[100];
    cout << "请输入要排序的元素的个数：";
    cin >> n;
    cout << "请输入要排序的元素：";
    for(int i = 0; i < n; i++)
        cin >> a[i];
    QuickSort(a,0,n-1);
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}