氣泡排序(Bubble Sort)、插入排序(Insertion Sort)、選擇排序(Selection Sort)


氣泡排序(Bubble Sort)、插入排序(Insertion Sort)、選擇排序(Selection Sort)是三種概念較簡單的排序方式,空間複雜度皆僅要 O(1),但平均時間複雜度皆達 O(n²),除非要處理的資料量少,否則實務上少有應用。


氣泡排序(Bubble Sort)

由後而前依序將兩兩相鄰的值互相比較,直到所有的值都被排到正確的位置為止。

圖示

現假設有一陣列 [6,5,4,9,1],要透過氣泡排序將陣列由小排到大的過程如下:

值得注意的是,當 i=(arr.length-2)=3 的迴圈跑完之後,只剩下 i=(arr.length-1)=4 的迴圈沒有跑,但經過前面幾輪迴圈,已能確定剩下的「9」必在最後一格,因此 i=(arr.length-1)=4 的迴圈可忽略不跑即排序完畢。

偽代碼&說明

若以「將陣列由小到大排序」為目標,則有指標「i」從第 0 項跑到倒數第二項,表示已經排序的範圍;另有指標「j」從最後一項跑到第 (i+1) 項,在此範圍內的相鄰值兩兩比較,左值小於右值則不變、左值大於右值則兩值互換。

只要兩相鄰值大小相等,兩者的相對位置就不會改變,因此屬於「穩定排序(stable sort)」。

程式碼範例(JavaScript)

function bubbleSort(arr){
    for(let i=0; i<=arr.length-2; i++){               //用指標i標示已經排序的範圍
        for(let j=arr.length-1; j>=(i+1); j--){       //指標j從尾往前走過所有未排序處
            if(arr[j-1]>arr[j]){                      //指標j對應的值與相鄰的值兩兩比較,若與目標順序不同則互相調換位置
                let temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

時間複雜度

氣泡排序使用雙層巢狀迴圈(nested loop),外層 i 從第 0 項走到 (arr.length-2) 項(次末項),在 i 之前的值代表已經排序好的資料;內層 j 從第 (arr.length-1) 項 (最末項) 開始走到第 (i+1) 項,用來將相鄰的值兩兩配對比較。現假設陣列中共有 (n+1) 筆資料(索引值從 0 到 n),時間複雜度分析如下:

  1. 最差情況:O(n²),若原陣列排序正好與目標順序完全相反,所有的值都被調換,最末項調換 n 次、次末項調換 (n-1) 次…第 1 項調換 1 次、第 0 項調換 0 次,全部共調換 [n+(n-1)+…+1+0] = [(n+0)·(n+1)]/2 = (n²+n)/2 次,O((n²+n)/2)=O(n²)。
  2. 最佳情況:O(n),若原陣列排序正好與目標順序完全相同,即 i 從第 0 項走到次末項,內層 j 的項目不需要執行,因此一共只有 (n-1) 個運算步驟,時間複雜度為 O(n)。
  3. 平均情況:O(n²),因使用巢狀迴圈,因此多數情況下會有 n‧n 個運算步驟。

空間複雜度

O(1),在排序過程中,資料只在原陣列當中比較、調換,需要的儲存空間固定,不需額外空間暫存資料。


插入排序(Insertion Sort)

從第二項起逐一取值當作「key」,並將其他所有的值依序跟「key」比較,其過程有如將「key」值從資料最末端依序往前掃描,直到找到正確位置後插入。

圖示

現假設有一陣列 [6,5,4,9,1],要透過插入排序將陣列由小排到大的過程如下:

偽代碼&說明

若以「將陣列由小到大排序」為目標,則有指標「j」表示該輪循環中的「key」所在、指標「i」表示「key」值在該輪循環應在的位置。

找到「key」值應在位置之後,將「key」值放到第「i」項即完成該輪迴圈的排序。

插入排序是不斷找到「key」應在位置、並將「key」放入該位置的過程,並沒有將任何值對調,兩大小相等的值在排序後會按照原順序排列,因此屬於「穩定排序(stable sort)」。

程式碼範例(JavaScript)

function insertionSort(arr){
    for(let j=1; j<=arr.length-1; j++){     //從第1項開始設為key,逐一跟其他資料比較
        let key = arr[j];
        let i = j-1;                        //連同下方while迴圈,找到該輪循環key應在位置
        while(i>=0 && arr[i] > key){
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = key;                     //把key放到正確位置上
    }
    return arr;
}

時間複雜度

選擇排序使用雙層巢狀迴圈(nested loop),外層 j 從第 1 項走到 (arr.length-1) 項(最末項),在 j 之前的資料代表已經當過「key」;內層 i 從第 (j-1) 項開始走到第 (-1) 項,用來將資料中所有的值逐一跟「key」比較,以找出「key」的正確位置。現假設陣列中共有 (n+1) 筆資料(索引值從 0 到 n),時間複雜度分析如下:

  1. 最差情況:O(n²),若原陣列排序正好與目標順序完全相反,所有的值都被調換,第 0 項調換 1 次、第 1 項調換 2 次…次末項調換 (n-1) 次、最末項調換 n 次,全部共調換 [1+2...+(n-1)+n] = [(1+n)‧n]/2 = (n+n²)/2 次,O((n+n²)/2)=O(n²)。
  2. 最佳情況:O(n),若原陣列排序正好與目標順序完全相同,即 j 從第 1 項走到最末項,內層迴圈比較 i 與「key」不需執行,因此一共只有 (n-1) 個運算步驟,時間複雜度為 O(n)。
  3. 平均情況:O(n²),因使用巢狀迴圈,因此多數情況下會有 n‧n 個運算步驟。

空間複雜度

O(1),在排序過程中,資料只在原陣列當中比較、賦值,需要的儲存空間固定,不需額外空間暫存資料。


選擇排序(Selection Sort)

在所有資料值中,依序找出最符合目標條件者先排,直到每筆資料都被放到正確的位置為止。

圖示

現假設有一陣列 [6,5,4,9,1],要透過選擇排序將陣列由小排到大的過程如下,綠底者代表當前最小值、黃底者代表正跟綠底最小值比較的值:

值得注意的是,當 i=(arr.length-2)=3 的迴圈跑完之後,只剩下 i=(arr.length-1)=4 的迴圈沒有跑,但經過前面幾輪迴圈,已能確定剩下的「9」必在最後一格,因此 i=(arr.length-1)=4 的迴圈可忽略不跑即排序完畢。

偽代碼&說明

若以「將陣列由小到大排序」為目標,則有指標「i」用來表示該輪循環中最小值應在位置、指標「j」從指標「i」處掃描到最後一筆資料,找出該輪循環的最小值。

找到最小值之後,將其放到 i 標示的應在位置上,在指標「i」以前的資料皆已經完成排序。

程式碼範例(JavaScript)

function selectionSort(arr){
    for(let i=0; i<=arr.length-2; i++){       //用指標i標示該輪循環最小值應在位置
        let min = i;
        for(let j=i; j<=arr.length-1; j++){   //用指標j找到該輪循環最小值,並設為第min項
            if(arr[j]<arr[min]){
                min = j;
            }
        }
        temp = arr[i];                        //將該輪循環最小值從第min項換到第i項;原在第i項者被換到原第min項,待後續比較
        arr[i] = arr[min];
        arr[min] = temp;
    }
    return arr;
}

對於兩大小相等的值而言,如果與之對調的值並非按照目標大小順序排列,則原本排序較前者可能被換到較後面的位置、原本排序較後者可能被換到較前面的位置,因此屬於「不穩定排序(unstable sort)」。

以下圖來說,目標順序是從小排到大,當綠色的 3 與其他值比較時,最小的值為 1、紅色的 3 與其他值比較時,最小的值為 2;但在排序前,2 的位置在 1 的前面,因此調換後,會變成綠 3 在後、紅 3 在前。

選擇排序為「不穩定排序」

時間複雜度

選擇排序使用雙層巢狀迴圈(nested loop),外層 i 從第 0 項走到 (arr.length-2) 項(次末項),用來代表當下最符合條件的值;內層 j 從第 i 項走到 (arr.length-1) 項(最末項),用來將資料中所有的值逐一跟「第 i 項」比較,以更新最符合條件的值。現假設陣列中共有 (n+1) 筆資料(索引值從 0 到 n),時間複雜度分析如下:

  1. 最差情況:O(n²),若原陣列排序正好與目標順序完全相反,所有的值都被調換,最末項調換 n 次、次末項調換 (n-1) 次…第 1 項調換 1 次、第 0 項調換 0 次,全部共調換 [n+(n-1)+…+1+0] = [(n+0)‧(n+1)]/2 = (n²+n)/2 次,O((n²+n)/2)=O(n²)。
  2. 最佳情況:O(n),若原陣列排序正好與目標順序完全相同,第 i 項與第 j 項依然要逐一比較,時間複雜度仍為 O(n²)。
  3. 平均情況:O(n²),因使用巢狀迴圈,不論最差或最佳情況都有 n‧n 個運算步驟,平均時間複雜度仍為 O(n²)。

空間複雜度

O(1),在排序過程中,資料只在原陣列當中比較、調換,需要的儲存空間固定,不需額外空間暫存資料。


三種排序法複雜度比較

#演算法 #氣泡排序 #插入排序 #選擇排序







你可能感興趣的文章

CSS保健室|font-family

CSS保健室|font-family

SOLID 設計原則筆記

SOLID 設計原則筆記

OOP 12 - Open-Closed Principle

OOP 12 - Open-Closed Principle






留言討論