奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对，a[j]和a[j+1]，j是奇数(j=1, 3, 5……)。如果它们的关键字的值次序颠倒，就交换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=2, 4,6……)。重复进行这样两趟的排序直到数组全部有序。

和冒泡排序法一样，奇偶排序的时间复杂度为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 }