下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第九排 三 52,49,80,36,14,58,61,23,97,14,23,36,49,52,58,61,75,80,假设含n个记录的序列为R1,R2Rn其相应的关键字序列为K1,K2,Kn它们之间存在着这样一个关系:{Rp1,Rp2,…,Rpn的操作称作排序二 排序和外部排 三 排序的方基于不同的“扩大度的方法,排序方法大致可分类交换类选择类归并类其它方法#defineMAXSIZE1000typedefintKeyType;typedefstruct 关键字InfoTypeotherinfo;其它数据 记录类typedefstruct r[MAXSIZE+1];//r[0]闲置 //顺序表长 顺序表类类个记录“”到有序序列中,9.排序一趟直 有序序有序序列R[1..i-无序序列无无序序列有序序列 R[1..j].keyR[i].key<R[j+1..i-将R[j+1..i-1]中的所有记录均 不同的具体实现方法导致不同的算法描直接排序(基于顺序查找)折半排序(基于折半查找)表排序(基于链表)排序(基于逐趟缩小增量一、直 排利用“顺序查找”实现
R[0] for(j=i-1;R[0].key<R[j].key;-- 位置为j对于在查找过找到的那些关键for(j=i-1;R[0].key<R[j].key;--j);R[j+1]=R[j]
i2,3,…,for(i=2;i<=n;++iif(R[i].key<R[i-{在R[1..i-1]中查找R[i]的 R[i];}voidInsertionSort(SqList&L)//对顺序表L作直 排序for(i=2;i<=L.length;++iif(L.r[i].key<L.r[i-1].key)L.r[0]=L.r[i]; for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j]; //记录后移L.r[j+1] }}//对于直 排序最好的情况(关键字在记录序列中顺序有序n
1i2
n n的情况(关键字在记录序列中逆序有序nnn
ii2
(n
2)(n2
(ii2
(n
4)(n2
二、折 排R[1..i-1]实现“在R[1..i-1]中查找R[i]的位置”,如此实现的排序为折半插voidBiInsertionSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]= L.r[i]暂存到在L.r[1..i-1]中折半查 位置for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j]; 记录后移L.r[high+1]=L.r[0];}//}//low= high=i-while(low<=high)m //if(L.r[0].key<highm- elselowm+1; }例如
位置
三、表排为了减少在排序过进行的采用的结构。利用静态链表静态链表类型说明如下#defineSIZE100 typedefstruct{RcdTyperc; //typedefSLNoder[SIZE]; intlength; }SLinkListType;// 排序基本思列 结构32”至“n”的分量(结点
初 i=i=i=
候j=0指k候j=0指k间 i=i=kji=i=jk结结voidLInsertionSort(ElemSL[],int//对记录序列SL[1..n]作 排SL[0].key=MAXINTSL[0].next=1;SL[1].next=for(i=2;i<=n;++ifor(j=0,k=SL[0].next;SL[k].key<=SL[i].key;j=k,k=SL[k].next){SL[j].next=i;SL[i].next=k;//结点 }// i=
i=
i=
voidArrange(ElemSL[],intn)p //pfor(i=1;i<n;++i)while(p<i)p=q qif(p!=i)SL[p]←→SL[i];交换记录,使第iSL[i].next }p= p为找第i+1个记录作准备,录}}//四 排序(又称缩小增量排序 具体做法为序列进行排序。例如:将n个记录分成d个子序列{R[1],R[1+d],R[1+2d],…,R[1+kd]{R[2],R[2+d],R[2+2d],…,R[2+kd]…{R[d],R[2d],R[3d],…,R[kd],R[(k+1)d]其中,d称为增量,它的值在排序过程序减为1。9 排序,设增量d9第二 排序,设增量d=9 排序,设增量d=9voidS Insert(SqList&L,intdk){for(i=dk+1;i<=n;++i)if(L.r[i].key<L.r[i-dk].key)L.r[0] //暂存在for(j=i-dk;j-L.r[j+dk]=L.r[j];//记录后移,查 位L.r[j+dk]= 9}//
void Sort(SqList&L,intdlta[],int //增量为dlta[] for(k=0;k<t; Insert(L, }//
2t-
10
log2(n
dlta[k]13t-k-kt
(2n 2注意!最后一次增量必须为快速排序一、起泡排二、一趟快速排三、快速排四、快速排序的时间分一、起泡排假设在排序
无序序列R[1..n-比较相邻记录,将键字最大的记录交
有序序列R[n-in-i+1的位置
R[n-1趟起泡排序的结果2趟起泡排序的结果3趟起泡排序的结果void emR[],intn)i=lastExchangeIndex=if(R[j+1].keylastExchangeIndex=if(R[j+1].key<R[j].key)Swap(R[j],lastExchangeIndexj;//}for(j=1;j<i;ilastExchangeIndex;本趟进行过交换}//}//
//最后一个记录的位起泡排序的结束条件最后一趟没有进行“交换记录 13 9forfor(j=1;j<i;j++)if(R[j+1].key<R[j].key)时间分最好的情况(关键字在记录序列中顺序有序只需进行一趟起泡“比较”的次数n-
“移动”的次数0的情况(关键字在记录序列中逆序有序需进行n1趟起泡“比较”的次数 “移动”的次数 n(n
3n(n
(iin
1)2
3(iin
1)2R[j].key≤R[i].key≤ (i+1≤j≤t)例
493658619775
R[s]=52为枢R[high].key要求R[high].key≥枢轴的关键字R[low].key要求R[low].key≤枢轴的关键字可见,经过“一次划分52,49,80,36,14,58,61,97,23,调整为:23,49,1436,(52)58,61,97,80在调整 ,设立了两个指针:和highs和highR[high].key≥52,和R[low].key≤52,否intPartitionRedType&Rintlowinthigh{pivotkey=R[low].key;//用子表的第一个记录做枢轴while(low<high);//从表的两端交替向中间扫描{while(low<high&&--R[low]←→R[high];;//将比枢轴小的记录交换while(low<high&&R[low]←→R[high];//将比枢轴大的记录交换到高}return //返回枢轴所在位}//intPartition(RedTypeR[],intlow,inthigh)R[0R[low];pivotkeyR[low].key;枢while(low<high)while(low<high&& 从右向左搜R[low]=while(low<high&& 从左向右搜R[high]=}R[low]= return}//三、快速排无序的记录序列无序的记录序列一次划voidQSort(RedType&R[],ints,intt)//对记录序列R[s..t]进行快速排if(s<t-1) 长度大于pivotloc=Partition(R,s,R[s..t进行一次划QSort(R,s,pivotloc-//对低子序列递归排序,pivotloc是枢轴位QSort(R,pivotloc+1,t);对高子序列递归排}}//Qsort时,待排序记录序列的上、下界分别为1和L.length。voidQuickSort(SqList&L)QSort(L.r,1,}//假设i=k,则对n个记录进行快排所需时间:T(n)=Tpass(n)+T(k-1)+T(n-其中Tpass(n)n个记录进行一次划分k1n中任意一值的可能性相Tavg(n)
Cn
navgnknavg
Tavg(n
k)Tavg
(2
2c)(n
ln(n
结论:快速排序的时间复杂度为先对R(s).key,R(t).key和R[(s+t)/2].key, 堆排序堆排序假设排序 ,待排记录序列的状态为有序序列R[1..i-无序无序序列
从中选关键字最小的简单选择排序voidSelectSort(ElemR[],intn)对记录序列R[1..n]作简单选择排序for(i=1;i<n;++i)ij=SelectMinKey(R,在R[i..n]if(i!=j)i}}//对n个记录进行简单选择排序,所需进行的关键字间的比较次数n
n(n(ni
i)2最大值为3(n-1)堆是满足下列性质的数列{r1r2
(小顶堆
(大顶堆r r 2i 2i例如{12,36,27,65,40,34,98,81,73,55,
是小顶{12362765401498817355 r2irir2i+1ri的右孩子 例如
不是例如{40,55,49,73,12,27,98,81,64,36{98,81,49,73,36,27,40,55,64,1298{12,81,49,73,36,27,40,55,64,98
{81,73,49,64,36,27,40,55,12,98voidHeapSort(HeapType&H)对顺序H进行堆排for( --iHeapAdjustH.ri,H.length 建大顶for(i=H.length;i>1;--i)//将堆顶记录和当 排序子序//H.r[1..i]中最后一个记录相互交换HeapAdjust(H.r1i-1);H.r[1进行筛选}}//typedefSqList堆堆例如
9812进行互换之后,它就不voidHeapAdjust(RcdType&R[],ints,int 已知R[s..m]中记录的关键字除R[s之外rc //forj=2*sj<=mj*=2j初值指向左孩}R[s]=rc;//将调整前的堆顶记 到s位}//if(j<m&&R[j].key<R[j+1].key)//左/右“子树根”之间先进行相互比令j指示关键字较大记录的位if(rc.key>=R[j].key)//再作“根”和“子树根”之间的比较若“>=”成立,则说明已找rc的入位置s,不需要继续往下调R[s]= s=//否则记录上移,尚需继续往下调例如将一个无序序列建成一个堆(初始堆)的方法筛选过程的算法为从最后一个非叶结点开始,逐步向根结点,反复进行“筛选”过程,使其结点元素的关键字大于左右孩子结点的关键字。最后一个非叶结点怎么求已知待排序序列数据元素个数为最后一个非叶结点的孩子结点一定是最后一个结点,则2i=n或者则堆排序voidHeapsort(Sqlist{Hfor(i=H.length/2;i>0;--HeapAdjust(H,i,H.length);//将H.r[1..H.length]建成大顶for(i=H.length;i>1;--{ 排序子序Hr[1..iHeapadjust(H,1,i-1)//将H.r[1..i-1}}堆排序的时间复杂度分析对深度为k的堆,“筛选”所需进行的关键字n个关键字,建成深度为h(=log2n+1)的堆,所需进行的关键字比较的次数至多4n;调整“堆顶”n-1次,总共进行的关键2(log2(n-1)+log2(n-2)+…+log22)<归并排序归并排序的过程基于下基本思想进行子序列“归并一个有序在排序中,通常采用的是2-路有序子序列 有序子序
这个操作对顺序表而言,是轻而易举的voidMerge(RcdTypeSR[],RcdTypeinti,intm,intn)将有序的记录序列SR[i..m//归并为有序的记录序列for(j=m+1,k=i;i<=m&&j<=n; //将SR中记录由小到大地并入TRif(SR[i].key<=SR[j].key)TR[kSR[i++];elseTR[k]=SR[j++]; }//if(i<=m)TR[k..n]=//将剩余的 到if(j<=n)TR[k..n]=//将剩余的 到R[s..t] 52,23, 36,68, (s=1,[52,23, [36,68,[52, [36,[
[23,[23,52,
[36,[14,36,[14,23,36,52,68,80voidMsort(RcdTypeRcdType&TR1[],ints,intt)将SR[s..t]归并排序为if(s==t) }}//m=//将SR[s..t]平分为SR[s..m]和Msort(SR,TR2,s,递归地将SR[s..m]归并为有序的TR2[s..m]Msort(SR,TR2,m+1,t);//递归地SR[m+1..t]归并为有序的Merge(TR2,TR1,s,m,//将TR2[s..m]和TR2[m+1..t]归并到voidMergeSort(SqList&L)L作2-MSort(L.r,L.r,1,}//n个记录进行归并排序的O(n),总共需进行log2n趟。基数排序序”的排序算法。n个记录的序列R1,R2对关键字(Ki0Ki1,…,Kid-1有序对于序列中任意两个记录Ri和Rj(1≤i<j≤n)都满足下列(词典)有序关系:(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-其中: 被称为“最主”位关键Kd- “ 优先MSD(MostSignificant(LeastSignificant先对K0进行排序K0后,分别对K1进行排序 先对Kd-1进行排序,然后对Kd-2 键字K0排序完成为止。 无序序对K2排对K1排对K0排{209,386,768,185,247,606,230,834,539首先按“个位数”取值分别为019“分配10组,之后按09的顺序将它们“收集”在一起;然后按其“十位数”取值分别为01“分配10组,之后再按从09的顺序将它们“收集”在一起;最后按其“百位数”重复一遍上述操作 2.“分按当前“关键字位”所取值,将记录分配到不同的“链队列”中,每个队列中记录的“关键字位”相同;4.对每个关键字位均重23两步进行第一次分f[9]→369→239→139[9]进行第一次收p→230→367→167→237→138进行第二次分32302313239139[3636167368[6
进行第三次分9←[进行第三次收集之后便得到记录的有序序提醒注意法Arrange将它调整为有序表。其中:分配为#defineMAX_NUM-OF-KEY8//关键码项数最大#define 10//关键码基数,此时为十进制整数的基#defineMAX_SPACE1000//分配的最大可利 空typedef keys[MAX_NUM_OF_KEY];/*关键码字 otheritems;//其它字 next;//指针字}SLCell;//表结点类typedefSLCellr[MAX_SPACE]//静态链表的可利用空间,r[0]为头结 keynum;//关键码个 renum;//当前表中记录}SLList;//链表类分配算voidDistribute(SLCell&r,inti,ArrType&f,ArrType{//静态链表L的r域中记录已按(kye[0],keys[1],…,keys[i-1])有序。本算法按第i个关键码ey[]建立RDX个子表,使同一子表中的记录的[]相同,f[0…RDX-1]和0…RDX-1]分别指向各子表的第一个和最后一个记录for(j=0;j<RADIX;j+f[j]=0子表初始化为空{//ord将记录中第i个关键 到[0…RADIX-if(!f[j])elser[e[j]].next=p;//e[j]指向字表表尾元素的位序e[j]=p;//将p所指的结点 }}第i9←[f[3]→367...
收集算voidCollect(SLCell&r,inti,ArrTypef,ArrType{/*本算法按keys[i]自小到大地将f[0…RADIX-1]所指各子表依次成一个for(j=0;!f[j];j=succ(j));//找第一个非空子表,succ为求后继函数r[0].next=f[j];t=e[j]//r[0].next指向第一个非空子表中第一个结点{for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j));//找下一个非空子表if(f[j]){r[t].next=f[j];t=e[j];}// }r[t].next=0;//t指向最后一个非空子表中的最后一个}voidRadixSort(SLList{//L是采用静态链表表示的顺序对L作
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 电子电路逻辑布线工岗中技术基础考核试卷含答案
- 平地机操作工岗中实操评优考核试卷含答案
- 2026年齐齐哈尔高等师范专科学校高职单招笔试物理历年参考题库含答案解析
- 巧克力成型工QC管理竞赛考核试卷含答案
- 2026年陕西财经职业技术学院高职单招笔试物理历年参考题库含答案解析
- 2026年闽北职业技术学院高职单招笔试语文历年参考题库含答案解析
- 2026年长春职业技术学院高职单招笔试化学历年参考题库含答案解析
- 2026年重庆旅游职业学院高职单招笔试职业适应性测验历年参考题库含答案解析
- 2026年重庆工业职业技术学院高职单招笔试英语历年参考题库含答案解析
- 2026年郑州理工职业学院高职单招笔试英语历年参考题库含答案解析
- 快消品特殊渠道开发课件
- 12J9-1 室外工程图集
- 嘉庚精神代代传
- ReFi动态养老财务模型目标基准点及养老财务相关知识测试题附答案
- GB/T 29911-2025汽车租赁服务规范
- 北京大学2025年推免研究生申请个人陈述范文
- 贝壳租房合同协议
- 风机降噪方案
- 多学科交叉融合驱动下机器人导论课程实践与思考
- ABBdcs组态课件CONDUCTORVMS操作
- 求职OMG-大学生就业指导与技能开发智慧树知到期末考试答案章节答案2024年中国海洋大学
评论
0/150
提交评论