快速排序算法详细图解JAVA_实现快速排序

快速排序算法详细图解JAVA_实现快速排序高快省的排序算法有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。假设我们现在对“61279345108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

高快省的排序算法

有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列:

3 1 2 5 4 6 9 7 10 8

在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。想一想,你有办法可以做到这点吗?

排序算法显神威

方法其实很简单:分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从找一个小于6的数,再从找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即=10),指向数字。

这里写图片描述
首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。哨兵j一步一步地向左挪动(即j–),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。
这里写图片描述
这里写图片描述
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下:

6 1 2 5 9 3 4 7 10 8
这里写图片描述
这里写图片描述
到此,第一次交换结束。接下来开始哨兵j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下:

6 1 2 5 4 3 9 7 10 8

第二次交换结束,“探测”继续。哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下:

3 1 2 5 4 6 9 7 10 8

这里写图片描述
这里写图片描述
这里写图片描述

到此第一轮“探测”真正结束。此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程,其实哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到i和j碰头为止。

OK,解释完毕。现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3 1 2 5 4”,右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧

如果你模拟的没有错,调整完毕之后的序列的顺序应该是:

2 1 3 5 4

OK,现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,到此2已经归位。序列“1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到序列是“1 2”。序列“5 4”的处理也仿照此方法,最后得到的序列如下:

1 2 3 4 5 6 9 7 10 8

对于序列“9 7 10 8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终将会得到这样的序列,如下

1 2 3 4 5 6 7 8 9 10

到此,排序完全结束。细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。
这里写图片描述

这是为什么呢?

快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想,到时候再聊。先上代码,如下

代码实现:

public class QuickSort {

#arr 需要排序的数组
#low 开始时最左边的索引=0
#high 开始时最右边的索引=arr.length-1
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;#左边哨兵的索引
        j=high;#右边哨兵的索引
        //temp就是基准位
        temp = arr[low];#以最左边为 基准位

        while (i<j) {
            //先看右边,依次往左递减
            #先从右往左找一个小于 基准位的数
            #当右边的哨兵位置所在的数>基准位的数 时
            #继续从右往左找(同时 j 索引-1)
            #找到后会跳出 while循环
            while (temp<=arr[j]&&i<j) {
                j--;
            }

            //再看左边,依次往右递增
            #步骤和上面类似
            while (temp>=arr[i]&&i<j) {
                i++;
            }

            //如果满足条件则交换
            if (i<j) {

#z、y 都是临时参数,用于存放 左右哨兵 所在位置的数据
                 z = arr[i];
                 y = arr[j];

                 # 左右哨兵 交换数据(互相持有对方的数据)
                 arr[i] = y;
                 arr[j] = z;

            }

        }

#这时 跳出了 “while (i<j) {}” 循环
#说明 i=j 左右在同一位置
        //最后将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];#或 arr[low] = arr[j];
         arr[i] = temp;#或 arr[j] = temp;


#i=j
#这时 左半数组<(i或j所在索引的数)<右半数组
#也就是说(i或j所在索引的数)已经确定排序位置, 所以就不用再排序了,
# 只要用相同的方法 分别处理 左右数组就可以了

        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }


    public static void main(String[] args){
        int[] arr = {
  
  10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
输出为
1
2
2
3
4
4
7
7
8
9
10
19
62

 
 
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

原文地址:http://developer.51cto.com/art/201403/430986.htm

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/179044.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • web渗透测试—-33、HttpOnly[通俗易懂]

    web渗透测试—-33、HttpOnly[通俗易懂]HttpOnly是微软公司的InternetExplorer6SP1引入的一项新特性。这个特性为cookie提供了一个新属性,用以阻止客户端脚本访问Cookie,至今已经称为一个标准,几乎所有的浏览器都会支持HttpOnly。下面示例显示了HTTP响应标头中HttpOnly使用的语法:Set-Cookie:<name>=<value>[;<Max-Age>=<age>]`[;expires=<date>][;domain=&lt

  • int32.parse什么意思_integer.parseint和valueof

    int32.parse什么意思_integer.parseint和valueofnt32.Parse(string)Int32.Parse(stringstr)methodconvertsthestringrepresentationofanumbertoits32-bitsignedintegerequivalent.Ittakesastringandtriestoextractanintegerfromi

  • FileProvider 的使用(Failed to find configured root that contains/storage/emulated/0/DCIM/ )

    FileProvider 的使用(Failed to find configured root that contains/storage/emulated/0/DCIM/ )首先扯点别的:今天不上班,在家里和剑宗喝了点酒,和同学聊了会天,也是挺开心,现在学会习。以前调用系统相机拍照的时候,流程是这样的privatevoidtakePhoto(){IntenttakePictureIntent=newIntent(MediaStore.ACTION_IMAGE_CAPTURE);if(takePictureIntent

    2022年10月29日
  • a3如何打印双面小册子_A3折叠成为小册子

    a3如何打印双面小册子_A3折叠成为小册子程序功能:A3PDF_A4PDF问题:A3幅面的双面打印的在中间用骑马钉装订成小册子,拆开中间装订的订书钉由复印机一次性扫描成PDF文件。阅读不方便:页码错乱,A3幅面,左右两页。本程序将扫描的A3幅面的PDF文件转换成理顺页码单面的A4幅面的PDF文件。编程思路:PDF文件==>页面png(图片文件)(用到:pdf2image,oppler中的pdftommp.exe)==>图片文件A3大小切分成…

  • 2021年各行业NPS基准分数一览[通俗易懂]

    2021年各行业NPS基准分数一览[通俗易懂]每每谈及NPS,总会有客户问我们:NPS分数达到多少才算得上好?这个问题没有统一的标准答案。因为NPS分数没有绝对的高低之分,不同行业之间标准不一。比如,根据TemkinGroup——知名的体验研究机构于2018年的调查,快餐行业的NPS均分是26,而医疗保健的NPS均分是19。因此,企业要想判断自己的NPS分数是好是坏,最需要了解的是所处行业的整体NPS水平。为了能够帮助大家快速了解自己在行业内的NPS地位,我们特别整理了分别处于ToB和ToC领域共14个行业的最新NPS基准分..

  • 国内 Go 代理汇总

    国内 Go 代理汇总golang国内的代理总是一个很头疼的问题,这里汇总一下国内几个可用的代理,到时候有些包下不下来就换几个代理多试试代理1:阿里云GoModule代理传送门:https://mirrors.aliyun.com/goproxy/简介gomodule公共代理仓库,代理并缓存go模块。你可以利用该代理来避免DNS污染导致的模块拉取缓慢或失败的问题,加速你的构建使用帮助使用go1…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号