首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >第九届蓝桥杯大赛个人赛省赛(软件类)Java类 真题 第五题 标题:快速排序

第九届蓝桥杯大赛个人赛省赛(软件类)Java类 真题 第五题 标题:快速排序

作者头像
静谧星空TEL
发布2022-05-07 10:29:23
1450
发布2022-05-07 10:29:23
举报

标题:快速排序

以下代码可以从数组a[]中找出第k小的元素。   它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。 请仔细阅读分析源码,填写划线部分缺失的内容。

package com.wzxy.test;

import java.util.Random;

public class Main2{
	
	public static void main(String args[]) {	//0 1 2 3 4 5
		int [] a = {1, 4, 2, 8, 5, 7};			//1 2 4 5 7 8 
		System.out.println(quickSelect(a, 0, 5, 4));	//a为数组 ,0-5为数组下标范围,4为k表示第k小的
	}
	public static int quickSelect(int a[], int l, int r, int k) {
		Random rand = new Random();
		int p = rand.nextInt(r - l + 1) + l;
		int x = a[p];
		int tmp = a[p]; a[p] = a[r]; a[r] = tmp;
		int i = l, j = r;
		while(i < j) {
                	while(i < j && a[i] < x) i++;
                	if(i < j) {
                        	a[j] = a[i];
                        	j--;
                	}
                	while(i < j && a[j] > x) j--;
                	if(i < j) {
                        	a[i] = a[j];
                        	i++;
                	}
        	}
        	a[i] = x;
        	p = i;
        	if(i - l + 1 == k) return a[i];
        	if(i - l + 1 < k) return quickSelect( _______________ ); //填空
        	else return quickSelect(a, l, i - 1, k);	
	}
}

提交的答案为:a, l, r, k

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-03-23,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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