200811190303氣泡排序法－bushcollyqr

以下轉錄自：http://program-lover.blogspot.com/2008/06/bubble-sort_20.html

氣泡排序法(bubble sort)是排序演算法(sorting algorithm)中較簡略單純翻譯一種翻譯社而其運作翻譯道理是藉由逐次比較相鄰翻譯兩筆資料，並依照排序前提(由大至小或由小至大)交流資料直到排序完成為止翻譯社

　　假定而今我們需要將 n 筆資料 A₁、A₂、......、A_n 由小排到大，則先比力 A₁ 與 A₂，若是 A₁ < A₂ 則互換兩筆資料。接著比力 A₂ 與 A₃，若是 A₂ < A₃ 則互換兩筆資料。以此類推，一直到比較完 A_{n - 1} 與 A_n 為止。

　　這樣就完了嗎？固然還沒。不過到目前為止，我們已經確定 A_n 是 n 筆資料中最大翻譯數字。

　　接下來，重複剛剛翻譯動作：比力 A₁ 與 A₂、A₂ 與 A₃、A₃ 與 A₄、......，不同的是，這一次只需要比較到 A_{n - 2} 與 A_{n - 1} 即可。到目前為止，我們可以確定 A_{n - 1} 是 n 筆資料中次大的數字。

　　接著就繼續反複一樣的動作，便能肯定每輪比力中的最大資料，皆在這些資料的最後面。直到肯定所有筆資料為止。

　　其道理的虛擬碼大致如下：

void bubblesort(Type data[1..n])
{
    Index i 翻譯公司 j;
    for (i = n to 1)
    {
        for (j = 1 to i - 1)
        {
            if (data[j] < data[j + 1])
            {
                exchange data[j] and data[j + 1];
            }
        }
    }
}

　　讓我們舉個例來說明。若是我們現在要將以下這些資料由大排到小：

1 43 6 79 50 2

　　則第一輪的比力與交流過程如下：

43 1 6 79 50 2

43 6 1 79 50 2

43 6 79 1 50 2

43 6 79 50 1 2

43 6 79 50 2 1

　　第二輪的比力與交流過程以下：

43 6 79 50 2 1

43 79 6 50 2 1

43 79 50 6 2 1

43 79 50 6 2 1

　　接下來以此類推。

　　由此可以看到，資估中較小的一筆會藉由交換慢慢"浮"到資料頂端，其氣泡排序之名也是是以而來的。

　　而在另外一方面，我們也能夠注重到，若是要使用氣泡排序法將 n 筆資料排序，需要進行的比力次數為： (n - 1) + (n - 2) + (n - 3) + ... + 1 = n(n - 1) / 2 翻譯社

　　對於一種排序演算法而言，如許的比較次數是相當沒有效率的翻譯社是以這個方式多半只是被拿來簡單的解釋排序概念，而不是拿來現實利用翻譯社

　　最後，照慣例"附贈"一個 C 語言實現泡泡排序法的程式：

#include <stdio.h>
#include <stdlib.h>

void bubblesort(int *data 翻譯公司 int n);

int main(void)
{
    int i, n, data[10];

    printf("請輸入資料筆數 n(<= 10): ");
    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        printf("請輸入第 %d 筆資料: ", i + 1);
        scanf("%d", &data[i]);
    }

    // 履行氣泡排序法
    bubblesort(data 翻譯公司 n);

    printf("
排序後 翻譯成效: ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", data[i]);
    }

    printf("
");
    system("pause");
}

void bubblesort(int *data 翻譯公司 int n)
{
    int i, j, temp;
    for (i = n - 1; i > 0; i--)
    {
        for (j = 0; j <= i - 1; j++)
        {
            if (data[j] < data[j + 1])
            {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
}