本文實例講述了java交換排序之奇偶排序實現方法。分享給大家供大家參考。具體如下：
奇偶排序，或奇偶換位排序，或磚排序，是一種相對簡單的排序算法，最初發明用于有本地互連的并行計算。這是與冒泡排序特點類似的一種比較排序。
該算法中，通過比較數組中相鄰的（奇-偶）位置數字對，如果該奇偶對是錯誤的順序（第一個大于第二個），則交換。下一步重復該操作，但針對所有的（偶-奇）位置數字對。如此交替進行下去。
處理器數組的排序
在并行計算排序中，每個處理器對應處理一個值，并僅有與左右鄰居的本地互連。所有處理器可同時與鄰居進行比較、交換操作，交替以奇-偶、偶-奇的順序。該算法由Habermann在1972年最初發表并展現了在并行處理上的效率。
該算法可以有效地延伸到每個處理器擁有多個值的情況。在Baudet–Stevenson奇偶合并分區算法中，每個處理器在每一步對自己所擁有的子數組進行排序，然后與鄰居執行合并分區或換位合并。
Batcher奇偶歸并排序
Batcher奇偶歸并排序是一種相關但更有效率的排序算法，采用比較-交換和完美-洗牌操作。
Batcher的方法在擁有廣泛互連的并行計算處理器上效率不錯。
最差時間復雜度 \Theta(n^2)
奇偶排序動態圖如下所示：
代碼實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
package com.baobaotao.test; /** * 排序研究 * */public class Sort { /** <span style="white-space:pre"> </span> * 奇偶排序 <span style="white-space:pre"> </span> * @param array <span style="white-space:pre"> </span> */ public static void batcherSort(int[] array) { int length = array.length ; boolean flag = true ; while(true) { flag = true ; for(int i=1;i<length-1;i+=2) { if(array[i] > array[i+1]) { swap(array, i, i+1) ; flag = false ; } } for(int i=0;i<length-1;i+=2) { if(array[i] > array[i+1]) { swap(array, i, i+1) ; flag = false ; } } if(flag) break ; printArr(array) ; } } /** * 按從小到大的順序交換數組 * @param a 傳入的數組 * @param b 傳入的要交換的數b * @param c 傳入的要交換的數c */ public static void swap(int[] a, int b, int c) { int temp = 0 ; if(b < c) { if(a[b] > a[c]) { temp = a[b] ; a[b] = a[c] ; a[c] = temp ; } } } /** * 打印數組 * @param array */ public static void printArr(int[] array) { for(int c : array) { System.out.print(c + " "); } System.out.println(); } public static void main(String[] args) { int[] number={11,95,45,15,78,84,51,24,12} ; batcherSort(number) ; } } |
輸出分析：
|
1
2
3
4
|
11 45 15 95 51 78 12 84 2411 15 45 51 12 95 24 78 8411 15 12 45 24 51 78 95 8411 12 15 24 45 51 78 84 95 |
希望本文所述對大家的java程序設計有所幫助。
