快速排序是一种非常常见但不容易懂的排序方法。
思路如下:
1、i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2、j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3、i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中
4、再重复执行2,3二步,直到i==j,将基准数填入a[i]中
也就是找一个基准数,根据基准数将数组分为左右两部分。再设一个基准数,重复操作
很难看懂?先看实例
有一个数组:
72 6 57 88 60 42 83 73 48 85
假设第一个数72为基准数,序号从0到9,那么i=0,j=9,X=72
首先我将基准数72挖掉,那么缺少a[0],需要找一个数来填补。从j=9开始往前找一个比72小的数(默认72是中间的数,a[0]肯定比72小)
那么j=8,也就是a[8]=48满足要求,那么将48填到a[0]的位置。
数组变为
48 6 57 88 60 42 83 73 ? 85
此时a[8]被挖空。i++(需要在前面找了)。
j=8,i=1,X=72
从第i位开始往后找比72大的数,那么i=3,也就是a[3]=88满足要求,将88填入a[8],数组变为
48 6 57 ? 60 42 83 73 88 85
此时a[3]被挖空。j--(需要在后面找了)。
j=7,i=3,X=72
从第j位开始往前找比72小的数,那么j=5,也就是a[5]=42满足要求,将42填入a[3],数组变为
48 6 57 42 60 ? 83 73 88 85
此时a[5]被挖空。i++(需要在前面找了)。
j=5,i=4,X=72
从第i位开始往后找比72大的数,i和j重合了,找到一个坑,a[5]=?,将72填入
48 6 57 42 60 72 83 73 88 85
这样就分为了两个部分,左边的数比72小,右边的数比72大。
将左右两部分重复上面的操作即可得到排序的数组。
代码实现如下:
static void QuickSort(List<int> list,int l,int r) { if (l < r) { //取临时值,防止l和r改变 //基准值不一定是list[0] int i = l; int j = r; int x = list[l]; //整体判断,只要仍小于就始终执行 while (i < j) { //从右边找到比基准值小的数 while (i < j && list[j] >= x) j--; //此时j为所求,并i++ if (i < j) { list[i] = list[j]; i++; } //从左边找到比基准值大的数 while (i < j && list[i] < x) i++; //此时j为所求,并j-- if (i < j) { list[j] = list[i]; j--; } } //最后i=j,将基准填入 list[i] = x; //还未结束,递归调用 QuickSort(list, l, i-1); QuickSort(list, i + 1, r); } }
控制台输出如下:
以上为每次进行快速排序的结果,最终达到排序的目的。