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