文档章节

快排模板(附求第k大的数)

o
 osc_mervd488
发布于 2018/04/23 19:03
字数 366
阅读 0
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 112;
int a[MAXN], n;

void sort(int l, int r)
{
	if(l >= r) return;
	int i = l, j = r, key = a[l];
	
	while(i < j)
	{
		while(i < j && a[j] >= key) j--;  //注意先从j开始, 也就是先从右边开始 
		if(i < j) a[i] = a[j];
		
		while(i < j && a[i] <= key) i++;
		if(i < j) a[j] = a[i];
	}
	
	a[i] = key;
	sort(l, i - 1); 
	sort(i + 1, r);
}

int main()
{
	scanf("%d", &n);
	REP(i, 0, n) scanf("%d", &a[i]);
	sort(0, n - 1);   //这里是n-1, 我写的版本是左闭右闭 
	REP(i, 0, n) printf("%d ", a[i]);
	puts("");
	return 0;
}

 

快排可以求第k大的数(如有些题目要求中位数), 利用左区间的个数来判断递归左区间还是右区间

//快排求第k大的数 
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int MAXN = 112;
int a[MAXN], n, k;
 
void sort(int l, int r)  
{
	if(l >= r) return;  
	int i = l, j = r, key = a[l];  
	
	while(i < j)
	{
		while(i < j && a[j] >= key) j--;
		if(i < j) a[i] = a[j];
		
		while(i < j && a[i] <= key) i++;
		if(i < j) a[j] = a[i];
	}
	
	a[i] = key;
	if(i < k) sort(i + 1, r);    //k - 1 为所求的位置, 画个图就知道了 
	else if(i > k) return sort(l, i - 1); 
	else return; //并没有整个数组排完, 找到了就结束 
}
 
int main()
{
	scanf("%d", &n);
	_for(i, 1, n) scanf("%d", &a[i]);
	scanf("%d", &k);
	sort(1, n);  
	printf("%d\n", a[k]);
	return 0;
}

 

 

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Swift百万线程攻破单例(Singleton)模式

一、不安全的单例实现 在上一篇文章我们给出了单例的设计模式,直接给出了线程安全的实现方法。单例的实现有多种方法,如下面: class SwiftSingleton { } 这段代码的实现,在shared中进行条...

一叶博客
2014/06/20
3.5K
16
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.4K
1
N简单CMS

N简单CMS能够让网站开发者更快速、灵活、简单的开发网站。 N简单CMS有以下特点: 更简单和自由的模板标签调用 专注于人性化的管理和操作 基于完全php5框架Kohana2.3.4开发 资源调用和消耗更低...

匿名
2013/02/26
3.2K
0

没有更多内容

加载失败,请刷新页面

加载更多

spring-boot集成redis

集成的客户端 1)lettuce方式集成 <dependency><groupId>org.apache.commons</groupId><artifactId>commons-pool2</artifactId></dependency><dependency><groupId>io.lettuce</gro......

简到珍
35分钟前
12
0
Java 8中Lambda表达式默认方法的模板方法模式,你够了解么?

为了以更简单的术语描述模板方法,考虑这个场景:假设在一个工作流系统中,为了完成任务,有4个任务必须以给定的执行顺序执行。在这4个任务中,不同工作流系统的实现可以根据自身情况自定义任...

北柠Java
35分钟前
3
0
阅文集团上半年总收入32.6亿元 同比增长9.7%

  腾讯科技讯,8 月 11 日消息,阅文集团(0772.HK)公布 2020 年中期业绩。报告显示,阅文集团 2020 上半年实现总收入 32.6 亿元,同比增长 9.7%;毛利润为 17.3 亿元,同比增长 6.8%。 ...

gfhtw
38分钟前
14
0
读取Node.js中的环境变量 - Read environment variables in Node.js

问题: Is there a way to read environment variables in Node.js code? 有没有办法在Node.js代码中读取环境变量? Like for example Python's os.environ['HOME'] . 例如,例如Python的os.......

javail
今天
9
0
使用 Cobbler 安装一台 CentOS 主机

安装 CentOS 主机之前,需要安装好 Cobbler 服务端。本文档使用的是 VMware Workstation Pro 14 来安装 CentOS 主机,网络模式需要和 Cobbler 服务端的网络模式相同。 环境: CentOS Linux r...

老孟的Linux私房菜
今天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部