今天下午的时候学了查找和排序的题目，由于比较简单，所以早早的完成了，但是我感觉自己对快排算法的理解并不是很透彻，虽然在用的时候，能很快的敲出来。所有在这里从新对快排学习一遍。
我先敲了一下快排的算法
#include<iostream> using namespace std; void qsort(int a[],int l,int r) //a[]代表无序数组，l代表左边界，r代表右边界 { int x = a[l],i = l,j = r; //i，j一开始分别指向左右边界，并将做边界的数值记录下来 if(l >= r) return ; //当区间只有一个数值时，本身就是有序的，此刻就不需要递归了 while(i != j) { while(i < j && a[j] >= x) j--; //从右边界开始判断，如果大于x值，j往左移，如果遇见小于的话，跳出循环 a[i] = a[j]; //跳出循环后，将后面小于x的值，移动到前面去 while(i < j && a[i] <= x) i++; a[j] = a[i]; } a[i] = x; //当i=j时，将x的值赋值到a[i]上去，这时比x小的都在左边，比x大的都在右边 qsort(a,l,i-1); //从a[i]，分开，递归判断左边的数值和右边的数值 qsort(a,i+1,r); } int main(){ int a[100]; int n; cin >> n; for(int i = 0;i < n;i++){ cin >> a[i]; } qsort(a,0,n-1); for(int i = 0;i < n;i++){ cout << a[i] << " "; } return 0; }
我在代码后面加了一些注释，方便对照相应的代码。
快排算法说白了，就是开始将一组数看做一个大区间，每次从区间的左边取开始的数值记录下来，然后将比x大的数移动到它的右边，比x小的数移动到它的左边，（注意，因为一开始你是从左边记录的x数值的，所以应从后面先判断，就是将while(i < j && a[j] >= x) j--;放在while(i < j && a[i] <= x) i++; 的前面，否则一开始的时候，你会覆盖最后一个数值。）移动完成后，相当于以x值为界，将数组分为两个区间，这时利用递归开始判断左右区间，和上面的思想一样。如果这个过程中，区间只有一个数值，就不需要递归了
