與單向冒泡相似的，雙向冒泡排序就是在一趟排序完成之后，同時向兩端有序的將元素冒出，使得兩端總是保持有序狀態，中間無序。
假設有 N 個待排序元素，則最多只需要 N /2 趟排序，就能使得所有元素變成有序的了。由于最近在搞排序算法，當然，在寫這篇隨筆
之前也有在網上搜索過與雙向冒泡排序相關的資料，我找到的都是通過嵌套了 while 循環語句來實現雙向冒泡排序的，而我接下來的，
并沒有這樣做，而是直接在單向冒泡排序算法中直接來修改，這樣很容易的也能實現雙向冒泡排序；
在隨機測試數據中沒有異常狀況，排序正常，但這畢竟是一種算法，我的是沒有經過什么嚴格驗證之類的，但既然是算法，只要靈魂思想不變，
總會有很多不同形式的實現方式，小弟初探算法，下面如有不正確的地方，還望高手指出，小弟虛心學習~~
請先移步至我的上一篇隨筆 ----> java 冒泡排序：http://www.aygfsteel.com/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
posted on 2012-07-18 17:55
fancydeepin 閱讀(1104)
評論(0) 編輯 收藏