快速排序算法详细图解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)


相关推荐

  • 微信小程序-和后台交互

    微信小程序-和后台交互微信小程序-和后台交互

  • java struts2 漏洞_Struts2漏洞简述

    java struts2 漏洞_Struts2漏洞简述S2-005漏洞S2-005是由于官方在修补S2-003不全面导致绕过补丁造成的。我们都知道访问Ognl的上下文对象必须要使用#符号,S2-003对#号进行过滤,但是没有考虑到unicode编码情况,导致\u0023或者8进制\43绕过。S2-005则是绕过官方的安全配置(禁止静态方法调用和类方法执行),再次造成漏洞。Payload如下:http://www.xxxx.com/aaa.action…

  • 万年历月份算法(最实用的万年历)

    中秋节到啦,送给大家一个《万年星期历公式》  该公式是根据公历的基本性质编制的,年份不限,准确率为100%, 公式如下: (年+年/4+年/400-年/100+月日天数-1)/7=XX……余星期几。 其中: (年+年/4+年/400-年/100)/7=XX……余数为该年1月1日星期数。 注:分数商均取整数; 月日天数:平年——润年 一月为:0+日数,0+日数, 二月为:3+日数,…

  • 基于LSTM的股票预测模型_python实现_超详细

    基于LSTM的股票预测模型_python实现_超详细文章目录一、背景二、主要技术介绍1、RNN模型2、LSTM模型3、控制门工作原理四、代码实现五、案例分析六、参数设置七、结论一、背景近年来,股票预测还处于一个很热门的阶段,因为股票市场的波动十分巨大,随时可能因为一些新的政策或者其他原因,进行大幅度的波动,导致自然人股民很难对股票进行投资盈利。因此本文想利用现有的模型与算法,对股票价格进行预测,从而使自然人股民可以自己对股票进行预测。理论上,………

  • Java爬虫系列一:写在开始前[通俗易懂]

    最近在研究Java爬虫,小有收获,打算一边学一边跟大家分享下,在干货开始前想先跟大家啰嗦几句。一、首先说下为什么要研究Java爬虫Python已经火了很久了,它功能强大,其中很擅长的一个就是写爬虫

  • 指针基础知识笔记

    指针基础知识笔记指针式C语言中的重要概念,也是C语言的一个重要特色,C的精华所在吧。1.指针-内存地址;2.指针变量:定义为,存放指向存储什么数据类型的地址的变量;它的值就是地址; 定义指针变量: 类型名*指针变量名;//类型名就是指向地址上的数据的类型; 例如: char*pa; int*pb;(注意的是):避免访问未初始化的指针; 3.取地址运算符:&获取某个变量的地址;//初始化指针; 例如:(chara;intb); char

发表回复

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

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