搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 毅毅的点滴 > 每天一题 · Day1 · 快速排序[785]

每天一题 · Day1 · 快速排序[785]

毅毅的点滴 2019-11-08
**题目描述**给定你一个长度为n的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。>> 输入格式* 输入共两行,第一行包含整数 n。* 第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。>> 输出格式* 输出共一行,包含 n 个整数,表示排好序的数列。

数据范围

1≤n≤100000

样例

输入样例:

5
3 1 2 4 5

输出样例:

1 2 3 4 5

分析

使用快排方法:
1.选取:一个比较值
2.整理:数列中小于这个数放在这个数的左侧,将数列中大于这个数放在这个数的右侧
3.进行这个数的左右两个子部分进行快排操作。

#include <iostream>using namespace std;
const int N = 1e5; //这个是输入数据的限制值int n;int q[N]; // 将大量数组开辟在全局(内存中的static区域),防止栈过爆
void quick_sort(int q[], int L, int R){ if(L >= R) return; //1.边界条件判断
// 2.选取一个比较值 int x = q[(L + R)>>1];
int i = L - 1; //这里的i,j要选取 L - 1和R + 1是因为在下面的while()比较的顺序,使i,j游标落在比较的 int j = R + 1; //数字上
while(i < j){ while(q[++i] < x); // 找到左侧的第一个大于比较值的游标位置 while(q[--j] > x); // 找到右侧的第一个小于比较值的游标位置 if(i < j) swap(q[i] , q[j]); // 如果两个i,j游标还未相遇,那么就交换 }
quick_sort(q, L, j); //快排左侧 quick_sort(q, j + 1, R); //快拍右侧}
int main(){ scanf("%d",&n); for(int i = 0; i < n; ++i) scanf("%d", &q[i]); quick_sort(q,0,n - 1); for(int i = 0; i < n; ++i) printf("%d ", q[i]); return 0;}


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《每天一题 · Day1 · 快速排序[785]》的版权归原作者「毅毅的点滴」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注毅毅的点滴微信公众号

毅毅的点滴微信公众号:gh_a7d89d6768a1

毅毅的点滴

手机扫描上方二维码即可关注毅毅的点滴微信公众号

毅毅的点滴最新文章

精品公众号随机推荐

上一篇 >>

spring festival