快速排序

快速排序是分治算法的典型应用，基本策略：

将数组A[1..n]分成两个子数组B[1..p]和B[p+1..n],使得B[1..p]中的元素均不大于B[p+1..n]中的元素，然后分别对这两个数组进行排序，最后把两个数组连接起来。

代码

#include <iostream>
using namespace std;

void printArray(int a[],int n){
    for(int i=0;i<n;i++){
       cout<<a[i]<<"\t";
    }
}


inline void Swap(int &s,int &t){
   int temp=s;
   s=t;
   t=temp;
}

int Partition(int a[],int p,int r){
    int i=p,j=r+1;
    int x=a[p];
    while(true){
         while(a[++i]<x);
         while(a[--j]>x);
         if(i>=j){break;}
         Swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}

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

int main(){
    int a[10]={10,3,90,22,8,1,20,100,33,106};
    cout<<"排序前：\n";
    printArray(a,10);
    QuickSort(a,0,9);
    cout<<"排序后：\n";
    printArray(a,10);
}

运行结果

排序前：
10  3   90  22  8   1   20  100 33  106
排序后：
1   3   8   10  20  22  33  90  100 106