請啟用 Javascript 查看內容

JavaScript 學演算法(八)- 排序演算法

 ·  ☕ 7 分鐘

這週是六角鼠年鐵人賽第十六週,資料結構先暫停一下,換換口味,來看排序。排序演算法(Sort Algorithm)是基礎演算法之一,是一種能將一串資料依照特定排序方式進行排列的一種演算法。

什麼是排序(Sort)

1. 定義

排序(Sort),將一組資料一使用者需求,予以重新排列其順序。

一般會依資料之大小順序排序(由大至小、或由小至大)。

2. 分類

排序演算法分類方式有以下這幾種。

第一類:內部與外部

  • 內部排序(Internal Sort) 又稱「陣列排序」
    • 定義:排序之工作,主要在主記憶體(RAM)完成。
    • 意指資料量小,可以直接放在記憶體內進行。
  • 外部排序(External Sort) 又稱「檔案排序」
    • 定義:排序之工作,主要是在輔助記憶體(Disk, File)完成。
    • 意指資料量大,無法直接存放在記憶體,必須先存放於輔助記憶體內再處理。

第二類:穩定性與不穩定性

  • 穩定性(Stable):相同值的資料,排序後順序和排序前一樣。
  • 不穩定性(Unstable):相同值的資料,排序後順序不一定和排序前一樣。

第三類:簡單與高等

  • 簡單排序:排序演算法簡單,但執行時間較長。
  • 高等排序:排序演算法複雜,執行時間較短。

第四類:比較與非比較

  • 比較排序:通過比較來決定元素間的相對次序。
  • 非比較排序:不通過比較來決定元素間的相對次序。

3. 常見排序演算法

排序相關動畫影片,可以稍微的看一下:

簡單排序:

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

初學排序所必須知道的三個最基本排序演算法,但它們由於速度不快而不實用。

高等排序:

  • 合併排序 Merge Sort
  • 快速排序 Quick Sort
  • 希爾排序 Shell Sort
  • 堆積排序 Heap Sort

高等排序通常用於高效處理大量資料(幾萬起跳),不過有些對於資料過於小(幾千幾百)可能反而比簡單排序還慢。

簡單排序

1. 氣泡排序(Bubble Sort)

氣泡排序(Bubble Sort)又稱為冒泡排序泡沫排序,是排序演算法中最簡單的,但運行時間是最差的。

其排序方式為相臨資料反覆進行比較,若發現資料順序不對,就將資料互換。資料將如氣泡般,從一端漂浮到另一端。

流程模擬動畫:

遞增排列運作原理:

  • 第一輪
    比較相鄰的元素,如果前者大於後者就相互交換;
    從頭到尾執行比較動作,可以確保最後一個元素將會是最大的。
  • 第二輪
    扣除最後一個元素(已排序完畢元素),針對其餘元素重複上述步驟;

每輪執行比較的元素會越來越少,執行至剩一個元素,排序完畢。

氣泡排序的過程範例:

nums = [4, 2, 3, 1];

第一輪
4 2 交換 => 2 4 3 1
4 3 交換 => 2 3 4 1
4 1 交換 => 2 3 1 4

第二輪
2 3 不換 => 2 3 1 4
3 1 交換 => 2 1 3 4

第三輪
2 1 交換 => 1 2 3 4

氣泡排序分析:

  • 穩定排序
  • 時間複雜度
    • 最佳:$O(n)$
    • 最差:$O(n^2)$
    • 平均:$O(n^2)$
  • 空間複雜度為: $O(1)$

演算法實作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function bubbleSort (arr) {
  
  const n = arr.length; // 1
  // 2
  for(let i = 0; i < n - 1; i++) {
    // 3
    for(let j = 0; j < n - 1 - i; j++) {
      // 4
      if(arr[j] > arr[j + 1]) {
        // 5
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}
  1. 元素數量。
  2. 執行 n - 1 輪(最後一次只剩自己,所以不比較)。
  3. 交換 n - 1 - i 次(兩兩互相比較,所以 -1,並扣除每輪已經排好的元素,所以減 i)。
  4. 比較大小。
  5. 元素交換位置。

交換位置也可以使用 ES6 的解構指定(destructuring assignment):

1
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];

你可以建立一個交換函式,之後很多排序法都會用到:

1
2
3
4
5
6
7
8
function swap(arr, index1, index2) {
  const temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
  
  // - ES6 的方式
  // [array[index1], array[index2]] = [array[index2], array[index1]];
}

氣泡排序的平均與最差的時間複雜度都是 $O(n^2)$,但最佳的情況(輸入陣列已是排序好的)時間複雜度為 $O(n)$(元素不做任何的交換)。

要讓最佳的情況時間複雜度為 $O(n)$,需要優化一下程式:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function bubbleSort (arr) {
  const n = arr.length;
  let swapped = true;
  
  for(let i = 0; (i < n - 1) && swapped; i++) {
    swapped = false;
    for(let j = 0; j < n - 1 - i; j++) {
      if(arr[j] > arr[j + 1]) {
        swapped = true;
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}

加上一個標注(flag),在新的一輪開始時,判斷上一輪是否有發生交換,如果沒有表示剩餘的元素已經排序完畢,下一輪會因為 swapped 被設為 false 就會跳出迴圈。

2. 選擇排序(Selection Sort)

選擇排序(Selection Sort) 是一種簡單直觀的排序演算法,類似氣泡排序。

其排序方式為反覆進行搜數列中的最小值,並與最左側的資料交互。

流程模擬動畫:

遞增排列運作原理:

  • 第一輪
    預設第一個元素為最小值,往右側進行搜尋最小值;
    若遇到比目前最小值還小的元素就替換掉;
    搜尋至最後,將最小值與最左側元素交換位置。
  • 第二輪
    扣除第一個元素,針對其餘元素重複以上的步驟。

持續上述步驟,每輪執行比較的元素會越來越少,直到排序完畢。

選擇排序的過程範例:

nums = [4, 1, 3, 2];

第一輪
min 4 (預設)
min 1
交換位置 => 1 4 3 2

第二輪
min 4 (預設)
min 3
min 2
交換位置 => 1 2 4 3

第三輪
min 4 (預設)
min 3
交換位置 => 1 2 3 4

選擇排序分析:

  • 不穩定排序。
  • 時間複雜度
    • Best Case:$O(n^2)$
    • Worst Case:$O(n^2)$
    • Average Case:$O(n^2)$
  • 空間複雜度為: $O(1)$

演算法實作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function selectionSort(arr) {
  const n = arr.length; // 1
  // 2
  for(let i = 0; i < n; i++) {
    // 3
    let minIndex = i;
    // 4
    for(let j = 1 + i; j < n; j++) {
      // 5
      if(arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex); // 6
  }
  return arr;
}
  1. 元素數量。
  2. 執行 n 輪。
  3. minIndex 用來紀錄最小值的索引。
  4. 因為 minIndex 預設為第一元素 j1 開始尋找,每輪會扣除已排好的元素,所以加 i
  5. 比較是否為最小值。
  6. 一輪結束後就將最小值與 i 交換。

選擇排序就算陣列已經是排序好的狀態,還是要經過多輪比較,所以不論是最好、最壞、平均的時間複雜度皆為 $O(n^2)$。但跟氣泡排序比起來,執行交換操作只需要 n 次。

3. 插入排序(Insertion Sort)

插入排序(Insertion Sort)是也一種簡單直觀的排序演算法,你如果玩過撲克牌,就都有用過。

其排序方式為,將左側作為已排序數列,右側為未排序數列,從未排序的數列中取第一個,放到已排序數列中的適當位置。

流程模擬動畫:

遞增排列運作原理:

  • 第一輪
    從第一個元素開始,該元素視為已經被排序;
    取出下一個元素,判斷要插入左側元素的前面還是後面。
  • 第二輪
    已經被排序已有兩個元素;
    取出下一個元素,判斷要插入左側元素的前面還是後面;
    如果是前面就依序往下判斷。

持續上述步驟,右側位被排序的元素會遞減,直到排序完畢。

插入排序的過程範例:

nums = [4, 2, 3, 1];

第一輪
[4] [2 3 1]
[  4] 2
[2 4]

第二輪
[2 4] [3 1]
[2   4] 3
[2 3 4]

第三輪
[2 3 4] [1]
[2 3   4] 1
[2   3 4] 1
[  2 3 4] 1
[1 2 3 4]

分析:

  • 穩定排序。
  • 時間複雜度
    • Best Case:$O(n)$
    • Worst Case:$O(n^2)$
    • Average Case:$O(n^2)$
  • 空間複雜度為: $O(1)$

演算法實作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function insertionSort(arr) {
  const n = arr.length;  // 1
  // 2
  for (let i = 1; i < n; i++) {
    let temp = arr[i]; // 3
    let j = i; // 4
    // 5
    while (j > 0 && temp < arr[j - 1]) {
      arr[j] = arr[j - 1];  // 6
      j -= 1;
    }
    arr[j] = temp;  // 7
  }
  return arr;
}
  1. 元素數量。
  2. 從第二個元素開始,所以 i = 1
  3. 使用一個變數儲存要判斷元素的值。
  4. 使用一個變數儲存前要判斷元素的當前索引。
  5. 只要當前索引比 0 大,並且小於左側的值,就繼續比較。
  6. 將左側的值往後移。
  7. 將要判斷元素的值插入正確位置上。

4. 總結

這三種簡單演算法複雜度基本上差不多:

排序方法 最佳時間 最差時間 平均時間 空間 穩定性
氣泡 Bubble $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 穩定
選擇 Selection $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不穩定
插入 Insertion $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 穩定

這是一個簡易的執行時間計時器,對 100 ~ 10000 個隨機數字進行排序。

執行時間會根據執行環境而有所不同,不過基本上元素數量越小,看不出彼此間的差異,但你可以觀察到當元素達到 10000 時,氣泡排序明顯是最差的,而插入排序稍微快於選擇排序。

不過這三種排序法,資料量非常大時(幾十萬起跳),基本上都要跑很久,所以實際應用上都不適合,下週來看比較實用的合併排序。


竹白
作者
竹白
前端筆記

文章目錄