学步园

事實上這個氣泡排序法已經不是單純的氣泡排序了，它使用了旗標與右端左移兩個方法來改進排序的效能，而Shaker排序法使用到後面這個觀念進一步改良氣泡排序法。
在上面的氣泡排序法中，交換的動作並不會一直進行至陣列的最後一個，而是會進行至MAX-i-1，所以排序的過程中，陣列右方排序好的元素會一直增加，使得左邊排序的次數逐漸減少，如我們的例子所示：

排序前：95 27 90 49 80 58 6 9 18 50

1. 27 90 49 80 58 6 9 18 50 [95] 95浮出
2. 27 49 80 58 6 9 18 50 [90 95] 90浮出
3. 27 49 58 6 9 18 50 [80 90 95] 80浮出
4. 27 49 6 9 18 50 [58 80 90 95] ......
5. 27 6 9 18 49 [50 58 80 90 95] ......
6. 6 9 18 27 [49 50 58 80 90 95] ......
7. 6 9 18 [27 49 50 58 80 90 95]

方括號括住的部份表示已排序完畢，Shaker排序使用了這個概念，如果讓左邊的元素也具有這樣的性質，讓左右兩邊的元素都能先排序完成，如此未排序的元素會集中在中間，由於左右兩邊同時排序，中間未排序的部份將會很快的減少。

方法就在於氣泡排序的雙向進行，先讓氣泡排序由左向右進行，再來讓氣泡排序由右往左進行，如此完成一次排序的動作，而您必須使用left與right兩個旗標來記錄左右兩端已排序的元素位置。

一個排序的例子如下所示：

排序前：45 19 77 81 13 28 18 19 77 11

如上所示，括號中表示左右兩邊已排序完成的部份，當left > right時，則排序完成。

public class ShakerSort 
...{    
    public static void sort(int[] number) 
    ...{        
        int i, left = 0, right = number.length - 1,shift = 0;         
        while(left < right) 
        ...{             // 向右进行气泡排序             
            for(i = left; i < right; i++) 
            ...{                 
                if(number[i] > number[i+1]) 
                ...{                     
                    swap(number, i, i+1);                     
                    shift = i;                 
                }             
            }             
            right = shift;             // 向左进行气泡排序             
            
            for(i = right; i > left; i--) 
            ...{                 
                if(number[i] < number[i-1]) 
                ...{                     
                    swap(number, i ,i-1);                     
                    shift = i;                 
                }             
            }             
            left = shift;         
        }     
    }    
    
    private static void swap(int[] number, int i, int j) 
    ...{        
        int t;        
        t = number[i];         
        number[i] = number[j];         
        number[j] = t;    
    }
}