黑马程序员技术交流社区

标题: 快速排序 [打印本页]

---

作者: 王春晓    时间: 2013-5-13 10:33
标题: 快速排序


public class QuickSort {
    public static void main(String[] args){
            //给定数组
            int[] arr = {2,14,3,6,5,10,1,2};
            //将数组快速排序
            Sort(arr);
            //打印排序结果
            printArr(arr);
    }
    public static void Sort(int[] arr){
            int start = 0;
            int end = arr.length-1;//数组的最大索引位置
            quickSort(arr,start,end);//调用关键函数
    }
    public static void quickSort(int[] arr,int left,int right){
            int i = left;//记录区间起始位置
            int j = right;//记录区间末尾位置
            //排序出口是left==right
            if (left < right) {
                    int temp = arr[left];//设置临时变量，记录参照点
                    while(i!=j){
                            //固定i，从右开始寻找小于参照的元素
                            while(i<j && arr[j]>temp){
                                    j--;
                            }
                            //找到后将其放在i的位置
                            if (i<j) {
                                    arr = arr[j];
                                    i++;
                            }
                            //此时j固定，从做开始寻找大于参照的的元素
                            while(i<j && arr<temp){
                                    i++;
                            }
                            //找到后将其放在j的位置
                            if (i<j) {
                                    arr[j] = arr;
                                    j--;
                            }                        
                    }
                    //当i==j时说明该区间的分配结束，将参照放置在其最终位置，i或j
                    arr = temp;
                    //递归调用排序左区间
                    quickSort(arr,left,i-1);
                    //递归调用排序右区间
                    quickSort(arr,i+1,right);
            }
    }
    //打印数组
    public static void printArr(int[] arr){
            for (Object a : arr)
                    System.out.print(a);
    }
}

快速排序中，那个while循环的运行过程是什么样的？

---

作者: 吴文彬    时间: 2013-5-13 11:13
如果 arr[j]>temp， 即arr[j]现在的位置，是它应该在的位置。所以j-- ，直接判断下一个位置的数是否满足这个条件。如果不满足条件，则交换两数的位置。那么交换后此数的位置也在它应该在的位置。
while(i<j && arr[i]<temp){
                                    i++;
                        } 这个的话，同理。
然后 while循环里的 i < j是硬性条件。 当 i == j时， 此时那个temp应该存放的位置 就是 i == j这个 位置。

---

作者: 吴文彬    时间: 2013-5-13 12:36
package com.itheima;


public class Test3 {

        public static void println(int array[], int len) {// 打印数组。。

                for (int i = 0; i < len; i++) {
                        System.out.print(array[i] + " ");
                }

                System.out.println();
        }

        public static void swap(int array[], int i, int j) {// 交换array[i],array[j]的值。
                int temp = array[i];

                array[i] = array[j];

                array[j] = temp;
        }

        public static int partition(int array[], int low, int high) {// 划分过程的方法，low为最低端下标，high为最高端下标
                // 基准点，即把这个数放到它应该在的位置。
                // 什么是应该在的问题？即把它左边的数都小于等于它，右边的数都大于等于它。
                int pv = array[low];// 用最低端的元素初始化基准。

                while (low < high) {// 结束条件为low 和 high 交汇的时候。
                        while ((low < high) && (array[high] >= pv)) {// 如果array[high]比基准点大high--,否则不满足退出循环。
                                high--;// 为什么high--呢，因为该数大于等于基准点，的确应该在基准点左边。没错，所以可以high--，查看上一个数，是否也同样满足。
                        }

                        swap(array, low, high);// 不满足,即array[high]位置的数小于基准点的数，则交换两元素位置。
                        // 为什么交换呢，因为基准点的右边只允许放比它大的数，比它小的数，当然放基准点的左边了。
                        while ((low < high) && (array[low] <= pv)) {// 如果array[low]比基准点小high++,否则不满足退出循环。
                                low++;// 为什么high++呢，因为该数小于等于基准点，应该在基准点左边，没错。所以可以high++，查看上一个数，是否也同样满足。
                        }

                        swap(array, low, high);// 否则交换array[low],array[high]的值。
                        // 为什么交换呢，因为基准点的左边只允许放比它小的数，比它大的数，当然放基准点的右边了。
                }

                return low;// 返回划分好的位置，即它的左边的数都比它小，右边都比它大。
        }

        public static void QSort(int array[], int low, int high) {
                if (low < high) {
                        int pivot = partition(array, low, high);// 划分array数组的low~high范围，划分后，基准点pivot左边数的都比array[len]小，基准点pivot右边的数都比大。此时array[pivot]在它应该在位置.
                        QSort(array, low, pivot - 1);// 递归快排pivot左边的数。
                        QSort(array, pivot + 1, high);// 递归快排pivot右边的数。
                }
        }

        public static void QuickSort(int array[], int len) {
                QSort(array, 0, len - 1);
        }

        public static void main(String[] args) {
                int array[] = { 1, 5, 100, 22, 21, 25, 49, 25, 16, 8 };// 定义并初始化，数组。
                int len = 10;// 数组长度.

                println(array, len);// 打印排序前的数组。
                QuickSort(array, len);// 快排
                println(array, len);// 打印快排后的数组。
        }
}
这个是我以前写的，注释挺全的，希望能帮到楼主。。。

---

作者: 王林涛    时间: 2013-5-13 12:45
首先你要理解&& （短路，与），比如，int a = 2; a>3 && a<6;   如果左侧为假，则不运算，直接为假。如果左侧为真，再继续运算右侧。
当右→左，固定I 从右开始寻找小于参照的元素
while(i<j && arr[j]>temp)，当保证 i<j为真是，条件满足，while循环继续，既然是从右→左寻找小于参照数的变量，那么while的遍历运动过程，当然是开始是从右到左，找到那个小于参照的数值后，赋值给i，而int i = left， if (left < right)     {int temp = arr[left];所以从右→左最后的排序为从左往右递增
当左→右，while的遍历过程相反

                                    

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2