快速排序

快排属于交换排序，是起泡（冒泡Bubble）排序的进一步优化
http://codevs.cn/problem/1076/
AC代码

#include<iostream>
using namespace std;
#define OK 1
#define MOD 99999997
#define MAXSIZE 100005

typedef int Status;
struct A
{
    int key;
    int b;
};
typedef struct
{
    A *r;
    int length;
}SqList;
typedef SqList RedType;
Status InitList(SqList &L);
void QSort ( SqList &L,int low,  int  high ) ;
int Partition ( SqList &L,int low,  int  high );
void Merge(RedType &R,RedType &T,int low,int mid,int high);
void MSort(RedType &R,RedType &T,int low,int high);
int count=0;

void swap(SqList &L)
{
    for(int i=1;i<=L.length;i++)
    {
        L.r[0].key=L.r[i].key;
        L.r[i].key=L.r[i].b;
        L.r[i].b=L.r[0].key;
    }
}
int main ( )
{
    SqList L;
    InitList(L);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>L.r[i].key;
    }
    L.length=n;
    QSort(L,1,L.length);
    for(int i=1;i<=n;i++)
    {
        cout<<L.r[i].key<<" ";
    }
    return 0;
    SqList T;
    InitList(T);
    count=0;
    QSort(L,1,L.length);
    swap(L);
    MSort(L, T,1, L.length );
    cout<<count%MOD<<endl;
}
void QSort ( SqList &L,int low,  int  high ) 
{  if  ( low < high ) 
    {  
        int pivotloc = Partition(L, low, high );
        QSort(L,low,pivotloc-1); 
        QSort(L, pivotloc+1, high ); 
     }
}
int Partition ( SqList &L,int low,  int  high ) 
{  
    L.r[0] = L.r[low];  
    int pivotkey = L.r[low].key;
   while  ( low < high ) 
    { while ( low < high && L.r[high].key >= pivotkey )  --high;
                 L.r[low] = L.r[high];
      while ( low < high && L.r[low].key <= pivotkey )  ++low;
                 L.r[high] = L.r[low];
     }
    L.r[low]=L.r[0]; 
    return low;
}
Status InitList(SqList &L)
{
    L.r=new A[MAXSIZE];
    L.length=0;
    return OK;
}
void Merge(RedType &R,RedType &T,int low,int mid,int high)
{   
    int i=low;int j=mid+1;int k=low; 
    while(i<=mid&&j<=high)  //将R中记录由小到大地并入T中
    {
        if(R.r[i].key<=R.r[j].key) 
            T.r[k++]=R.r[i++]; 
        else 
        {
            count+=(mid-i+1);
            T.r[k++]=R.r[j++]; 
        }
    }                   
    while(i<=mid) T.r[k++]=R.r[i++];    //将剩余的R[low..mid]复制到T中 
    while(j<=high) T.r[k++]=R.r[j++];//将剩余的R[j.high]复制到T中 
}
void MSort(RedType &R,RedType &T,int low,int high)
{  

    if(low==high) 
    {
        T.r[low]=R.r[low];
    }
    else
    { 
        SqList S;
        InitList(S);
        int mid=(low+high)/2;       //将当前序列一分为二，求出分裂点mid 
        MSort(R,S,low,mid);     //R[low..mid]递归，结果放入S[low..mid] 
        MSort(R,S,mid+1,high);//R[mid+1..high]递归，结果放入S[mid+1..high]
        Merge(S,T,low,mid,high);//将S[low..mid]和S[mid+1..high]归并到T[low..high]
    }                       
}