分段排序讲解

PAGE1分段排序1.排序后得到两段数据同时为升（降）（1）后往前冒泡排序。思考：什么时候a(j)与a(j-1)要互换？a.当前（a(j)）是奇数，前面（a(j-1)）是偶数时；b.当前与前面（a(j)与a(j-1)）都是奇数时，还要看值的大小，符合a(j)<a(j-1)c.当前与前面（a(j)与a(j-1)）都是偶数时，还要看值的大小，符合a(j)<a(j-1)b与c可以统一为：当a(j)<a(j-1)，并且两个数同奇偶什么时候不互换？当前为偶，前面为奇时。fori=1ton-1fori=1ton-1 forj=ntoi+1step-1 ifa(j)mod2=1anda(j-1)mod2=0ora(j)mod2=a(j-1)mod2anda(j)<a(j-1)thent=a(j):a(j)=a(j-1):a(j-1)=tendif nextjnexti同样功能的语句书写，请参考《进阶题典作业手册》P177T12男生在前按身高升序，女生在后按身高升序：《进阶题典作业手册》P176T7（对比不一样的判断手段）（2）选择排序。思路：双向排序。找与最小的奇数，与第1个互换，换出最大的偶数，与最后一个互换。L=1:R=ndowhileL<RL=1:R=ndowhileL<R k1指向[L,R]里任意一个奇数:k2指向[L,R]里任意一个偶数（此处通过引用函数，返回值为0时表示不存在要找的数，否则返回相应数所在的位置） fori=LtoR ifk1<>0anda(i)mod2=1anda(i)<a(k1)thenk1=i ifk2<>0anda(i)mod2=0anda(i)>a(k2)thenk2=i nexti ifk1<>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)同奇或同偶，并且tmp<a(j)；或者：tmp为奇而a(j)为偶时tmp=a(i):j=i-1j继续往前找（j=j-1）的条件是（?处的条件）：tmp与a(j)同奇或同偶，并且tmp<a(j)；或者：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-1)互换偶无要求互换偶奇不互换偶a(j)>a(j-1)互换fori=1ton-1fori=1ton-1 forj=ntoi+1step-1 ifa(j)mod2=1then‘当前为奇数ifa(j-1)mod2=0ora(j)<a(j-1)then‘前面是偶数，或者比前面小（不管奇偶性）t=a(j):a(j)=a(j-1):a(j-1)=t endif elseifa(j-1)mod2=0anda(j)>a(j-1)then t=a(j):a(j)=a(j-1):a(j-1)=tendif nextjnexti同样功能的语句书写，请参考《进阶题典作业手册》P177T10（冒泡排序）（2）选择排序。思路：双向排序。i=1:j=ni=1:j=ndowhilei<j k=i form=i+1toj ifa(m)<a(k)thenk=m nextm ifa(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)\2 forj=1ton-i*2 ifk*a(j)>k*a(j+2)then互换k=-k nextjnexti3.间隔排序奇位升，偶位升fori=1to(n-1)\2奇位升，偶位升fori=1to(n-1)\2 forj=1ton-i*2 ifa(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-1k=1:start=1:end=8:flag=1dowhilek<=n-1fori=starttoend-flagstepflagifa(i)>a(i+flag)thena(i)与a(i+flag)互换值end=end-flag‘已有序的这头区间缩减1flag=-flag‘控制对比方向（当前与前面还是当前与后面）和区间缩减的变量k=k+1start与end互换值‘交换冒泡起始与终止nextiloopi=1:j=ndowhilei<j‘思考：此处为什么不写成i<=j？fork=jtoi+1step-1‘小的往前冒ifa(k)<a(k-1)then互换nextki=i+1fork=itoj-1‘小的往后冒ifa(k)<a(k+1)then互换nextkj=j-1loop思路2：冒泡排序，巧妙利用符号和计算、互换来自动控制区间和冒泡方向（2019.11杭州周边T11）思路3：选择排序。双向指针，从中间依次向两边降序排序，最大的放中间，第2大放其右，第3大放其右，再右－左……直到全部有序。m=(1+n)\2m=(1+n)\2‘n为奇数时为正中心位置，n为偶数时，为一半偏左p=m:q=mfori=1ton-2ifimod2=1thenk=q+1:q=q+1elsek=p-1:p=p-1endifpos=kforj=1tonifj<porj>qanda(j)<a(k)thenk=j‘当前已有序的区间是[p,q-1]或[p+1,q]nextjifpos<>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=1min=1fori=2ton‘先找到最小数所在的位置minifa(i)<a(min)thenmin=inextii=minmodn+1‘i指向min的下一个位置，即准备放第2小的数的位置dowhilei<>(min-1+n-1)modn+1‘min-1表示待排序数的最末尾处，当m