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)
blank

相关推荐

  • Jenkins教程(Windows版)

    Jenkins教程(Windows版)安装Java环境安装过程省略环境变量JAVA_HOME=C:\ProgramFiles\Java\jdk1.8.0_191PATH增加%JAVA_HOME%\binjava-version安装Maven环境安装过程省略环境变量MAVEN_HOME=D:\apache-maven-3.5.4PATH增加%MAVEN_HOME%\binmvn-v安装Tomcat环境安装过程省略环境变量CATALINA_BASE=D:\apache-tom..

  • 约瑟夫环问题详解

    约瑟夫环问题详解在牛客网上做到一道题,是约瑟夫环的变型,所以借此学习一下新知识,并且巩固一下对题目意思的理解,这一篇仅作约瑟夫环问题的解释,下一篇再写题目:1.首先,我们先来了解一下什么是约瑟夫环问题:讲一个比较有意思的故事:约瑟夫是犹太军队的一个将军,在反抗罗马的起义中,他所率领的军队被击溃,只剩下残余的部队40余人,他们都是宁死不屈的人,所以不愿投降做叛徒。一群人表决说要死,所以用一种策略来先后杀…

  • MATLAB中LSTM算法实例_bresenham直线算法

    MATLAB中LSTM算法实例_bresenham直线算法Gauss-Newton算法MATLAB实现结果回顾算法实现总结结果回顾Gauss-Newton算法对Gauss-newton算法做了详细的解释,并且使用C++做了实例程序。但是程序其实有微小错误,实际的坐标并不是年代1815—1885,而是1—8,否则p=A∗exp(B∗t)p=A*exp(B*t)p=A∗exp(B∗t)拟合时将会迅速增大,也得不到A=0.7A=0.7A=0.7…

  • 微信小程序开发实战1 微信小程序开发概述

    微信小程序开发实战1 微信小程序开发概述1.微信小程序开发概述1.1微信小程序的特点微信小程序是微信平台提供的一种开放技术,微信小程序为企业用户服务,用于建立一种移动端的“轻应用”,这种应用是不需要下载安装即可使用的应用,用户扫一扫或者搜一下即可打开应用。用户也不用关心是否安装了太多应用的而造成手机空间不足问题。微信小程序的推出后,与订阅号、服务号、企业号并列成为微信的企业应用体系。图1-1微信公众平台产品类型微信小程序运行在微信平台之上,微信平台对不同的手机平台已经做了兼容。使用微信小程序开发的应用,不需要兼容多个平台,开发完成后可

  • pytest的使用_实例调用和类调用

    pytest的使用_实例调用和类调用Pytest执行用例规则Pytest在命令行中支持多种方式来运行和选择测试用例1.对某个目录下所有的用例pytest2.对模块中进行测试pytesttest_mod.py3.对文件夹进行

  • linux 7z压缩、解压命令「建议收藏」

    linux 7z压缩、解压命令「建议收藏」原文地址:https://blog.csdn.net/jk110333/article/details/7829879支持7Z,ZIP,Zip64,CAB,RAR,ARJ,GZIP,BZIP2,TAR,CPIO,RPM,ISO,DEB压缩文件格式安装:sudoapt-getinstall p7zip-full# 7zayajiu.7zyajiu.jpgyajiu.png…

发表回复

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

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