基本介紹
- 中文名：奇偶排序
- 外文名：Parity sorting
- 思路：在數組中重複兩趟掃描
- 相關著作：《Java數據結構和算法》
詳細說明
和冒泡排序法一樣，奇偶排序的時間複雜度為O(N^2)。
《Java數據結構和算法》中寫道：
奇偶排序實際上在多處理器環境中很有用，處理器可以分別同時處理每一個奇數對，然後又同時處理偶數對。因為奇數對是彼此獨立的，每一刻都可以用不同的處理器比較和交換。這樣可以非常快速地排序。
Java代碼
1 public void oddEvenSort(int[] array){
2 for (int i = 0; i < array.length; i += 2){
3 int j = 0;
4 scan(array, j);
5 j = 1;
6 scan(array, j);
7 }
8 }
9
10 private void scan(int[] array, int j) {
11 while (j < array.length - 1){
12 if (array[j] > array[j + 1]){
13 swap(array, j, j + 1);
14 }
15 j += 2;
16 }
17 }
18
19 private static void swap(int[] array, int index1, int index2) {
20 int temp = array[index1];
21 array[index1] = array[index2];
22 array[index2] = temp;
23 }
後來有朋友提出建議，我小小的改動了一下，對隨機數組排序的效率略有提高：
Java代碼
24 public static void oddEvenSort(int[] array) {
25 boolean unsorted = true;
26 while (unsorted) {
27 unsorted = false;
28 int i = 1;
29 boolean oddUnsorted = scan(array, i);
30 i = 0;
31 boolean evenUnsorted = scan(array, i);
32 unsorted = oddUnsorted || evenUnsorted;
33 }
34 }
35
36 private static boolean scan(int[] array, int i) {
37 boolean unsorted = false;
38 while (i < array.length - 1) {
39 if (array[i] > array[i + 1]) {
40 swap(array, i, i + 1);
41 unsorted = true;
42 }
43 i += 2;
44 }
45 return unsorted;
46 }
47
48 private static void swap(int[] array, int index1, int index2) {
49 int temp = array[index1];
50 array[index1] = array[index2];
51 array[index2] = temp;
52 }
