yuliyang的专栏
登录 注册 欢迎 退出 我的博客 配置 写文章 文章管理 博客首页 全站 当前博客 空间 博客 好友 相册 留言 用户操作 [发私信] [加为好友] 订阅我的博客 yuliyang的公告 文章分类 存档 2009年06月(4) 2009年05月(1) 2008年10月(3) 快速排序与快速选择算法(quick sort and quick select algorithm) 收藏 飞燕之家上的一道排序题: 题目描述:
某市重点高中很有名气,它在计算录取分数线的时候, 采用以下办法:总人数乘以录取百分比,得到录取人数k后, 从最高分开始数k个人,这个人的中考分数就作为 这所学校的录取分数线了。 输入:
有多个测试点,每个测试点第一行是n和k(k<=n), n是总人数,总人数不超过1e6,k是录取的人数 第二行就是n个学生的中考分数,由于采用一种 特殊的标准计分方式,分数范围在0至1e8 输出:
对每个测试点输出对应的分数线,一个结果一行 样例输入:
7 3 1 2 3 4 5 6 7 样例输出:
5 最开始用插入,第三组用例超时
view plaincopy to clipboardprint?
#include <iostream> using namespace std; int main() { unsigned int numTotal,numEnroll; while(EOF!=scanf("%u %u",&numTotal,&numEnroll) && numTotal!=0 && numEnroll!=0) { unsigned int * pdataDes=new unsigned int[numEnroll]; unsigned int * pdataSrc=new unsigned int[numTotal]; memset(pdataDes,(unsigned int)0,numEnroll*sizeof(unsigned int)); for(int i=0;i<numTotal;i++) { scanf("%u",&pdataSrc[i]); } for(int i=0;i<numTotal;i++) { for(int j=0;j<numEnroll;j++) { if(pdataSrc[i]>pdataDes[j]) { for(int k=numEnroll-1;k>j;k--) pdataDes[k]=pdataDes[k-1]; pdataDes[j]=pdataSrc[i]; break; } } } printf("%u\n",pdataDes[numEnroll-1]); memset(pdataDes,0,numEnroll*sizeof(unsigned int)); delete [] pdataDes; delete [] pdataSrc; } return 0; } #include <iostream> using namespace std; int main() { unsigned int numTotal,numEnroll; while(EOF!=scanf("%u %u",&numTotal,&numEnroll) && numTotal!=0 && numEnroll!=0) { unsigned int * pdataDes=new unsigned int[numEnroll]; unsigned int * pdataSrc=new unsigned int[numTotal]; memset(pdataDes,(unsigned int)0,numEnroll*sizeof(unsigned int)); for(int i=0;i<numTotal;i++) { scanf("%u",&pdataSrc[i]); } for(int i=0;i<numTotal;i++) { for(int j=0;j<numEnroll;j++) { if(pdataSrc[i]>pdataDes[j]) { for(int k=numEnroll-1;k>j;k--) pdataDes[k]=pdataDes[k-1]; pdataDes[j]=pdataSrc[i]; break; } } } printf("%u\n",pdataDes[numEnroll-1]); memset(pdataDes,0,numEnroll*sizeof(unsigned int)); delete [] pdataDes; delete [] pdataSrc; } return 0; } Test 1: Accepted Time = 0 ms
Test 2: Accepted Time = 48 ms Test 3: Time Limit Exceed -------------------------------- Problem ID ct8_2 Test Result Time Limit Exceed Time Limit 5000 ms Total Memory 5416 Kb / 65000 Kb Code Length 1066 Bytes 后来改为统计第n大的数,直接输出。。本以为减少了内存读写操作能好些,结果第二组用例居然更慢了。。。
view plaincopy to clipboardprint?
#include <iostream> using namespace std; int main() { unsigned int numEnroll,numTotal,temp,curMax; while(EOF!=scanf("%u %u",&numTotal,&numEnroll)) { unsigned int * pdata=new unsigned int[numTotal]; memset(pdata,0,numEnroll*sizeof(unsigned int)); unsigned int i; for(i=0;i<numTotal;i++) { scanf("%u",&pdata[i]); } i=0; unsigned int count=1; while(count<=numEnroll) { int flag=0; curMax=0; for(int j=0;j<numTotal;j++) { if(curMax<pdata[j]) { flag=j; curMax=pdata[j]; } } pdata[flag]=0; count++; } printf("%u\n",curMax); delete [] pdata; } return 0; } #include <iostream> using namespace std; int main() { unsigned int numEnroll,numTotal,temp,curMax; while(EOF!=scanf("%u %u",&numTotal,&numEnroll)) { unsigned int * pdata=new unsigned int[numTotal]; memset(pdata,0,numEnroll*sizeof(unsigned int)); unsigned int i; for(i=0;i<numTotal;i++) { scanf("%u",&pdata[i]); } i=0; unsigned int count=1; while(count<=numEnroll) { int flag=0; curMax=0; for(int j=0;j<numTotal;j++) { if(curMax<pdata[j]) { flag=j; curMax=pdata[j]; } } pdata[flag]=0; count++; } printf("%u\n",curMax); delete [] pdata; } return 0; } Test 1: Accepted Time = 0 ms
Test 2: Accepted Time = 68 ms Test 3: Time Limit Exceed -------------------------------- Problem ID ct8_2 Test Result Time Limit Exceed Time Limit 5000 ms Total Memory 4000 Kb / 65000 Kb Code Length 905 Bytes 后来改为快速排序,这回快了一些,但是第四组用例仍然超时:
view plaincopy to clipboardprint?
#include <iostream> using namespace std; #define max 1000000 int pdata[max]={0}; void swap(int *a,int *b) { int temp=*a; *a=*b; *b=temp; } int partition(int *a,int begin,int end) { int i=begin-1; for(int j=begin;j<end;j++) { if(a[j]<=a[end]) { i+=1; swap(&a[i],&a[j]); } } swap(&a[i+1],&a[end]); return i+1; } void myqsort(int *a,int begin,int end) { if(begin<end) { int i=partition(a,begin,end); myqsort(a,begin,i-1); myqsort(a,i+1,end); } } int main() { int numTotal,numEnroll; while(EOF!=scanf("%u %u",&numTotal,&numEnroll)) { //int *pdata = new int [numTotal]; memset(pdata,0,numTotal*sizeof(int)); for(int i=0;i<numTotal;i++) scanf("%u",&pdata[i]); myqsort(pdata,0,numTotal-1); printf("%u\n",pdata[numTotal-numEnroll]); //delete [] pdata; } return 0; } #include <iostream> using namespace std; #define max 1000000 int pdata[max]={0}; void swap(int *a,int *b) { int temp=*a; *a=*b; *b=temp; } int partition(int *a,int begin,int end) { int i=begin-1; for(int j=begin;j<end;j++) { if(a[j]<=a[end]) { i+=1; swap(&a[i],&a[j]); } } swap(&a[i+1],&a[end]); return i+1; } void myqsort(int *a,int begin,int end) { if(begin<end) { int i=partition(a,begin,end); myqsort(a,begin,i-1); myqsort(a,i+1,end); } } int main() { int numTotal,numEnroll; while(EOF!=scanf("%u %u",&numTotal,&numEnroll)) { //int *pdata = new int [numTotal]; memset(pdata,0,numTotal*sizeof(int)); for(int i=0;i<numTotal;i++) scanf("%u",&pdata[i]); myqsort(pdata,0,numTotal-1); printf("%u\n",pdata[numTotal-numEnroll]); //delete [] pdata; } return 0; } Test 1: Accepted Time = 0 ms
Test 2: Accepted Time = 26 ms Test 3: Accepted Time = 4246 ms Test 4: Time Limit Exceed -------------------------------- Problem ID ct8_2 Test Result Time Limit Exceed Time Limit 5000 ms Total Memory 4032 Kb / 65000 Kb Code Length 934 Bytes 由于快速排序导致大量递归浪费时间空间,所以考虑要减少递归次数。由于要找第n大的数,所以没有必要对所有数据都排序,又找到了快速选择算法。。
view plaincopy to clipboardprint?
#include <iostream> #include <ctime> using namespace std; int pdata[1000000]={0}; void swap(int *a, int *b) { int temp=*a; *a=*b; *b=temp; } int partition(int *a, int begin, int end) { swap(&a[rand()%(end-begin+1)],&a[end]); int i=begin-1; for(int j=0;j<end;j++) { if(a[j]<=a[end]) { i++; swap(&a[i],&a[j]); } } swap(&a[i+1],&a[end]); return i+1; } int qksel(int *a, int n, int begin, int end) { int temp=partition(a,begin,end); if(n==temp)return a[temp]; else if(n<temp) return qksel(a,n,begin,temp-1); else return qksel(a+temp+1,n-temp-1,0,end-temp-1); } int main() { srand((unsigned int)time(NULL)); int numTotal,numEnroll; while(EOF!=scanf("%d %d",&numTotal,&numEnroll)) { for(int i=0;i<numTotal;i++) scanf("%d",&pdata[i]); int temp=qksel(pdata,numTotal-numEnroll,0,numTotal-1); printf("%d\n",temp); } return 0; } #include <iostream> #include <ctime> using namespace std; int pdata[1000000]={0}; void swap(int *a, int *b) { int temp=*a; *a=*b; *b=temp; } int partition(int *a, int begin, int end) { swap(&a[rand()%(end-begin+1)],&a[end]); int i=begin-1; for(int j=0;j<end;j++) { if(a[j]<=a[end]) { i++; swap(&a[i],&a[j]); } } swap(&a[i+1],&a[end]); return i+1; } int qksel(int *a, int n, int begin, int end) { int temp=partition(a,begin,end); if(n==temp)return a[temp]; else if(n<temp) return qksel(a,n,begin,temp-1); else return qksel(a+temp+1,n-temp-1,0,end-temp-1); } int main() { srand((unsigned int)time(NULL)); int numTotal,numEnroll; while(EOF!=scanf("%d %d",&numTotal,&numEnroll)) { for(int i=0;i<numTotal;i++) scanf("%d",&pdata[i]); int temp=qksel(pdata,numTotal-numEnroll,0,numTotal-1); printf("%d\n",temp); } return 0; } 终于。。。。
Test 1: Accepted Time = 0 ms
Test 2: Accepted Time = 21 ms Test 3: Accepted Time = 3187 ms Test 4: Accepted Time = 3248 ms -------------------------------- Problem ID ct8_2 Test Result Accepted Total Time 6456 ms Total Memory 4032 Kb / 65000 Kb Code Length 1030 Bytes 后记:这题做了整整两天提交了n多次,没心思再细抠了。。
快速选择算法描述是看老外写的,看得不一定明白。。链接如下
也不知道是不是这么回事,
另外看别人提交的答案有个强悍的家伙四组用例一共才用不到1500ms,
我这个排序写得肯定很傻,请高手指出问题,我爱你们
发表于 @ 2009年06月13日 09:53:00 | 评论( 0 ) | 编辑| 举报| 收藏
旧一篇:cin、cin.get()、cin.getline()、getline()、gets()等函数的用法给yuliyang的留言只有注册用户才能发表评论!登录注册姓 名:
校验码: Csdn Blog version 3.1a Copyright © yuliyang 本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/yuliyang/archive/2009/06/13/4265619.aspx
|
|