A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 王春晓 中级黑马   /  2013-5-13 10:33  /  1741 人查看  /  3 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 王春晓 于 2013-5-13 20:46 编辑

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循环的运行过程是什么样的?

评分

参与人数 1技术分 +1 收起 理由
Sword + 1

查看全部评分

3 个回复

倒序浏览
如果 arr[j]>temp, 即arr[j]现在的位置,是它应该在的位置。所以j-- ,直接判断下一个位置的数是否满足这个条件。如果不满足条件,则交换两数的位置。那么交换后此数的位置也在它应该在的位置。
while(i<j && arr[i]<temp){
                                    i++;
                        } 这个的话,同理。
然后 while循环里的 i < j是硬性条件。 当 i == j时, 此时那个temp应该存放的位置 就是 i == j这个 位置。
回复 使用道具 举报
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);// 打印快排后的数组。
        }
}
这个是我以前写的,注释挺全的,希望能帮到楼主。。。

评分

参与人数 1技术分 +1 收起 理由
殇_心。 + 1

查看全部评分

回复 使用道具 举报
首先你要理解&& (短路,与),比如,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的遍历过程相反

                                    
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马