java实现快速排序图解_快速排序图文详解

java实现快速排序图解_快速排序图文详解快速排序快速排序法介绍图解代码理解快速排序法介绍快速排序(QuickSort)是对冒泡排序的一种改进,基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。图解代码理解publicclassQuickSort{//从小到大排序publicvoidquickSort(intleft,intright,

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

Jetbrains全系列IDE稳定放心使用

快速排序法介绍

  • 快速排序(QuickSort)是对冒泡排序的一种改进,基本思想是:通过一趟排序将 要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

图解

在这里插入图片描述

代码理解

public class QuickSort { 
   

    //从小到大排序
    public void quickSort(int left, int right, int[] nums){ 
   
        if(left<right){ 
   
            //将小于nums[left]的值放左边,大于nums[left]的值放右边
            int index = partition(left, right, nums);
            //对左边部分进行快速排序
            quickSort(left, index, nums);
            //对右边部分进行快速排序
            quickSort(index+1, right, nums);
        }
    }

    private int partition(int left, int right, int[] nums) { 
   
        /** * 这一部分的理解,我们可以假设此时数组排序为【2,1,3,4,5】 * 那么while (left<right&&nums[right]>base) * 会循环到right=1 * 之后数组变化如下 * nums[left]=nums[right] * 【1,1,3,4,5】 * while (left<right&&nums[left]<base)循环到left=1 * nums[right]=nums[left]相当于什么都没做 * 此时left等于right,跳出循环 * 整个过程可以简化为 * base = nums[left] * nums[left]=nums[right] * nums[right]=base */
        int base = nums[left];
        while (left<right){ 
   
            while (left<right&&nums[right]>=base){ 
   
                right--;
            }
            nums[left] = nums[right];
            while (left<right&&nums[left]<=base){ 
   
                left++;
            }
            nums[right] = nums[left];
        }
        nums[right] = base;

        return left;
    }

    public static void main(String[] args) { 
   
        int[] nums = { 
   2,3,1,5,4};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(0,nums.length-1, nums);
        for(int num:nums){ 
   
            System.out.println(num);
        }
    }
}

快速排序算法性能分析

  • 快速排序的时间性能取决于快速排序递归的深度
  • 在最优的情况下,Partition每次都划分得很均匀,如果排序n个数值,那么递归树的深度就为.log2n.+1(.x.表示不大于x的最大整数),即仅需递归log2n次,其时间复杂度为O(nlogn)
  • 在最坏的情况下,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个数值的子序列,此时需要执行n-1次递归调用且第i次划分需要经过n-i次比较才能得到第i个数值,其时间复杂度为O(n^2)

算法图

  • 口诀:堆归选基与初始序列无关 快选希堆排序不稳定

在这里插入图片描述

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

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

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

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

(0)


相关推荐

  • MVC三层架构的实现

    MVC三层架构的实现在MVC设计模式中认为,任何软件都可以分为三部分组成:1.控制程序流转的控制器Controller2.封装数据处理数据的模型Model3.负责展示数据的视图View在MVC设计思想中要求符合MVC设计思想的软件应该保证MVC这三部分相互独立,互不干扰,每一部分只负责自己擅长的部分。即某一个模块发生变化,应该尽量做到不影响其他两个模块,这样有利于后期的扩展和维护,代码也可复用…

  • HDU 4825 Xor Sum 字典树+位运算

    HDU 4825 Xor Sum 字典树+位运算

  • UML时序图简析[通俗易懂]

    UML时序图简析[通俗易懂]前言在嵌入式软件开发中,必然会遇到与其他控制板卡或者服务器通信的情况。比如,制作一个无线远程控制系统。系统分为,输入设备,云端服务器,执行设备。其中输入设备,用户可以通过设备上的触摸屏进行交互,控制或者监测远程设备云端服务器,收发终端,接收输入设备的命令,并将其转换为执行设备可识别的信号发送到可执行设备。执行设备,执行服务器发送过来的命令,并且反馈当前的设备的一些状态.简单如下图所示。一般,这样的系统需要多人共同协作完成,输入设备的开发人员负责输入设备开发,云端负责云端,执行端负责执行端

  • USB转RS485代替PC/PPI通讯电缆

    USB转RS485代替PC/PPI通讯电缆S7-200的CPU使用的是RS485,PC机有RS232口和USB口,两种接口电气规范不同,需要用中间电路转换成同一接口类型。现在常用的PC/PPI其实就是一根USB/RS485的匹配电缆。

  • python读取txt文件并画图[通俗易懂]

    1,使用python读取txt文件已知txt文件内容如下:001124394165256361234567请以第一列为x轴,第二列为y轴画图 步骤如下: 1)使用readlines读取文件 2)建立两个空列表X,Y,将第一列的数字放入X,第二列的数字放入Y中 3)以X,Y为轴画图 实现如下…

  • 图片懒加载原理及实现(java懒加载原理)

    一,前置知识1,为什么要图片懒加载懒加载是一种对网页性能优化的方式,比如当访问一个页面的时候,优先显示可视区域的图片而不是一次性加载所有图片,当需要显示时,再发送图片请求,避免打开网页时加载过多资源。当一个网站的加载图片过多时就需要懒加载的协助,页面图片多时,在首次载入时一次性加载会耗费时间长,使用懒加载可以使页面加载速度快、减轻服务器的压力、节省流量。如下图:随着滚轮滚动,底部的图片会被不断地加载,从而显示在页面上,也就是说懒加载其实就是按需加载,当页面需要显示图片的时候才进行加载,否则不加载

发表回复

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

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