问题描述
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
（问题描述摘自百度百科）
闲话
在实际的算法编程中，快排使用的是algorithm库中的sort()函数（可以了解下，很简单也很好用），但是自己从来没有实现过这个排序算法…
Code
#include<bits/stdc++.h>
#define N 100
using namespace std;
int a[N]={6, 7, 5, 2, 5, 8, 3, 5, 1};
int n=9;
int partition(int l, int r){
int flag=a[l];
while(l<r){
while(l<r&&a[r]>=flag)
r--;
if(l<r){
swap(a[r], a[l]);
}
while(l<r&&a[l]<=flag)
l++;
if(l<r){
swap(a[r], a[l]);
}
}
a[l]=flag;
return l;
}
void quick_sort(int l, int r){
if(l<r){
int m=partition(l, r);
quick_sort(l, m-1);
quick_sort(m+1, r);
}
}
int main()
{
quick_sort(0, n-1);
for(int i=0;i<n;i++)
cout<<a[i];
getchar();
return 0;
}
