八旬老人废寝忘食,只为学会Java快速排序,今天他终于学会了

小学生才玩儿冒泡,猛男都玩儿快排

在常见的排序算法中,快速排序在性能上有绝对的优势,家里有条件的建议都把原理搞懂;

老规矩,先看demo

public class QuickSort {

    public static int[] sort(int[] arr, int left, int right) {

        //left和right为数组边界的下标,如果left >= right,则直接返回,无需排序
        if (left >= right) return arr;

        //定义两个游标i和j,我们将通过i和j确定出参照数的下标
        //注意将i、j与left、right区分,i、j是游标,而left、right是扫描边界,边界是进入方法后确定不变的,而i和j会一直变化
        int i = left, j = right, temp = arr[left];

        //开始从两端往中间扫描,确认参照数下标,所有操作都是基于i<j
        while (i < j) {
            //先从右往左扫描
            //如果j处的元素大于参照数,则j-1,继续往数组中部扫描
            while (arr[j] >= temp && i < j) j--;
            //如果j处的元素小于参照数,则将j处的元素赋值给i处,这里的if判断其实可以不写,写出来只是为了方便大家理解
            if (arr[j] < temp && i < j) arr[i] = arr[j];

            //再从左往右扫描
            //如果i处的元素小于参照数,则i+1,继续往数组中部扫描
            while (arr[i] <= temp && i < j) i++;
            //如果i处的元素大于参照数,则将i处的元素赋值给j处,这里的if判断其实可以不写,写出来只是为了方便大家理解
            if (arr[i] > temp && i < j) arr[j] = arr[i];
            //记住我们扫描的目的===> 为了找出参照数在数组中正确的下标,这个下标左边的元素都比参照数小,右边的都比它大
            //记住我们扫描的目的===> 为了找出参照数在数组中正确的下标,这个下标左边的元素都比参照数小,右边的都比它大
            //记住我们扫描的目的===> 为了找出参照数在数组中正确的下标,这个下标左边的元素都比参照数小,右边的都比它大
        }
        //这里也可以换成arr[j] = temp,因为经过扫描后,i==j
        arr[i] = temp;
        //这是快速排序的精髓所在,分治递归,将数组分成两半,前半部分是0到i-1
        sort(arr, left, i - 1);
        //后半部分是i+1到数组长度-1
        sort(arr, i + 1, right);
        return arr;
    }

    public static void main(String[] args) {
        //定义一个无序数组
        int[] arr = {5, 12, 3, 18, 19, 55, 0, 28, -1, 33};
        System.out.print("原数组:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        //left和right代表数组两端边界的下标
        sort(arr, 0, arr.length - 1);
        System.out.print("\n排序后:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

运行结果

原数组:5 12 3 18 19 55 0 28 -1 33 
排序后:-1 0 3 5 12 18 19 28 33 55 

原理:


给定一个数组arr

在数组中选择一个数字作为参照数,这个数字一般就是数组的第一个元素(最理想的参照数是排序好后的数组中的中位数,但我们不知道是谁,所以就直接用数组内第一个元素)

重点来了,然后定义两个游标 i 和 j ,因为我们要从数组两端往中间扫描,所以首次扫描时i等于left等于0,j等于right等于arr.length-1

分别从数组两端往中间扫描,一般先从右边开始,直到找到一个正确的参照数下标,什么样的下标才叫正确?把参照数放到这个下标后,参照数左边的数字都比参照数小,右边的数字都比参照数大

第一次扫描完成后,会进行递归扫描,递归扫描会把原数组以参照数隔开,切分成两个数组,这两个数组再进行上述操作,最终实现数组元素排序

我知道你哪儿不懂


一定要分清left、right和i、j的关系,left和right是确定数组边界,就是数组中left到right之间的元素才会进行排序,比如如果你输入的left=1,right=arr.length-2,那么数组中首尾两个元素是不参与排序的


自己看吧:

sort(arr, 1, arr.length - 2);//首尾两个元素不参与排序

运行结果

原数组:5 12 3 18 19 55 0 28 -1 33

排序后:5 -1 0 3 12 18 19 28 55 33

再来一个加深理解:

sort(arr, 5, arr.length - 1);//前5个元素不参与排序

运行结果

原数组:5 12 3 18 19 55 0 28 -1 33

排序后:5 12 3 18 19 -1 0 28 33 55


ok我话说完,skr~

上一篇:Linux自动备份压缩MySQL数据库的实用方法


下一篇:Gradle学习系列之一——Gradle快速入门(转)