排序演算法入門冒泡排序

在開發中，對一組資料進行有序地排列是經常需要做的事情，所以掌握幾種甚至更多的排序演算法是絕對有必要的

本文章介紹的是排序演算法中較簡單的一種演算法：冒泡排序

先嘗試用最簡單的想法去實現排序，以此來比較學習冒泡排序

問題：設有一數組，其大小為10個元素（int   str[10]）數組內的數據是無序。現在要求我們透過程式將這個無序的陣列變成一個從小到大排序的陣列（從下標為0開始）

思路：按照題目的要求，毫無疑問，正確的結果應該就像這樣： 1 2 3 4 5 6 7 8 9 10   要做到這樣，最簡單且最直接想到的方法就是進行對比交換。

首先，將10個數裡最小的個數放到下標為0的位置上（str[0]）

通過將下標為0的數（str[0]）與剩下其餘9個數字進行對比交換（將較少者放置在下標為0的位置上），就可以得到這10個數最小的那個

10個數最小的那位確定後，接下來就要找剩下9個數最小的那個。

因為已經確定出一個最小的數，所以就不要動str[0]，直接從str[1]開始，與剩下的8個數對比交換，找出9個數中最小的那位放到下標為1（str[1]）的位置上

繼續按照這個思路就可以將這十個數變成有序的（從小到大）的數組

代碼：

#include <stdio.h>  
  
void swap(int *a, int *b); //交换两个数  
  
int main()  
{  
    int     str[10];  
    int     i, j;  
    //初始化数组为10 9 8 7 6 5 4 3 2 1  
    for (i = 0; i < 10; i++)  
    {  
        str[i] = 10 - i;  
    }  
    //排序，从a[0]开始排，从小到大  
    for (i = 0; i < 10; i++)  
    {  
        for (j = i + 1; j < 10; j++)  
        {  
            if (str[i] > str[j])  
            {  
                swap(&str[i], &str[j]);  
            }  
        }  
    }  
        //将十个数输出  
    for (i = 0; i < 10; i++)  
        printf("%d\n", str[i]);  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int     c;  
     c = *a;  
    *a = *b;  
    *b =  c;  
}

這個方法是比較容易想到的實作方法。但存在不足：就是原本位於前面的較小數字被交換到後面

演示：

開始：9 4 5 6 8 3 2 7 10 1  （下標從左到右分別是0~9）依照上面的程序進行比較交換

第一次：4 9 5 6 8 3 2 7 10 1 

第二次：4 9 5 6 8 3 2 7 10 1 

。 。 。 ：（無交換）

第五次：3 9 5 6 8 4 2 7 10 1 

第六次：2 9 5 6 8 3 4 7 10 1 

。 。 。 ：（沒有交換）

第十次：1 9 5 6 8 3 4 7 10 2 

可以看出，原來較小的數是在前面的，經過一輪的交換後放到後面了

那麼怎樣解決這個不足呢？可以使用冒泡排序

什麼是冒泡排序呢？

你可以這樣理解：（從小到大排序）存在10個不同大小的氣泡，由底至上地把較少的氣泡逐步地向上升，這樣經過遍歷一次後，最小的氣泡就會被上升到頂（下標為0），然後再從底至上地這樣升，循環直到十個氣泡大小有序。

在冒泡排序中，最重要的思想是兩兩比較，將兩者較少的升上去

冒泡排序最壞情況的時間複雜度是O(n²)

代碼：

#include <stdio.h>  
void swap(int *a, int *b);  
int main()  
{  
    int    array[10] = {15, 225, 34, 42, 52, 6, 7856, 865, 954, 10};  
    int    i, j;  
    for (i = 0; i < 10; i++)  
    {  
        //每一次由底至上地上升  
        for (j = 9; j > i; j--)  
        {  
            if (array[j] < array[j-1])  
            {  
                    swap(&array[j], &array[j-1]);  
            }  
        }  
    }  
    for (i = 0; i < 10; i++)  
    {  
        printf("%d\n", array[i]);  
    }  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int    temp;  
    temp = *a;  
      *a = *b;  
      *b = temp;  
}

冒泡排序演算法只會將較少的逐步向上推，不會造成文章前面所說的不足，這裡就不給予示範。

更多排序演算法入門之冒泡排序相關文章請關注PHP中文網！