前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >快速排序基本思路(通俗易懂+例子)「建议收藏」

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

作者头像
全栈程序员站长
发布2022-07-02 16:25:44
3980
发布2022-07-02 16:25:44
举报

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

快速排序

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

快速排序的基本思想是

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]中。


代码

代码语言:javascript
复制
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

在这里插入图片描述
在这里插入图片描述

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 快速排序
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档