雙向冒泡排序

雙向冒泡排序，是一種計算方法。

基本介紹

• 中文名：雙向冒泡排序（改進冒泡排序）
• 外文名：Shaker Sort

算法原理

傳統冒泡算法原理

冒泡排序算法的運作如下：（從後往前）

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
3. 針對所有的元素重複以上的步驟，除了最後一個。
4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

雙向冒泡算法原理

雙向冒泡排序算法的運作如下：

1. 傳統冒泡氣泡排序的雙向進行，先讓氣泡排序由左向右進行，再來讓氣泡排序由右往左進行，如此完成一次排序的動作
2. 使用left與right兩個旗標來記錄左右兩端已排序的元素位置。

算法實例

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

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

往右排序：19 45 77 13 28 18 19 77 11 [81]

向左排序：[11] 19 45 77 13 28 18 19 77 [81]

往右排序：[11] 19 45 13 28 18 19 [77 77 81]

向左排序：[11 13] 19 45 18 28 19 [77 77 81]

往右排序：[11 13] 19 18 28 19 [45 77 77 81]

向左排序：[11 13 18] 19 19 28 [45 77 77 81]

往右排序：[11 13 18] 19 19 [28 45 77 77 81]

向左排序：[11 13 18 19 19] [28 45 77 77 81]

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

C語言代碼實現

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>#define MAX 30#define SWAP(x, y) {int t; t = x; x = y; y = t;}void Shakersort(int []);int main(){    int i;    int number[MAX];    srand(time(NULL));    printf("排序前：");    for (i = 0; i < MAX; i++)    {        number[i] = rand() % 100;        printf("%d ", number[i]);    }        Shakersort(number);    printf("\n改進冒泡排序後：");    for (i = 0; i < MAX; i++)        printf("%d ", number[i]);    printf("\n");    return 0;}void Shakersort(int number[]){    int left = 0, right = MAX - 1, shift = 1;    int i;        while (left < right)    {        for (i = left; i < right; i++)        {            if (number[i] > number[i+1])            {                SWAP(number[i], number[i+1])                shift = i;            }        }        right = shift;        for (i = right-1; i >= left; i--)        {            if (number[i] > number[i+1])            {                SWAP(number[i], number[i+1])                shift = i + 1;            }        }        left = shift;    }}