奇偶排序是一個比較有個性的排序,基本思路是奇數列排一趟序,偶數列排一趟序,再奇數排,再偶數排,直到全部有序
舉例吧,
待排數組
|
1
|
[6 2 4 1 5 9] |
第一次比較奇數列,奇數列與它的鄰居偶數列比較,如6和2比,4和1比,5和9比
|
1
|
[6 2 4 1 5 9] |
交換后變成
|
1
|
[2 6 1 4 5 9] |
第二次比較偶數列,即6和1比,5和5比
|
1
|
[2 6 1 4 5 9] |
交換后變成
|
1
|
[2 1 6 4 5 9] |
第三趟又是奇數列,選擇的是2,6,5分別與它們的鄰居列比較
|
1
|
[2 1 6 4 5 9] |
交換后
|
1
|
[1 2 4 6 5 9] |
第四趟偶數列
|
1
|
[1 2 4 6 5 9] |
一次交換
|
1
|
[1 2 4 5 6 9] |
Java實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
static void oddEvensort(int[] ary) { //奇偶排序 boolean flag = true; while (flag) { boolean odd = false, even = false; for (int i = 0; i < ary.length - 1; i+=2) { if (ary[i] > ary[i + 1]) { ary[i] = ary[i + 1] + 0 * (ary[i + 1] = ary[i]); odd = true; } } for (int i = 1; i < ary.length - 1; i+=2) { if (ary[i] > ary[i + 1]) { ary[i] = ary[i + 1] + 0 * (ary[i + 1] = ary[i]); even = true; } } flag = odd || even; //若為false，表示不論奇偶序列，一個符合條件的比較都沒有 } } |
上面的 flag = odd || even; 有一個為true，表示還在交換， 那么最后只有 都為 false時，flag才為false。
改寫成 flag = odd && even; 有一個為false，則不再整體循環了。跟冒泡排序一樣，可以減少最后一次內層循環。
