数据结构排序小结

《数据结构排序小结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构排序算法总结数据结构排序这章内容比较经典，都是一些很好的算法，将來很町能会用得到，总结一下，加深一下印彖。文章篇幅有点大，请点击查看更多，下面是跳转链接：_、插入排序二、交换排序三、选择排序四、归并排序五、垒数排序插入排序1）氏接插入排序1）口泡排序1）简单选择排序2）折半插入排序2）快速排序2）堆排序3）希尔排序123456789101112}//InscrtSort1）直接插入排序算法演示返回H录时间复杂度：平均情况一。（卍）最坏情况_0（n2）辅助空间：0（1）稳定性:稳定voidInsertSort(SqList&L)

2、{//对顺序表L作直接插入排序。inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.rkey)){//〃〈〃时,需将L.r[i]插入有序子表L.r[O]=L.r[i];//复制为哨兵for(j=i-l;LT(L.r[0].key,L.r[j].key);—j)L.r[j+l]=L.r[j];//记录后移L.r[j+l]=L.r[0];//插入到正确位置2）折半插入排序返回目录时间复杂度：平均情»i—0（n2）稳定性：稳定?■12345voidBlnscrtSort(SqList&L){/

3、/对顺序表L作折半插入排序。inti,j,high,low,m;for(i=2;i<=L.length;++i){L.r[O]=L.r[i];//将L.r[i]暂存到L.r[O]678910low=1;high=i~l;while(low<=high){//在r[low..high]屮折半查找冇序插入的位置m=(low+high)/2;//折半if(LT(L.r[0].key,L.r[m].key))high=m-1;//插入点在低半区elselow二m+1;//插入点在高半区11}12for(j=i-l;j>二high+1;--j)

4、Lr[j+1]=L.r[j];//记录后移13L.r[high+1]=L.r[0];//插入14}15)//BTnsertSort3)希尔排序算法演示返冋冃录时间复杂度：理想情O(nlog2n)最坏情况一0(严)稳定性：不稳定12345678910111213141516171819voidShelllnsert(SqList&L,intdk){//对顺序表L作一趟希尔插入排序。木算法対算法10.1作了以下修改：//1•前后记录位置的壇量是dk,而不是1；//2.讥0]只是暂存单元，不是哨兵。当jUO时，插入位置已找到。inti,j;

5、for(i=dk+l;i<=L.1ength;++i)if(LT(L.r[i].key,L.r[i-dk].key)){//需将L.r[i]插入有序增量子表L.r[0]二L.r[i];//暂存在L.r[0]for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//记录后移，查找插入位置L.r[j+dk]=L.r[0];//插入}}//Shel1InsertvoidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0.

6、.t-l]对顺序表L作希尔排序。for(intk=O;k=i;j-

7、-)//对当前无序区R[i・・n]自下向上扫描if(R[j+1]・key2)快速排序算法演示返回目录时间复杂度：平均情O(nlog2n)最坏情况一0(廿)辅助空间：O(log2n)稳定性：

8、不稳定9■12345678910111213141516171819202122232425262728intPartition(SqList&L,intlow,inthigh){//交换顺序表L中子序列L.r[low.