快速排序
最后更新于：2022-04-01 15:56:31
快速排序是分治算法的典型应用，基本策略：
> 将数组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
~~~