快速排序基本思路(通俗易懂+例子)「建议收藏」

快速排序基本思路(通俗易懂+例子)「建议收藏」快速排序今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单下面进行简单的试试快速排序的基本思想是1、先从数列中取出一个数作为基准数2、分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边3、再对左右区间重复第二步,直到各区间只有一个数概括来说为挖坑填数+分治法下面举例来进行说明,主要有三个参数,i为区间的开始地址,j为区间

大家好,又见面了,我是你们的朋友全栈君。

快速排序

内推日常实习社招也可以简历发送到我邮箱,长期接受简历,部门做搜索产品研发,主要php和go语言!
2022百度提前批招聘】填写内推码可以免专业笔试,部门直接发起面试,有想去的部门可以发送简历到 927①56零36@qq.com 定向内推,本次招聘不影响正常校招流程,相当于多一次机会,赶紧填写内推码【am8eh4】试试吧!
在这里插入图片描述

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单
下面进行简单的试试

快速排序的基本思想是

1、先从数列中取出一个数作为基准数

2、分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边

3、再对左右区间重复第二步,直到各区间只有一个数

概括来说为 挖坑填数+分治法

下面举例来进行说明,主要有三个参数,i为区间的开始地址,j为区间的结束地址,X为当前的开始的值

第一步,i=0,j=9,X=21

0 1 2 3 4 5 6 7 8 9
21 32 43 98 54 45 23 4 66 86

第二步,从j开始由,后向前找,找到比X小的第一个数a[7]=4,此时i=0,j=6,X=21
进行替换

0 1 2 3 4 5 6 7 8 9
4 32 43 98 54 45 23 21 66 86

第三步,由前往后找,找到比X大的第一个数a[1]=32,此时i=2,j=6,X=21

0 1 2 3 4 5 6 7 8 9
4 21 43 98 54 45 23 32 66 86

第四步,从j=6开始由,由后向前找,找到比X小的第一个数a[0]=4,此时i=2,j=0,X=21,发现j<=i,所以第一回结束

可以发现21前面的数字都比21小,后面的数字都比21大
接下来对两个子区间[0,0]和[2,9]重复上面的操作即可

下面直接给出过程,就步详细解说了

i=2,j=6,X=43

0 1 2 3 4 5 6 7 8 9
4 21 43 98 54 45 23 32 66 86

i=4,j=6,X=43

0 1 2 3 4 5 6 7 8 9
4 21 32 98 54 45 23 43 66 86

i=4,j=5,x=43

0 1 2 3 4 5 6 7 8 9
4 21 32 43 54 45 23 98 66 86

i=5,j=5,x=43

0 1 2 3 4 5 6 7 8 9
4 21 32 23 43 45 54 98 66 86

然后被分为了两个子区间[2,3]和[5,9]

…最后排序下去就是最终的答案

0 1 2 3 4 5 6 7 8 9
4 21 23 32 43 45 54 66 86 98

总结:

1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2.j–由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。


代码

class Solution { 
   
	public void sort(int left,int right,int[] array) { 
   
		if (left>=right) return ;
		int start=left;
		int end=right;
		int flag=left;
		while(left<right) { 
   
			while ((left<right)&&(array[right]>=array[flag])) { 
   
				right--;
			}
			if (array[right]<array[flag]) { 
   
				int tmp=array[right];
				array[right]=array[flag];
				array[flag]=tmp;
				flag=right;
			}
			while ((left<right)&&(array[left]<=array[flag])) { 
   
				left++;
				}
			if (array[left]>array[flag]) { 
   
				int tmp=array[left];
				array[left]=array[flag];
				array[flag]=tmp;
				flag=left;
			}
		}
		sort(start, left-1, array);
		sort(left+1, end, array);
	}
}

分享一个比较牛逼的学习java的网站,基础知识和架构等都有,连接如下:
http://how2j.cn?p=54321
在这里插入图片描述

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

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

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

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

(0)


相关推荐

  • USB 驱动彻底删除「建议收藏」

    USB 驱动彻底删除「建议收藏」最近做USB自定义设备开发,遇到以下问题,应该算是解决了,特地写出来和大家分享。在进行USB设备开发的时候,经常需要更改USB设备的名称或者pid、vid等,特别是进行自定义USB设备,自己写驱动程序的时候,会出现一个问题就是:设计了一个USB设备,插到电脑上通过安装驱动可以正常试用。后来修改了USB设备的设备名称pid、vid,再插上电脑,还是显示原来的设备名称

    2022年10月20日
  • IDEA的下载和使用安装

    IDEA的下载和使用安装一.IDEA的下载IDEA下载地址:https://www.jetbrains.com/idea/download/#section=windowsIDEA分为两个版本:旗舰版(Ultimate)和社区版(Community)。旗舰版收费(限30天免费试用),社区版免费二.安装过程在这我们选择装旗舰版,社区版虽然免费,但是有些功能不全双击【ideaIU-2018.3.3.exe】安装文件:点击下一步(Next)选择好【文件的安装文件目录】,点击【Next】

  • android scaleanimation动画,Animation之ScaleAnimation(缩放动画片)「建议收藏」

    android scaleanimation动画,Animation之ScaleAnimation(缩放动画片)「建议收藏」Animation之ScaleAnimation(缩放动画)ScaleAnimation(缩放动画)缩放的意思就是对图片或者文字等进行扩大或缩小。下面开始编写代码,相关重要属性参数的解释都在代码中。1、编写main.xml文件。xmlns:tools=”http://schemas.android.com/tools”android:layout_width=”match_parent”andr…

    2022年10月15日
  • java 取余和取模运算之间的区别「建议收藏」

    java 取余和取模运算之间的区别「建议收藏」转自lee371042https://blog.csdn.net/lee371042/article/details/102553342packageOperator;importjava.math.BigInteger;/***假如有两个数:*amod(b)与a%b,b为正整数,*一种叫a对b取模,另一个叫a对b取余,两种叫法有什么区别呢?*通常情况下,取模运算也叫取余运算,*它们返回的结果都是一个数对另一个数的余数,**区别在于当a是一

  • Java 异常之 RuntimeException和Exception的区别

    Java 异常之 RuntimeException和Exception的区别在java的异常类体系中,Error和RuntimeException是非检查型异常,其他的都是检查型异常。所有方法都可以在不声明throws的情况下抛出RuntimeException及其子类不可以在不声明的情况下抛出非RuntimeException简单的说,非RuntimeException必要自己写catch块处理掉。RuntimeExce

  • stn专线和otn有什么区别_stn云专线是什么意思?

    stn专线和otn有什么区别_stn云专线是什么意思?云专线产品是指依托于STN(智能传送网),为客户提供灵活业务接入、灵活带宽、高可靠性及端到端质量保障的专线产品。STN云专线产品描述:依托于STN(智能传送网),为客户提供灵活业务接入、灵活带宽、高可靠性及端到端质量保障的二层以太专线产品。STN(SmartTransportNetwork)智能传送网,采用JIPRAN及PTN技术相结合发展起来的—种增强型分组组网技术,该技术可叠加在移动业…

    2022年10月19日

发表回复

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

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