神马文学网快速排序与快速选择算法(quick sort and quick select algor...
来源：百度文库 编辑：神马文学网 时间：2024/04/29 05:12:59
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
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 {
scanf("%u",&pdataSrc[i]);
}
for(int i=0;i {
for(int j=0;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
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 {
scanf("%u",&pdataSrc[i]);
}
for(int i=0;i {
for(int j=0;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
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 {
scanf("%u",&pdata[i]);
}
i=0;
unsigned int count=1;
while(count<=numEnroll)
{
int flag=0;
curMax=0;
for(int j=0;j {
if(curMax {
flag=j;
curMax=pdata[j];
}
}
pdata[flag]=0;
count++;
}
printf("%u\n",curMax);
delete [] pdata;
}
return 0;
}
#include
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 {
scanf("%u",&pdata[i]);
}
i=0;
unsigned int count=1;
while(count<=numEnroll)
{
int flag=0;
curMax=0;
for(int j=0;j {
if(curMax {
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
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 {
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 {
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 scanf("%u",&pdata[i]);
myqsort(pdata,0,numTotal-1);
printf("%u\n",pdata[numTotal-numEnroll]);
//delete [] pdata;
}
return 0;
}
#include
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 {
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 {
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 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
#include
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 {
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 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 scanf("%d",&pdata[i]);
int temp=qksel(pdata,numTotal-numEnroll,0,numTotal-1);
printf("%d\n",temp);
}
return 0;
}
#include
#include
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 {
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 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 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多次，没心思再细抠了。。快速选择算法描述是看老外写的，看得不一定明白。。链接如下http://www.ics.uci.edu/~eppstein/161/960125.html也不知道是不是这么回事，另外看别人提交的答案有个强悍的家伙四组用例一共才用不到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
登录 注册 欢迎 退出 我的博客 配置 写文章 文章管理 博客首页 全站 当前博客 空间 博客 好友 相册 留言 用户操作
[发私信] [加为好友]
订阅我的博客
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
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
scanf("%u",&pdataSrc[i]);
}
for(int i=0;i
for(int j=0;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
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
scanf("%u",&pdataSrc[i]);
}
for(int i=0;i
for(int j=0;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
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
scanf("%u",&pdata[i]);
}
i=0;
unsigned int count=1;
while(count<=numEnroll)
{
int flag=0;
curMax=0;
for(int j=0;j
if(curMax
flag=j;
curMax=pdata[j];
}
}
pdata[flag]=0;
count++;
}
printf("%u\n",curMax);
delete [] pdata;
}
return 0;
}
#include
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
scanf("%u",&pdata[i]);
}
i=0;
unsigned int count=1;
while(count<=numEnroll)
{
int flag=0;
curMax=0;
for(int j=0;j
if(curMax
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
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
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
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
myqsort(pdata,0,numTotal-1);
printf("%u\n",pdata[numTotal-numEnroll]);
//delete [] pdata;
}
return 0;
}
#include
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
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
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
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
#include
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
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
}
int main()
{
srand((unsigned int)time(NULL));
int numTotal,numEnroll;
while(EOF!=scanf("%d %d",&numTotal,&numEnroll))
{
for(int i=0;i
int temp=qksel(pdata,numTotal-numEnroll,0,numTotal-1);
printf("%d\n",temp);
}
return 0;
}
#include
#include
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
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
}
int main()
{
srand((unsigned int)time(NULL));
int numTotal,numEnroll;
while(EOF!=scanf("%d %d",&numTotal,&numEnroll))
{
for(int i=0;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多次，没心思再细抠了。。快速选择算法描述是看老外写的，看得不一定明白。。链接如下http://www.ics.uci.edu/~eppstein/161/960125.html也不知道是不是这么回事，另外看别人提交的答案有个强悍的家伙四组用例一共才用不到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
快速排序与快速选择算法(quick sort and quick select algor...
算法设计与分析 2.81 快速排序
快速排序算法
快速排序算法
快速排序算法
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
算法连载（2）--快速排序与插入排序的比较 - Compower Studio - CSD...
A Quick MFC and WTL Comparison
IEBlog : Extending IE Quick and Dirty
BSD Sockets: A Quick And Dirty Primer
[Cockcroft98] Chapter 1. Quick Tips and Recipes
采用部分快速排序算法实现数组的部分排序
[原创]精益生产--Quick Changeover快速换模总结 - 老黄的畅享空间 - ...
快速排序
Quick Installation
quick与quickly的用法区别
ViewCVS and Apache on Windows Setup Quick Reference | Subversionary
sort排序
采用部分快速排序算法实现数组的部分排序 - eaglet的专栏 - CSDN博客
采用部分快速排序算法实现数组的部分排序 - eaglet - 博客园
快速排序--C语言
java快速排序法
Quick Guide to Prototype
Quick Guide to Prototype