C++排序算法总结.pdf

《C++排序算法总结.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、(1)2分法查找(2)插入排序(稳定)(3)冒泡排序(稳定)(4)基数排序(5)归并排序(6)直接选择排序(不稳定)(7)快速排序(不稳定)(8)希尔排序(不稳定)(9)堆排序=================================================(1)2分法查找有序连续内存templateintbsearch(Cvalue,iteratorbegin,iteratorend){iteratormid=&begin[(end-begin)/2];if(*mid==value)returnbegin-mid;else{i

2、f(begin==end)return-1;if(value<*mid)returnbsearch(value,begin,mid);elsereturnbsearch(value,++mid,end);}return-1;}intmain(void){intbuf2[]={1,3,9,10};intidx=bsearch(1,buf2,&buf2[3]);if(idx!=-1)printf("v=%d,pos=%d",buf2[idx],idx);elseprintf("notfound");return0;}(2)插入排序(稳定

3、)----当然，可以用折半插入排序来提高性能templatevoidisort(Tbegin,size_tlength){size_tl=length*sizeof(*begin);Ts=(T)malloc(l);s[0]=begin[0];for(intb=1;b0;--k){s[c+k]=s[c+k-1];1}break;}}s[c]=begin[b];}memcpy(begin,s,l);del

4、ete[]s;}main(...)shortbuf2[]={11,3,9,10,7,6,15,2};isort(buf2,8);for(inti=0;ivoidbubsort(Ts,size_tlen){for(inti=0;is[m+1]){inttmp=s[m];s[m]=s

5、[m+1];s[m+1]=tmp;op=1;}}if(!op)return;}}(4)基数排序:O(nlog(r)m)其中r为所采取的基数，而logr(n)=m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。合理设计r和m的值，可以得到最有解。它利用了每次比较以后得到的历史信息。需要根据需求具体设计，没有通用形式，必须根据具体问题的信息具体设计，例如扑克牌排序等。它的核心思想是利用数据的某方面的特定信息。下面的例子是排序如果各2位正数，使用了10个桶#include#include#include

6、m>#include#include//Radix,Bucketsort2#defineDEMICAL10intbuk[DEMICAL][DEMICAL+1];//bucketshortt[DEMICAL];//top;int*p;voidgetb(size_tb){printf("t[b]=%d,",t[b]);if(t[b]==0){printf("buk[%d]isempty",b);return;}else{for(inti=1;i<=t[b];++i){printf("buk[%d,%d]=%d",b,i,

7、buk[b][i]);*p++=buk[b][i];}}}voidgetall(){for(inta=0;a

8、){//lowdemicalinthv