快速排序C++实现

快速排序是对冒泡排序的一种改进，冒泡排序一次只能移动一次，而快速排序一次就能将大于轴值的数移动到轴值的后面（升序），减少了移动的次数

#include<iostream> using namespace std; int oneSort(int a[],int x,int y); //一次划分函数 void qSort(int a[],int,int); //快速排序函数 int main(){ int a[]={3,6,5,9,7,1,8,2,4}; //int a[]={1,2,3,4,5,6,7,8,9}; int n=sizeof(a)/sizeof(int); qSort(a,0,n-1); for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0; } int oneSort(int a[],int x,int y){ int i=x; //i从左往右走 int j=y; //j从右往左走 int tmp=a[x]; //把第一个数当轴值，保存到tmp中 while(i<j){ //当i<j时，循环 while(tmp<a[j]&&i<j) //如果右边的值比轴值大就循环 j--; if(i<j){ a[i]=a[j]; //此时tmp>a[j]，将a[j]的值赋值给a[i],然后i++ i++; } while(a[i]<tmp&&i<j) //如果左边的值比轴值小就循环 i++; if(i<j){ a[j]=a[i]; //此时tmp<a[i],将a[i]的值赋值给 //a[j],然后j-- j--; } } a[i]=tmp; //最后i，j的位置的值就是轴值所在的值tmp，此时， //i左边的值都比tmp小，i右边的值都比tmp大， //完成一次划分 return i; //返回i的位置，然后对i左边和右边递归进行划分 } void qSort(int a[],int x,int y){ if(x<y){ int k=oneSort(a,x,y); //取得一次划分的轴值，再对轴 //值左右边进行递归划分 qSort(a,x,k-1); qSort(a,k+1,y); } }