排序——冒泡排序

冒泡排序

基本思想

• 依次比較相臨兩個資料元素的大小，若逆序則交換兩個資料元素，否則不交換。
• 當完成一趟交換以後，最大的元素将會出現在資料序列的最後一個位置。
• 重複以上過程，直到待排序序列中沒有逆序為止。

每趟結束時，不僅能擠出一個最大值到最後面位置，還能同時部分理順其他元素；

**一旦下趟沒有交換，還可提前結束排序**
           

算法實作

c++代碼實作

// 原始冒泡排序
void bubblf_sort(SqList &L){
    // 從大到小有序
    for(i = 1; i <= L.length; ++i)
        for(j = 1; j <= L.length - 1; j++){
            if(L.r[j + 1].key < L.r[j].key){
                temp = L.r[j + 1];
                L.r[j + 1] = L.r[j];
                L.r[j] = temp;
            }

        }
}

// 改進後的算法
void bubblf_sort(SqList &L){
    for(i = 1, change = true; i <= L.length - 1 && change; i++){
        change = false;
        for(j = 1; j < L.length - i; ++i)
            if(L.r[j + 1].key < L.r[j].key){
                temp = L.r[j];
                L.r[j] = L.r[j + 1];
                L.r[j + 1] = temp;
                change = true;
            }
    }
}           

python代碼實作

'''冒泡排序-BubbleSort'''
def bubble_sort(alist):
    for j in range(len(alist)-1,0,-1):
        # j表示每次周遊需要比較的次數，是逐漸減小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

l = [54, 45, 32, 34, 56, 90]
bubble_sort(l)

print(l)
           

[32, 34, 45, 54, 56, 90]           

算法分析

• 時間複雜度為 O(n^2)
  • 最好情況下: 隻需 1趟排序，比較次數為 n-1，不移動
  • 最壞情況下：需 n-1趟排序，第i趟比較n-i次，移動3(n-i)次
• 空間複雜度為 O(1)
• 是一種穩定的排序方法