排序方法之－－－奇偶排序方法

转帖：http://blog.csdn.net/benjamin_whx/article/details/42456755

经典排序算法 - 奇偶排序Odd-even sort

又一个比较性质的排序,基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序

举例吧,

待排数组[6 2 4 1 5 9]

第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比

[6 2 4 1 5 9]

交换后变成

[2 6 1 4 5 9]

 

第二次比较偶数列,即6和1比,5和5比

[2 6 1 4 5 9]

交换后变成

[2 1 6 4 5 9]

 

第三趟又是奇数列,选择的是2,6,5分别与它们的邻居列比较

[2 1 6 4 5 9]

交换后

[1 2 4 6 5 9]

 

第四趟偶数列

[1 2 4 6 5 9]

一次交换

[1 2 4 5 6 9]

p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; color: #555555; -webkit-text-stroke: #000000} p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; -webkit-text-stroke: #000000; min-height: 14.0px} span.s1 {font-kerning: none} td.td1 {width: 156.0px; margin: 0.5px 0.5px 0.5px 0.5px; padding: 1.0px 1.0px 1.0px 1.0px} td.td2 {width: 89.0px; margin: 0.5px 0.5px 0.5px 0.5px; padding: 1.0px 1.0px 1.0px 1.0px}

最差时间复杂度 O(N?)

p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Menlo} span.s1 {font-variant-ligatures: no-common-ligatures}

public static void batcherSort(int[] array) {

        int length = array.length ;  

        boolean flag = true ;  

        while(true) {  

            flag = true ;  

            for(int i=1;i

                if(array[i] > array[i+1]) {  

                    swap(array, i, i+1) ;  

                    flag = false ;  

                }  

            }  

            for(int i=0;i

                if(array[i] > array[i+1]) {  

                    swap(array, i, i+1) ;  

                    flag = false ;  

                }  

            }  

            if(flag) break ;  

            printArr(array) ;  

        }  

    }