//快速排序 from aha #include<iostream> using namespace std; int a[101],n; void print(int a[],int n) { for(int i=1;i<=n;i++) { cout<<a[i]<<" "; } cout<<endl; } void quicksort(int left,int right) { int l,r; l=left,r=right; if(l>r) //呼应后面的判断,当只剩一个数字的时候会有l>r //一个数字的时候,这个数字是已经归位了的,所以可以直接退出了。 { return; } int temp; temp=a[left]; //基准数 //从小到大情况下的目的:把基准数复原且将小于基准数的数放在基准数左边 //大于基准数的数放在基准数的右边 while(l!=r) //循环的条件是两个哨兵没有相遇 //当两个哨兵相遇了就跳出循环,不再交换值。 { //注意这里的顺序,是先让右边的开始找,右边的找完才能左边的找 //注意基准数是取右边的那个数字 while(a[r]>=temp&&r>l) //r>l没有等号的原因:目的就是让两个哨兵相遇 //虽然循环条件是r>l,但是如果没有找到可以交换的数,那么就会有r=l; //下面的循环l<r,同理 { r--; } while(a[l]<=temp&&l<r) //注意a[l]<=temp,有等于号,一开始a[l]是等于temp的 //如果不写这个等于号 就永远不会进入这个循环 // 注意这个循环和上一个while循环都有要求<= >=有等于号 { l++; } if(l<r) //如果两个哨兵没有相遇,就交换两个值。 { int t=a[l]; a[l]=a[r],a[r]=t; } } //因为前面会让l!=r的情况一直循环,所以能运行到这里的都是l==r的。 //这里使基准数归位,就是让基准数和r==l的那个位置交换值。 a[left]=a[l]; a[l]=temp; //基准值的两边分别递归 quicksort //不用排序归位的基准值了,因为他已经归位了 //所以就newright=l-1或者r-1,现在是l==r的。 //要注意:当最后递归到只剩下一个数字的时候,就应该可以退出了。 //所以此时是l==r的,所以将会有 l-1<left,r+1>right的情况 //呼应quicksort开头那个if(l<r)的时候return. quicksort(left,l-1); quicksort(l+1,right); return; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } quicksort(1,n); //left=1,right=n; print(a,n); return 0; }
原文:https://www.cnblogs.com/xuwanwei/p/10878648.html