#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<time.h>
using namespace std;

#define MaxSize 100
typedef int KeyType;

int Partition(KeyType R[],int i,int j){
    //对R[low..high]做划分,并返回基准记录的位置
    //用区间的第1个记录作为基准
    KeyType pivot=R[i];//用区间的第1个记录作为基准
    while(i<j){//从区间两端交替向中间扫描，直至i=j为止
        while(i<j&&R[j]>=pivot)//pivot相当于在位置i上
            j--;//从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]
        if(i<j) //表示找到的R[j]的关键字<pivot.key
            R[i++]=R[j];//相当于交换R[i]和R[j]，交换后i指针加1
        while(i<j&&R[i]<=pivot)//pivot相当于在位置j上
            i++;//从左向右扫描，查找第1个关键字大于pivot.key的记录R[i]
        if(i<j)//表示找到了R[i]，使R[i].key>pivot.key
            R[j--]=R[i];//相当于交换R[i]和R[j]，交换后j指针减1
    }
    R[i]=pivot;//基准记录已被最后定位
    return i;//基准元素位置
}

int RandomPartition(KeyType R[],int i,int j){
    //对R[low..high]做随机划分,并返回基准记录的位置
    //取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准
    srand((unsigned)time(NULL));
    int k=i+rand()%(j-i+1);
    swap(R[k],R[i]);
    //下面的步骤与Partition函数相同,不再作注释
    KeyType pivot=R[i];
    while(i<j){
        while(i<j&&R[j]>=pivot)
            j--;
        if(i<j)
            R[i++]=R[j];
        while(i<j&&R[i]<=pivot)
            i++;
        if(i<j)
            R[j--]=R[i];
    }
    R[i]=pivot;
    return i;
}

void QuickSort(KeyType R[],int low,int high){
    //对R[low..high]快速排序
    int pivotpos;//划分后的基准记录的位置
    if(low<high){//仅当区间长度大于1时才须排序
        //pivotpos=Partition(R,low,high);
        pivotpos=RandomPartition(R,low,high);//对R[low..high]做划分
        QuickSort(R,low,pivotpos-1);//对左区间递归排序
        QuickSort(R,pivotpos+1,high);//对右区间递归排序
    }
}

//*****************************测试函数***************************
int main(){
    int n,R[MaxSize];
    printf("请输入数组大小：\n");
    scanf("%d",&n);
    printf("请输入数组元素：\n");
    for(int i=1;i<=n;i++)
        scanf("%d",&R[i]);
    printf("Before sorting:\n");
    for(int i=1;i<=n;i++)
        printf("%d  ",R[i]);
    printf("\n");
    QuickSort(R,1,n);
    printf("After sorting:\n");
    for(int i=1;i<=n;i++)
        printf("%d  ",R[i]);
    printf("\n");
    return 0;
}

• 最好时间复杂度：在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)。用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。
  
• 空间复杂度：快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。
  
• 稳定性：快速排序是非稳定的，例如[2，2，1]。