7-1排序(25分)
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：只有1个元素；
数据2：11个不相同的整数，测试基本正确性；
数据：10个随机整数；
数据4：个随机整数；
数据5：个随机整数；
数据6：个顺序整数；
数据7：个逆序整数；
数据8：个基本有序的整数；
数据9：个随机正整数，每个数字不超过。
输入格式:输入第一行给出正整数N（≤），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。
输出格式:在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。
输入样例:---5
输出样例:-20-17-81
方法1：简单粗暴STLsort+vectorAC代码总计需要2分钟
直接使用STLsort+vector
#includeiostam#includevector#includealgorithmusingnamespacestd;vectorintdata;intmain(){intN,i;cinN;for(intj=0;jN;j++){cini;data.push_back(i);}sort(data.begin(),data.end());vectorint::iteratorit;for(it=data.begin();it!=data.end()-1;it++)cout*it";cout*it;}这个方法可以看出，STL确实是一个强大的高效算法模板库。
方法二：快速排序
采用快速排序，根据理论我们知道它是一定能够在要求的时间内完成排序任务的。
#includeiostam#includevector#includealgorithmusingnamespacestd;vectorintData;intPartition(intlow,inthigh){intpivotloc;pivotloc=Data[low];while(lowhigh){while(lowhighData[high]=pivotloc)high--;Data[low]=Data[high];while(lowhighData[low]=pivotloc)low++;Data[high]=Data[low];}Data[low]=pivotloc;turnlow;}voidQSort(intlow,inthigh){intpivotloc;if(lowhigh){pivotloc=Partition(low,high);QSort(low,pivotloc-1);QSort(pivotloc+1,high);}}intmain(){intN,i;cinN;for(intj=0;jN;j++){cini;Data.push_back(i);}QSort(0,N-1);vectorint::iteratorit;for(it=Data.begin();it!=Data.end()-1;it++)cout*it";cout*it;}方法三：希尔排序
希尔排序，我采用手工给出delta序列的方法，在最后时间上，竟然超过了前两个算法。
#includeiostam#includevector#includealgorithmusingnamespacestd;vectorintData;voidShellinsert(intd){for(inti=d;iData.size();i++){if(DataData[i-d]){intj,tmp=Data;for(j=i-d;j=0Data[j]=tmp;j-=d);//循环让j停留在待插入位置j+=d;//插入位置for(intk=i;k!=j;k-=d)Data[k]=Data[k-d];//后移Data[j]=tmp;//插入}}}voidShellSort(){inta[11]={,9,79,51,47,7,29,11,7,,1};for(inti=0;i11;i++)Shellinsert(a);}intmain(){intN,i;cinN;for(intj=0;jN;j++){cini;Data.push_back(i);}ShellSort();vectorint::iteratorit;for(it=Data.begin();it!=Data.end()-1;it++)cout*it";cout*it;}方法四：借助STL建堆进行堆排序
STL关于堆的函数为
make_heap(iteratorbegin，iteratorend,cmp)建堆
cmp=less()建大顶堆
cmp=gater()建小顶堆
pop_heap(iteratorbegin，iteratorend,cmp)将堆第一个元素放到最后（取出第一个元素）然后重新按堆排列，注意，如果反复使用这个语句，只能取出两个值，必须要再加上pop_back()才能“真正”取出。
push_heap(iteratorbegin，iteratorend,cmp)按照堆规则添加元素
使用堆排序的方法，将通过的时间降低到了两位数
比前三个算法又更快了许多。
#includeiostam#includevector#includealgorithmusingnamespacestd;vectorintData;voidHeapSort(){vectorintData2;Data2=Data;make_heap(Data2.begin(),Data2.end(),gaterint());//借助STL建堆for(inti=0;iData.size();i++){Data=Data2[0];//取堆顶pop_heap(Data2.begin(),Data2.end(),gaterint());Data2.pop_back();//取出并重排}turn;}intmain(){intN,i;cinN;for(intj=0;jN;j++){cini;Data.push_back(i);}HeapSort();vectorint::iteratorit;for(it=Data.begin();it!=Data.end()-1;it++)cout*it";cout*it;}总结：
以上三个算法，在实际运行时间上，逐个从四位数降到三位数再降到两位数，当然，两位数与STL的使用是有着密切的关系的，倘若我自己写堆函数，可能也无法达到两位数的惊人成绩，所以，STL在提升速度方面和简化代码方面有着巨大的作用，通过这一道题，实现了昨天推送中学习的几种重要算法。
预览时标签不可点收录于话题#个上一篇下一篇