归并排序
归并排序想必大家并不陌生，它的算法思路也十分清晰，且很容易发现，它是可以递归的：
对于有序表的归并算法：依次比较有序表表首，将表首元素插入新数组，移动表首指针，再更改原数组中元素。
#includeiostream#includevector#includealgorithmusingnamespacestd;vectorintData;voidmergeSort(intlow,inthigh){if(low==high)return;intmid=(low+high)/2;mergeSort(low,mid);//归并左mergeSort(mid+1,high);//归并右//有序列的归并算法intp1=low,p2=mid+1;vectorintmergelist;//需要额外空间存放归并后序列while(p1!=mid+1p2!=high+1)if(Data[p1]=Data[p2])mergelist.push_back(Data[p1++]);elsemergelist.push_back(Data[p2++]);if(p1!=mid+1)//如果最终p1未到位，把p1后面的序列复制过去while(p1!=mid+1)mergelist.push_back(Data[p1++]);elsewhile(p2!=high+1)mergelist.push_back(Data[p2++]);inttmp=low;for(vectorint::iteratorit=mergelist.begin();it!=mergelist.end();it++)Data[tmp++]=*it;return;}intmain(){intN,i;cinN;for(intj=0;jN;j++){cini;Data.push_back(i);}mergeSort(0,N-1);vectorint::iteratorit;for(it=Data.begin();it!=Data.end()-1;it++)cout*it";cout*it;}
基数排序
基数排序是不同于其他排序的一种比较特殊的排序方式。
基数排序是一种借助多关键字排序思想来实现单逻辑关键字排序的方法。
就比如桥牌：
它始终是按照花色顺序再按照牌力排序的。
倘若我们规定SHCD(当然实际上桥牌是SHDC)
那么上面这手牌它就是有序的。
按照这个思想，令S，H，C，D为数的十位、百位、千位等，依次类推，十位大的无论各位都比十位小的大，我们先对个位进行排序，排序后再对十位排序，此时，个位的排序并没有打乱，依次类推，可以得到有序序列。
比如上面这扑克，全部按照牌力排序，最后再按照花色选出，就能得到上面这个样子的手牌，（说不定新睿就是这样做的）。
如对排序：
先对个位排序：（可以使用到队列）
然后有序列变为：
再对10位进行一次
有序列变为：111521325
再来一趟：111325521
这就是基数排序，代码我觉得他不会考，考了也就模拟以上过程即可，可能会需要用到队列，如果是对数排列，可以开一个0~9的队列组。
预览时标签不可点收录于话题#个上一篇下一篇