快速排序(随机化快速排序 随机主元)java代码(递归实现)分治法(分而治之)

举报
YuShiwen 发表于 2022/03/31 01:03:23 2022/03/31
【摘要】 固定主元的快速排序: 1.首先选取一个主元(一般取数组的头部或者尾部为主元); 2.把其他数与主元比较,如果比主元小,放主元左边,如果比主元大,放主元右边;(这个时候主元左边的数都只是比主元小,左边的数...

固定主元的快速排序

1.首先选取一个主元(一般取数组的头部或者尾部为主元);
2.把其他数与主元比较,如果比主元小,放主元左边,如果比主元大,放主元右边;(这个时候主元左边的数都只是比主元小,左边的数还没有从小到大排好,右边也是)。
3.对主元左边数组段重复1,2步骤;对右边也重复1,2步骤。

ps:上述步骤2的具体实现说明(主元以每次选取数组尾端元素为例):
1.创建两个指针i,j;i初始值为数组头部元素下标减一,j为数组头部元素下标(i左边存放比主要小的元素,i到j存放比主元大的元素,等到j走到尾端要交换主元素时,i+1元素与主元交换即可)
2.j进行移动并与主元进行判断;如果j所对应元素小于主元,j++,i不操作;如果大于,i++,i和j所指元素进行交换,j++.

固定主元的弊端:

如果需要排序的序列为234561 ,那么会使得算法的时间复杂度为:O(n2).
为了避免这种情况,选择随机的主元是一个很好的方式。

随机主元的快速排序(随机化快速排序):

也就是用系统生成随机数的方法去选择数组下标作为主元,选择后便与数组最后一个元素进行交换,之后的步骤就与固定主元的快速排序相同。
随机主元的快速排序它的时间复杂度的数学期望为:O(nlogn)。
步骤如下:
1.首先选取一个随机主元,与数组尾端元素进行交换.
2.把其他数与主元比较,如果比主元小,放主元左边,如果比主元大,放主元右边;(这个时候主元左边的数都只是比主元小,左边的数还没有从小到大排好)。
3.对主元左边数组段重复1,2步骤;对右边也重复1,2步骤。

ps:上述步骤2的具体实现参考固定主元的快速排序中的ps.

举例:
比如给定数组为945721683,下面我们对其进行分析:
开始——>(比主元大的用蓝色表示,比主元小的用橙色表示,i指向数组首端的前一个,j指向数组首端,即i=left-1,j=left).
刚开始i指向空,j指向9.
1.随机选择主元,假设选择主元为6;
2.主元6与末尾8交换,变为:945721386
3.主元6与j所指9比较,比6小,j++,j指向4,数组变为:945721386
4.主元6与j所指4比较,比4大,i++,i此时指向9,i与j交换,j++,变为:495721386
5.主元6与j所指5比较,比5大,i++,i此时指向9,i与j交换,j++,变为:459721386
6.主元6与j所指7比较,比7小,j++,变为:457921386
7…省略2138的比较与上述类似,变为:452139786
8.j指向了数组最后一个,即主元,则i+1与主元交换,即9与主元6交换
9.然后递归调用本函数,左边参数的left = left,right = i;右边参数的left = i+2,right= right;递归出口条件为left>=right.

java代码实现随机化快速排序:

public void toQuickSort(int []arr,int left,int right) {
	if(left>=right) 
		return;
	int principalElement = left+(int)(Math.random()*(right-left+1));  //选取随机主元
	//把随机主元放到数组尾部
	int temp = arr[principalElement];
	arr[principalElement] = arr[right];
	arr[right] = temp;
	//数组中元素与主元比较
	int i = left-1;
	for(int j = left;j<=right;j++) {
		if(arr[j]<arr[right]) {
			i++;
			int temp1 = arr[i];
			arr[i] = arr[j];
			arr[j] = temp1;
		}
	}
	//最后把主元放到适当位置
	int temp2 = arr[right];
	arr[right] = arr[i+1];
	arr[i+1] = temp2;
	
	toQuickSort(arr,left,i);
	toQuickSort(arr,i+2,right);
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

函数调用,运行结果:

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

文章来源: blog.csdn.net,作者:Mr.Yushiwen,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/MrYushiwen/article/details/107258290

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200