八旬老人废寝忘食,只为学会Java快速排序,今天他终于学会了-阿里云开发者社区

开发者社区> 负债程序猿> 正文

八旬老人废寝忘食,只为学会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~

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《排序算法》——快速排序(Java)
十大算法之快速排序: 方法其实很简单:分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。
744 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
8112 0
Java快速排序的调试
Created by Wang, Jerry, last modified on Feb 06, 2016
65 0
java 算法基础之二快速排序算法
java 算法基础之二快速排序算法
1940 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
10525 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
9890 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11362 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
6497 0
+关注
负债程序猿
知道的越多,不知道的越多
118
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载