冒泡排序的實現

一、冒泡排序簡介

冒泡排序，重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

二、算法的運作

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

三、時間復雜度

      若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數和記錄移動次數均達到最小值：比較次數: n-1 ，移動次數為0 。所以，冒泡排序最好的時間復雜度為O(n) 。
　　若初始文件是反序的，需要進行趟n-1 排序。每趟排序要進行 n-i ((1≤i≤n-1))次關鍵字的比較，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：比較次數n*(n-1)/2 ，移動次數3n*(n-1)/2 。
冒泡排序的最壞時間復雜度為O(n*n) 。
綜上，因此冒泡排序總的平均時間復雜度為O(n*n) 。

四、算法穩定性

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，不用交換一下的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序算法。

五、代碼實現

#include <stdio.h>
#define SIZE 8
 
void bubble_sort(int a[], int n);
 
void bubble_sort(int a[], int n)
{
    int i, j, temp;
    for (j = 0; j < n - 1; j++)
        for (i = 0; i < n - 1 - j; i++)
        {
            if(a[i] > a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
}
 
int main()
{
    int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    int i;
    bubble_sort(number, SIZE);
    for (i = 0; i < SIZE; i++)
    {
        printf("%d", number[i]);
    }
    printf("\n");
}