Chinaunix首页 | 论坛 | 博客
  • 博客访问: 8965
  • 博文数量: 9
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 45
  • 用 户 组: 普通用户
  • 注册时间: 2011-08-23 20:55
文章分类

全部博文(9)

文章存档

2016年(9)

我的朋友

分类: C/C++

2016-12-24 17:34:13

转帖: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) ;  

        }  

    }





阅读(239) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册