**快速排序法(quick sort)**的基本思想是:通过一趟排序将要排序的记录分割成独立的两部分,其中一部分的所有记录关键码比另外一部分的记录关键码都要小,然后再按此方法对这两部分数据分别进行递归快速排序,从而使序列成为有序序列。
设有A[1]一A[n]的n个数据,选取第一个数据作为关键数据,然后将所有比它小的数据都放到它前面,所有比它大的数据都放到它后面,称为一趟快速排序。其算法是:
①设置两个变量i、j,排序开始的时候i=左边界,j=右边界,令关键数据s=A[i]。
②从 i 开始向前搜索,直到找到小于s的数。
③从 j 开始向前搜索,直到找到小于s的数。
④如果i≤j,则交换A [ i ]和A [ j ]。
⑤重复第②~④步,直到i≥j;将关键数据与A[j]交换。
#include <iostream>
#include <stdlib.h>
#include<ctime>
using namespace std;
#define N 10
void Quicksort(int A[],int n,int left,int right){//快速排序，n为数组大小，left为左边界，right为右边界
int i,j,t;
if(left < right){ //一趟快速排序
i = left;
j = right+1;
while(1){
while(++i<n && A[++i]<A[left]);//i向后搜索<升序>降序
while(j-1>-1 && A[--j]>A[left]);//J向前搜索，>升序，<降序
if(i>=j)break;
t=A[i],A[i]=A[j],A[j]=t; //交换
}
t=A[left],A[left]=A[j],A[j]=t; //交换
Quicksort(A,n,left,j-1);//左半部分递归
Quicksort(A,n,j+1,right);//右半部份递归
}
}
int main(){
int A[N],i;
srand((unsigned int )time(0));
cout<<"随机生成的数组为："<<endl;;
for(i=0;i<N;i++){//随机生成一个10个的100以内的数字作为数组A
A[i]=rand()% 100;
cout<<A[i]<<" ";
}
cout<<endl;
cout<<"快速排序结果为:"<<endl;
Quicksort(A,N,0,N-1);//快速排序函数
for(i=0;i<N;i++)
cout<<A[i]<<" "; //输出
return 0;
}
结果如图：
