快速排序

 

谁考了第k名

1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int N=105;
 6 struct stu{
 7     double grade;
 8     int number;
 9 };
10 stu stus[N];
11 int k;
12 int partition(int begin,int end){
13     //确定基准值
14     stu tmp=stus[begin];
15     while(begin<end){
16         while(begin<end&&stus[begin].grade<=stus[end].grade)end--;
17         if(begin<end){
18             stus[begin]=stus[end];
19             begin++;
20         }
21         while(begin<end&&stus[begin].grade<=stus[end].grade)begin++;
22         if(begin<end){
23             stus[end]=stus[begin];
24             end--;
25         }
26     }
27     stus[end]=tmp;
28     return end;
29 }
30 void quickSort(int begin,int end){
31     int benchmark=partition(begin,end);
32     if(benchmark==k)return;
33     if(k<benchmark&&benchmark-1>begin)quickSort(begin,benchmark-1);
34     if(k>benchmark&&end>benchmark+1)quickSort(benchmark+1,end);
35 }
36 int main(){
37     int n;
38     cin>>n>>k;
39 
40     for(int i=1;i<=n;i++)
41         cin>>stus[i].number>>stus[i].grade;
42     quickSort(1,n);
43     //输出结果
44     printf("%d %g",stus[k].number,stus[k].grade);
45     return 0;
46 }

 

上一篇:Java 对象数组题目 + 改进(封装方法)


下一篇:ES6学习---迭代器的运用,自定义遍历数据--for of