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

八旬老人废寝忘食,只为学会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 应用容器化
原文地址:梁桂钊的博客 博客地址:http://blog.720ui.com 欢迎关注公众号:「服务端思维」。一群同频者,一起成长,一起精进,打破认知的局限性。 Google 在 2018 年下旬开源了一款新的 Java 工具 Jib,可以轻松地将 Java 应用程序容器化。
1243 0
Java 的快速 JSON 解析器/生成器fastjson
Fastjson 是一个 Java 库,可用于将 Java 对象转换为它们的 JSON 表示。它还可用于将 JSON 字符串转换为等效的 Java 对象。Fastjson 可以处理任意 Java 对象,包括您没有源代码的预先存在的对象。
141 0
xml与java对象的快速互转
做流程图的项目时,新的流程定义为xml的,需要对xml与java对象进行互转 查了一下activiti的转换xml方式,发现转换太麻烦了,需要一步步的解析xml 后面发现直接用jaxb就可以很快实现互转,而且现在这个jaxb在jdk内,不需要引入外部的解析xml的包 具体如下: 一.
1062 0
7天零基础快速入门Java编程 | 开发者速成班
如果你还是Java小白,那么福利来啦!开发者社区整理了7篇Java入门教程,一日一课,一周开启你的编程之旅!
10940 0
手写快速排序(JavaScript)
手写快速排序(JavaScript)
27 0
java 算法基础之二快速排序算法
java 算法基础之二快速排序算法
1975 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
19691 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的,?mysql的 3306,?mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建. ? have?fun! ?将编程看作是一门艺术,而不单单是个技术。
17985 0
+关注
负债程序猿
知道的越多,不知道的越多
119
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载
http://www.vxiaotou.com