分段排序讲解

分段排序排序后得到两段数据同时为升降

1.1n后往前冒泡排序1思考什么时候与要互换？aj aj.l当前是奇数,前面是偶数时；a.aj aj-lb.当前与前面aj与aj・l都是奇数时,还要看值的大小,符合ajaj-lc.当前与前面aj与aj-l都是偶数时，还要看值的大小，符合与可以统一为当并且两个数同奇偶ajaj.l9b cajaj-l,什么时候不互换？当前为偶，前面为奇时for i=l to n-1for j=n toi+1step-1if aj mod2=1and aj-l mod2=0or ajmod2=aj-l mod2and ajaj-l thent=aj:aj=aj-l:aj-l=tend ifnext jnext i同样功能的语句书写，请参考《进阶题典作业手册》P177T12男生在前按身高升序，女生在后按身高升序《进阶题典作业手册》对比不一样的判断手段Pl76T7选择排序思路双向排序找与最小的奇数，与第个互换，换出最大的偶数，与最后一个互换21L=1:R=ndo whileLR指向［］里任意一个奇数指向［］里任意一个偶数kl L,R k2L,R此处通过引用函数，返回值为时表示不存在要找的数，否则返回相应数所在的位置0for i=L toRif kl0and ai mod2=1and aiakl then kl=iif k20and ai mod2=0and aiak2then k2=inext i与互换:if kl0then aLakl L=L+1与互换:if k20thenaR ak2R=R-1loop插入排序只针对某种情况分析当］已按要3i-1求有序，准备将插入后保持有序aitmp=ai:j=i-l dowhile继续往前找的条件是？处的条件:与同奇j=j-l jtmp ajloop或同偶，并且tmpaj；或者tmp为奇而aj为偶时排序后得到两段数据一升一降

2.后往前冒泡排序1与大小关系是否互换？aj aj-l ajaj-l奇互换ajaj-l奇偶无要求互换奇不互换偶偶互换ajaj-lfor i=l ton-1for j=n toi+1step-1，当前为奇数if ajmod2=1then前面是偶数，或者比前面小不管奇偶性if aj-l mod2=0or ajaj-l thent=aj:aj=aj-l:aj-l=tend ifelseifaj-l mod2=0and ajaj-l thent=ajaj=aj-l:aj-l=tend ifnextjnext i同样功能的语句书写，请参考《进阶题典作业手册》冒泡排序P177T10

（2）选择排序思路双向排序左右交替上升（下降）

4.i=l:j=ndo whileijk=ifor m=i+l tojif amakthen k=mnext m与互换:if akmod2=1and koithen akai i=i+l与互换:if akmod2=0and kojthen akaj j=j-lloop同样功能不同语句书写，请参考《进阶题典作业手册》P173T2

（3）插入排序（自主思考并表达出查找插入位置过程继续查找的条件）奇位升，偶位降

3.间隔排序k=lfor i=l ton-l\2奇位升，偶位升for j=l ton-i*2互换for i=l to（n-l）\2if k*ajk*aj+2thenfor j=l ton-i*2k=-kif ajaj+2then互换nextjnextj nextinext i1n1n（以左右交替上升为例）思路1冒泡排序，双向指针控制区间边界，从两边往里有序，依次“往前冒一往后冒”交替执行冒泡过程，直到区间数据为个时结束1第趟，在区间［］里，小的后往前冒，最小的在第位，再在［］里小的往后冒，第小的在第位;1l,n12,n2n第趟，在区间［］里，小的后往前冒，再在［］里小的往后冒;22,n—13,n—1k=l:start=l:end=8:flag=l•…Odo whilek=n-li=l:j=nfor i=start toend-flag stepflag，思考此处为什么不写成〈二do whileij ij⑴与互换值if aiai+flag then a ai+flag小的往前冒for k=j toi+1step-1if akak-l已有序的这头区间缩减end=end-flag1互换then控制对比方向当前与前面还是当flag=-flagnext k前与后面和区间缩减的变量i=i+lk=k+l小的往后冒互换fork=itoj-l ifakak+lthen与互换值’交换冒泡起始与终止start endnextk j=j-lnext ilooploop介思路2冒泡排序，巧妙利用符号和计算、互换来自动控制区间和冒泡方向（

2019.11杭州周边T11）思路3选择排序双向指针，从中间依次向两边降序排序，最大的放中间，第2大放其右，第3大放其右，再右一左……直到全部有序（）/为奇数时为正中心位置，为偶数时，为一半偏左m=l+n\2np=m:q=mfor i=l ton-2if i mod2=1thenk=q+l:q=q+lelsek=p-l:p=p-lend ifpos=k基于环的排序，排序结果为［］再接着［］呈升序排序，如图:

5.min,n l,min-l,思路基于环的思想，以为起点，为终点，进行选择排序min min-1在［］头尾相连的环中，指针向前走步表示为即走步为l,n i1i=i+1-1mod n+1,i=imod n+1,k i=i+k-l modn+1；往后走1步,则为i=i-l+n-1mod n+1,往后走k步为i=i-k+n+1modn+1在环里的指针移动，一定要注o意的使用modmin=l先找到最小数所在的位置for i=2tonminif aiaminthen min=inext i指向的下一个位置，即准备放第小的数的位置i=min modn+11min2表示待排序数的最末尾处,当时，为do whileiomin-l+n-l modn+1min-1min=l nk=i」遍历的区间是:的下一个开始到j=imodn+1i min-1do whilejominif ajakthen k=jj=jmodn+1z j往前移一步loop⑴与互换if koithenaak当前的处已有序，往前移一步i=imodn+1i iloop。