午后星期午

java 双向冒泡排序

与单向冒泡相似的，双向冒泡排序就是在一趟排序完成之后，同时向两端有序的将元素冒出，使得两端总是保持有序状态，中间无序。
假设有 N 个待排序元素，则最多只需要 N /2 趟排序，就能使得所有元素变成有序的了。由于最近在搞排序算法，当然，在写这篇随笔
之前也有在网上搜索过与双向冒泡排序相关的资料，我找到的都是通过嵌套了 while 循环语句来实现双向冒泡排序的，而我接下来的，
并没有这样做，而是直接在单向冒泡排序算法中直接来修改，这样很容易的也能实现双向冒泡排序；
在随机测试数据中没有异常状况，排序正常，但这毕竟是一种算法，我的是没有经过什么严格验证之类的，但既然是算法，只要灵魂思想不变，
总会有很多不同形式的实现方式，小弟初探算法，下面如有不正确的地方，还望高手指出，小弟虚心学习~~

请先移步至我的上一篇随笔   ---->   java 冒泡排序：http://www.blogjava.net/fancydeepin/archive/2012/07/18/java_bubblesort.html


下面对单向冒泡排序稍作修改，来实现双向冒泡排序：

排序基类：BaseSort.java

package sort;
/**
 * -----------------------------------------
 * @文件: BaseSort.java
 * @作者: fancy
 * @邮箱: fancydeepin@yeah.net
 * @时间: 2012-7-18
 * @描述: 基类
 * -----------------------------------------
 */
public class BaseSort {

    protected final static int ASC  = 1;    // 升序
    protected final static int DESC = 0;    // 降序
    
    //交换i1、i2下标指向的值
    public void swap(Object[] array, int i1, int i2){
        Object tempObj;
        tempObj  = array[i1];
        array[i1] = array[i2];
        array[i2] = tempObj;
        tempObj = null;
    }
    
    //打印输出数组元素
    public void print(Object[] array){
        for(Object obj : array){
            System.out.print(obj + "    ");
        }
        System.out.println();
    }
}


双向冒泡排序：BubbleSort.java

package sort;
/**
 * -----------------------------------------
 * @文件: BubbleSort.java
 * @作者: fancy
 * @邮箱: fancydeepin@yeah.net
 * @时间: 2012-7-18
 * @描述: 冒泡排序
 * -----------------------------------------
 */
public class BubbleSort extends BaseSort{

    /**
     * @方法名:    doubleBubbleSort 
     * @参数名： array 排序对象
     * @参数名： order 排序顺序
     * @描述语:    双向冒泡排序
     */
    public void doubleBubbleSort(Object[] array, int order){
        int length = array.length;
        if(order == ASC){  //升序排序
            for(int i = 0, j; i < length/2; i++){  //N个数需要N/2趟
                for(j = i; j < length - 1 - i; j++){ //假设是从左至右,则每当此for循环结束,较大的数往右边冒出
                    if(Double.parseDouble(array[j].toString()) > Double.parseDouble(array[j + 1].toString())){
                        swap(array, j, j + 1);
                    }
                }
                System.out.println("-------------------------------------------------------------------------->第" + (i + 1) + "次正向冒泡");
                print(array);
                for(--j; j > i; j--){  //添加一层循环,同时从右至左,则每当此for循环结束,较小的数往左边冒出
                    if(Double.parseDouble(array[j - 1].toString()) > Double.parseDouble(array[j].toString())){
                        swap(array, j - 1, j);
                    }
                }
                System.out.println("<--------------------------------------------------------------------------第" + (i + 1) + "次反向冒泡");
                print(array);
            }
        }else if(order == DESC){  //降序排序
            for(int i = 0, j; i < length/2; i++){  //N个数需要N/2趟
                for(j = i; j < length - 1 - i; j++){ //假设是从左至右,则每当此for循环结束,较小的数往右边冒出
                    if(Double.parseDouble(array[j].toString()) < Double.parseDouble(array[j + 1].toString())){
                        swap(array, j, j + 1);
                    }
                }
                System.out.println("-------------------------------------------------------------------------->第" + (i + 1) + "次正向冒泡");
                print(array);
                for(--j; j > i; j--){  //添加一层循环,同时从右至左,则每当此for循环结束,较大的数往左边冒出
                    if(Double.parseDouble(array[j - 1].toString()) < Double.parseDouble(array[j].toString())){
                        swap(array, j - 1, j);
                    }
                }
                System.out.println("<--------------------------------------------------------------------------第" + (i + 1) + "次反向冒泡");
                print(array);
            }
        }
    }
}


测试类：TestApp.java

package sort;
/**
 * -----------------------------------------
 * @文件: TestApp.java
 * @作者: fancy
 * @邮箱: fancydeepin@yeah.net
 * @时间: 2012-7-18
 * @描述: 测试类
 * -----------------------------------------
 */
public class TestApp {

    public static void main(String[] args) {
        Object[] array = {10,8,9,6,7,5,4,3,1,2};
        (new BubbleSort()).doubleBubbleSort(array, BubbleSort.ASC);
    }
}


10 个数需要 5 趟排序，每趟排序完成将其排序结果输出两次，一次是正向冒泡排序的结果，另外一次是反向冒泡排序的结果，
以这里的升序排序为例子，在每一趟排序中，正向冒泡排序将剩余所有元素中较大的元素冒至剩余元素最右端，反向冒泡排序将剩余所有元素中较小的元素冒至剩余元素最左端，
这样一来，10 个待排序的元素，最多只需要来回 5 趟，就能将所有元素变成有序。下面是后台打印输出结果：


-------------------------------------------------------------------------->第1次正向冒泡
8    9    6    7    5    4    3    1    2    10    
<--------------------------------------------------------------------------第1次反向冒泡
1    8    9    6    7    5    4    3    2    10    
-------------------------------------------------------------------------->第2次正向冒泡
1    8    6    7    5    4    3    2    9    10    
<--------------------------------------------------------------------------第2次反向冒泡
1    2    8    6    7    5    4    3    9    10    
-------------------------------------------------------------------------->第3次正向冒泡
1    2    6    7    5    4    3    8    9    10    
<--------------------------------------------------------------------------第3次反向冒泡
1    2    3    6    7    5    4    8    9    10    
-------------------------------------------------------------------------->第4次正向冒泡
1    2    3    6    5    4    7    8    9    10    
<--------------------------------------------------------------------------第4次反向冒泡
1    2    3    4    6    5    7    8    9    10    
-------------------------------------------------------------------------->第5次正向冒泡
1    2    3    4    5    6    7    8    9    10    
<--------------------------------------------------------------------------第5次反向冒泡
1    2    3    4    5    6    7    8    9    10    



   [转载出处：http://www.blogjava.net/fancydeepin ]

posted on 2013-12-31 13:48 午后星期午 阅读(122) 评论(0)  编辑  收藏 所属分类: Java


只有注册用户登录后才能发表评论。
网站导航: