經典算法題每日演練——第二十二題 奇偶排序

　　這個專題因為各種原因好久沒有繼續下去了，MM吧。。。你懂的，嘿嘿，不過還得繼續寫下去，好長時間不寫，有些東西有點生疏了，

這篇就從簡單一點的一個“奇偶排序”說起吧，不過這個排序還是蠻有意思的，嚴格來說複雜度是O(N2)，不過在多核的情況下，可以做到

N2 /(m/2)的效率，這裡的m就是待排序的個數，當m=100，複雜度為N2 /50，還行把，比冒泡要好點，因為重點是解決問題的奇思妙想。

    下面我們看看這個算法是怎麼描述的，既然是奇偶，肯定跟位數有關了

1：先将待排序數組的所有奇數位與自己身後相鄰的偶數位相比較，如果前者大于後者，則進行交換，直到這一趟結束。

2：然後将偶數位與自己身後相鄰的奇數位相比較，如果前者大于後者，則進行交換，直到這一趟結束。

3：重複1，2的步驟，直到發現無“奇偶”，“偶奇” 交換的時候，就認為排序完畢，此時退出循環。

　　由于網速問題，下載下傳幾次freehand都失敗了，我就手寫個例子吧。

① 待排序數組：                                            9  2  1  6  0  7

② 所有奇數位與身後的相鄰的偶數位比較交換       2  9  1  6  0  7

③ 所有偶數位與身後的相鄰的奇數位比較交換       2  1  9  0  6  7

④ 所有奇數位與身後的相鄰的偶數位比較交換       1  2  0  9  6  7

⑤ 所有偶數位與身後的相鄰的奇數位比較交換       1  0  2  6  9  7

⑥ 所有奇數位與身後的相鄰的偶數位比較交換       0  1  2  6  7  9

我們可以看到，經過5趟排序後，我們的數組就排序完畢了，從圖中②可以看到，如果每個線程分攤一個奇數位，那交換是不是隻要

一次就夠了呢，可以看到這個算法在多核處理下面還是很有優勢的。

最後的運作代碼：