一、快速排序：
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
- 1．先从数列中取出一个数作为基准数。（第一个数）
- 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 3．再对左右区间重复第二步，直到各区间只有一个数。
二、思路分析：
1、两个主要功能函数：int find（int *b，int left，int right）与 void quicksort（int *b，int left，int right）
2、find（）功能：将传入的区间首值放至正确位置（其左边值皆小于其，其右边值皆大于其）
3、quicksort（）函数功能：调用find将该区间首值放至正确位置，再对已放至正确位置的左边区间与右边区间快排。
4、find（）函数详解：flag表示的从left+1位置至flag位置存的数据皆小于b[left]。
（1）、 i是循环遍历的，但flag只会因if（b[i]<num）才执行+1，所以随着i的移动，flag可能没有移动。
（2）、若出现了b[i]<num的情况，且i与flag不相等（说明中间有大于等于num的值，导致flag没有移动），就需要把这个小于num的b[i]，与大于等于num的b[flag+1]交换位置。来保证实现“ 从left+1位置至flag位置存的数据皆小于b[left]。”
三、代码如下：
//快速排序分治法 #include <iostream> using namespace std; #define N 1000 int n=5; int a[N]; int find(int *b,int left,int right){//将首位数放至正确位置：其左边值皆小于它，右边值皆大于它 if(left<right){ int flag=left; int num=b[left]; for(int i=left+1;i<=right;i++){//从left+1位置开始比较 if(b[i]<num){ flag++;//移动flag，自left+1至flag（+1操作后的）的值皆小于b[left] if(flag!=i){//交换b[i]与b[flag] int change=b[flag]; b[flag]=b[i]; b[i]=change; } } } //上述循环执行完毕，flag为此段首值在此段的正确位置（flag左边值皆小于其，flag右边值皆大于其） int change=b[flag]; b[flag]=b[left]; b[left]=change; return flag; } } void quicksort(int *b,int left,int right){//快排且分治 if(left<right){ int x=find(b,left,right); quicksort(b,left,x-1);//对已放至正确位置的x值左边快排 quicksort(b,x+1,right);//对已放至正确位置的x值右边快排 } } void print(){//打印结果 for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } } int main(){ for(int i=1;i<=n;i++){ cin>>a[i]; } //cout<<find(a,1,5)<<endl; quicksort(a,1,5); print(); return 0; }
四、示例输入输出：
1、输入
522 2401 123 100 2
2、输出
2 100 123 522 2401
