Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
快速排序与快速选择
? 解题记录 ?
? 模板 ?
? 排序 ?
2024-03-26 17:49:23
48
0
0
rockdu
? 解题记录 ?
? 模板 ?
? 排序 ?
看到网上有许多快速排序和快速选择的代码，但是相当一部分都有些错误，这里放一下自己的写法 快速排序模板题：https://www.luogu.com.cn/problem/P1177 快速选择模板题：https://vjudge.net/problem/POJ-2388 ``` #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; const int maxn = 1e6 + 5; int n, a[maxn]; void kth_element(int * l, int * k, int * r) { if(l >= r - 1) return; int * ptr = rand() % (r - l) + l, *i, *j; int base = *ptr; swap(*ptr, *l); i = l, j = r; while (i < j) { do --j; while(i < j && *j > base); if (i < j) *i = *j; else break; do ++i; while(i < j && *i < base); if (i < j) *j = *i; else break; } *i = base; if (k == i) return; if (k < i) kth_element(l, k, i); else kth_element(i, k, r); } void quick_sort(int * l, int * r) { if(l >= r - 1) return; int * ptr = rand() % (r - l) + l, *i, *j; int base = *ptr; swap(*ptr, *l); i = l, j = r; while (i < j) { do --j; while(i < j && *j > base); if (i < j) *i = *j; else break; do ++i; while(i < j && *i < base); if (i < j) *j = *i; else break; } *i = base; quick_sort(l, i); quick_sort(i, r); } int main() { srand(66662333); scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } // quick_sort(a + 1, a + n + 1); // for(int i = 1; i <= n; ++i) { // printf("%d ", a[i]); // } kth_element(a + 1, a + n / 2 + 1, a + n + 1); printf("%d", a[n / 2 + 1]); } ```
上一篇: 无
下一篇:
多模态Transformer
0
赞
48 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册