快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
算法的思路很清晰，但是如果在区间划分过程中边界值没有处理好，也是很容易出现bug的。下面给出两种比较清晰的思维来指导区间划分代码的编写。
第一种思维即所谓的挖坑法思维，下面通过分析一个实例来分析一下挖坑法的过程：
以一个数组作为示例，取区间第一个数为基准数。
 初始时，left = 0; right= 9; X = a[left] = 72
由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从right开始向前找一个<=X的数。显然,right=8时，符合条件，将a[8]挖出再填到上一个坑a[left]中。 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从left开始向后找一个大于X的数，当left=3，符合条件，将a[3]挖出再填到上一个坑a[right] 中;
数组变为： 
再重复上面的步骤，最终数组将变成如下形式：
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。将X填入a[5]的坑中，数据变为：
因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a中。
照此分区方法，快速排序java代码如下：
- public class Partition {
-
- /**
- * 基于base划分，小的在左，大的在右， 不要求整个序列有序
- *
- * @param ary
- * @param base
- */
- static void sort(int[] ary, int base) {
- int left = 0;
- int right = ary.length - 1;
-
- int leftpoint = left, rightpoint = right;
-
- while (true) {
- // 分成左右两边同时进行比较，一边从左向右，一边从右向左，
- while (leftpoint < right && ary[leftpoint++] < base); //leftpoint大于right或ary[leftpoint]>base停止循环
-
- while (rightpoint >= left && ary[rightpoint--] > base); //反之
- System.out.println("左边需要交换的索引:" + (leftpoint-1));
- System.out.println("右边需要交换的索引:"+ (rightpoint+1));
- //上面拿到了不符合条件的两个索引，即需要交换的两个索引
- if (leftpoint - 1 < rightpoint + 1) {//需要交换
- swap(ary, leftpoint - 1, rightpoint + 1);
- Util.printArray(ary);
- leftpoint = left;
- rightpoint = right;
- } else {
- break;
- }
- }
- }
-
-
- private static void swap(int[] ary, int a, int b) {
- int temp = ary[a];
- ary[a] = ary[b];
- ary[b] = temp;
- }
-
- public static void main(String[] args) {
- int[] ary = Util.generateIntArray(10);
- System.out.println("原序列：");
- Util.printArray(ary);
- sort(ary, 5);
- System.out.println("排序后：");
- Util.printArray(ary);
- }
- }
结果：
- 原序列：
- [2, 8, 4, 3, 7, 5, 1, 9, 0, 6]
- 左边需要交换的索引:1
- 右边需要交换的索引:8
- [2, 0, 4, 3, 7, 5, 1, 9, 8, 6]
- 左边需要交换的索引:4
- 右边需要交换的索引:6
- [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
- 左边需要交换的索引:5
- 右边需要交换的索引:5
- 排序后：
- [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
区间划分的的另一种指导思维:
将数组的第一个元素作为区间划分值，从第二个元素开始分区，直到形成如图所示的结果，
然后交换l 
如此，可以如下编写快速排序代码： - public void qSort(int array[],int left,int right)
- {
- if(left < right){
-
- int key = array[left];
-
- int high = right;
-
- int low = left+1;
-
- while(true){
-
- while(low <= high && array[low] <= key) low++;
-
- while(low <= high && array[high] >= key) high--;
-
- if(low > high)
- break;
-
- swap(array,low,high);
- }
- swap(array,left,high);
-
- printArray(array);
-
- qSort(array,left,high-1);
-
- qSort(array,high+1,right);
- }
- }
|
