快速排序是分治算法的典型應用，基本策略：
> 將數組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
~~~
