分段排序1.排序后得到两段数据同时为升（降）（1）后往前冒泡排序。思考：什么时候a(j)与a(j-1)要互换？a.当前（a(j)）是奇数
，前面（a(j-1)）是偶数时；b.当前与前面（a(j)与a(j-1)）都是奇数时，还要看值的大小，符合a(j).当前与前面（a(j)与a(j-1)）都是偶数时，还要看值的大小，符合a(j)-1)，并且两个数同奇偶什么时候不互换？当前为偶，前面为奇时。fori=1ton-1forj=ntoi+1st
ep-1ifa(j)mod2=1anda(j-1)mod2=0ora(j)mod2=a(j-1)mod
2anda(j)jnexti同样功能的语句书写，请参考《进阶题典作业手册》P177T12男生在前按身高升序，女生在后按身高升序：《进阶题典作
业手册》P176T7（对比不一样的判断手段）（2）选择排序。思路：双向排序。找与最小的奇数，与第1个互换，换出最大的偶数，与最
后一个互换。L=1:R=ndowhileL处通过引用函数，返回值为0时表示不存在要找的数，否则返回相应数所在的位置）fori=LtoRifk1<>0anda(i
)mod2=1anda(i)0anda(i)mod2=0anda
(i)>a(k2)thenk2=inextiifk1<>0thena(L)与a(k1)互换:L=L+1ifk2
<>0thena(R)与a(k2)互换:R=R-1loop（3）插入排序。只针对某种情况分析：当[1,i-1]已按要求
有序，准备将a(i)插入后保持有序。j继续往前找（j=j-1）的条件是（?处的条件）：tmp与a(j)同奇或同偶，并且tmpj)；或者：tmp为奇而a(j)为偶时tmp=a(i):j=i-1dowhile?j=j-1loop2.排序后得
到两段数据一升一降（1）后往前冒泡排序。a(j)a(j-1)a(j)与a(j-1)大小关系是否互换？奇奇a(j)换偶无要求互换偶奇不互换偶a(j)>a(j-1)互换fori=1ton-1forj=ntoi+1step-1if
a(j)mod2=1then‘当前为奇数ifa(j-1)mod2=0ora(j)n‘前面是偶数，或者比前面小（不管奇偶性）t=a(j):a(j)=a(j-1):a(j-1)=tendifelsei
fa(j-1)mod2=0anda(j)>a(j-1)thent=a(j):a(j)=a(j-1):a(j-1)
=tendifnextjnexti同样功能的语句书写，请参考《进阶题典作业手册》P177T10（冒泡排序）（2）选择排
序。思路：双向排序。i=1:j=ndowhileik=mnextmifa(k)mod2=1andk<>ithena(k)与a(i)互换:i=i+1ifa(k
)mod2=0andk<>jthena(k)与a(j)互换:j=j-1loop同样功能不同语句书写，请参考《进阶题典
作业手册》P173T2（3）插入排序（自主思考并表达出查找插入位置过程继续查找的条件）奇位升，偶位降k=1fori=1to
(n-1)\2forj=1ton-i2ifka(j)>ka(j+2)then互换k=-knextjnex
ti3.间隔排序奇位升，偶位升fori=1to(n-1)\2forj=1ton-i2ifa(j)>a(j+2)
then互换nextjnexti4.左右交替上升（下降）（以左右交替上升为例）思路1：冒泡排序，双向指针控制区间边界
，从两边往里有序，依次“往前冒－往后冒”交替执行冒泡过程，直到区间数据为1个时结束。第1趟，在区间[1,n]里，小的后往前冒，最小
的在第1位，再在[2,n]里小的往后冒，第2小的在第n位；第2趟，在区间[2,n－1]里，小的后往前冒，再在[3,n－1]里小的往
后冒；……k=1:start=1:end=8:flag=1dowhilek<=n-1fori=starttoend-
flagstepflagifa(i)>a(i+flag)thena(i)与a(i+flag)互换值end=end-fl
ag‘已有序的这头区间缩减1flag=-flag‘控制对比方向（当前与前面还是当前与后面）和区间缩减的变量k=k+1sta
rt与end互换值‘交换冒泡起始与终止nextiloopi=1:j=ndowhilei=j？fork=jtoi+1step-1‘小的往前冒ifa(k)i=i+1fork=itoj-1‘小的往后冒ifa(k)op思路2：冒泡排序，巧妙利用符号和计算、互换来自动控制区间和冒泡方向（2019.11杭州周边T11）思路3：选择排序。双向指针
，从中间依次向两边降序排序，最大的放中间，第2大放其右，第3大放其右，再右－左……直到全部有序。m=(1+n)\2‘n为奇数时
为正中心位置，n为偶数时，为一半偏左p=m:q=mfori=1ton-2ifimod2=1thenk=q+
1:q=q+1elsek=p-1:p=p-1endifpos=kforj=1tonifj>qanda(j)pos<>kthena(pos)与a(k)互换nexti5.基于环的排序，排序结果为：[min,n]再接着[1,min
-1]，呈升序排序，如图：思路：基于环的思想，以min为起点，min-1为终点，进行选择排序在[1,n]头尾相连的环中，指针i
向前走1步表示为i=(i+1-1)modn+1，即i=imodn+1，走k步为i=(i+k-1)modn+1；
往后走1步，则为i=(i-1+n-1)modn+1，往后走k步为i=(i-k+n+1)modn+1。在环里
的指针移动，一定要注意mod的使用。min=1fori=2ton‘先找到最小数所在的位置minifa(i)n)thenmin=inextii=minmodn+1‘i指向min的下一个位置，即准备放第2小的数的位置dowh
ilei<>(min-1+n-1)modn+1‘min-1表示待排序数的最末尾处，当min=1时，为nk=ij=imodn+1‘j遍历的区间是:i的下一个开始到min-1dowhilej<>minifa(j)ithena(i)与a(k)互换i=imodn+1‘当前的i处已有序，i往前移一步loop丽中信息4/4 |
|
