sort

Time Limit: 6000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 46140 Accepted Submission(s): 13318

Problem Description 给你n个整数，请按从大到小的顺序输出其中前m大的数。

Input 每组测试数据有两行，第一行有两个数n,m(0 < n,m < 1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。

Output 对每组测试数据按从大到小的顺序输出前m大的数。

Sample Input 5 3 3 -35 92 213 -644

Sample Output 213 92 3

Hint 请用VC/VC++提交

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1425

就是普通的快排，快排详解博客链接：

http://blog.csdn.net/morewindows/article/details/6684558

---

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> #include <stack> #include <queue> #include <vector> #define INF 0xffffffff using namespace std; const int maxn = 1000000+6; int s[maxn]; void quick_sort(int l, int r, int m){ if(l < r){ int i=l, j=r, x=s[l]; //选第一个值为基准数 while(i < j){ while(i<j && s[j]<x) j--; if(i<j) s[i++] = s[j]; //从右往左找到第一个比基准数大的,填入位置i while(i<j && s[i]>=x) i++; if(i<j) s[j--] = s[i]; //从左往右找到第一个比基准数小的，填入位置j } s[i] = x; //i==j,填入基准数 quick_sort(l, i-1, m); if(i<=m) //只要排序前m个就够了 quick_sort(i+1, r, m); } } int main(){ int n, m; while(scanf("%d%d", &n ,&m) == 2 && n){ for(int i=0; i<n ;i++){ scanf("%d", &s[i]); } quick_sort(0, n-1, m); for(int i=0; i<m; i++){ if(i == 0){ printf("%d", s[i]); continue; } printf(" %d", s[i]); } printf("\n"); } return 0; }