半熟前端

軟體工程師 / 台灣人 / 在前端的路上一邊探索其他領域的可能性

演算法

Array.sort 淺析

Array.sort 淺析

這篇文章不是談論在 Javascript 原生的 sort 要注意的事項。例如:

;[1, 2, 3, 8, 20, 30, 11].sort()
// [1, 11, 2, 20, 3, 30, 8]

因為預設的 sort 方法會把值轉為 String,並按照 char code 做排序,所以才會出現上面的結果。

今天要來探討 Javascript 的 sort 背後的實作方式。

V8 的實作當中,我們可以看到幾個事實:

  • Array 的 sort 是用 quick sort 排序
  • 在陣列數量小於等於 10 的時候,使用插入排序。

為了簡化 V8 中的代碼,這邊撰寫一個簡單的快速排序代碼:(僅供參考)

function quickSort(arr, p, r) {
  if (p < r) {
    var q = partition(arr, p, r)
    quickSort(arr, q - 1, p)
    quickSort(arr, q + 1, r)
  }
}

function partition(arr, p, r) {
  var x = arr[r]
  var i = p - 1
  for (var j = p; j < r - 1; j++) {
    if (arr[j] <= x) {
      i += 1
      var tmp = a[j]
      arr[j] = a[i]
      arr[i] = tmp
    }
  }
  var tmp = arr[r]
  arr[r] = a[i + 1]
  arr[i + 1] = tmp
}

深入探討:為什麼是快速排序?

快速排序法的實現重點在於如何選擇一個相對好的 pivot,來避免最壞情況的發生。在實際的情況當中,輸入的資料並不一定是隨機的,所以在實務上都會使用 random 的方式來選擇 pivot。

第一個問題是,為什麼 V8 使用快速排序?雖然快速排序的平均時間複雜度可以達到 O(nlogn)O(nlogn),但是最壞情況也有可能達到O(n2)O(n^2)。同時,快速排序並不是一個穩定的演算法,也就是兩個同樣值的資料,在排序之後位置可能會不同。

為什麼不用合併排序?

合併排序簡單可以分為兩大步驟,先把 array 分解後再調用 merge 不斷合併。不僅平均、最壞、最好時間複雜度都可以達到O(nlogn)O(nlogn),演算法本身也是穩定的,為什麼不採用呢?

In-place

我們在 quick sort 當中,並不需要對 array 做合併的動作,也就是整個演算法可以不另外耗費空間完成,而 merge sort 需要 O(n)O(n) 的空間。因此儘管快速排序有上述的情況發生,但在實務上他仍然是一個相當好的選擇。

我們可以透過 randomize 的方式(關於如何隨機選取 pivot,實際上還能夠寫一大篇文章來解釋),來避免 O(n2)O(n^2) 的情形發生。

Stable

不過儘管如此,我們還是沒辦法解決 stable 的問題,雖然在大部分的場景當中可能並不重要(畢竟資料排序通常都是由後端實作),不過如果真的碰到時,這就是非常重要的考量了。

並不是每個瀏覽器的實作都是用 Quicksort

插入排序

如果仔細看一下 V8 的原始碼,會發現這一段:

 while (true) {
  // Insertion sort is faster for short arrays.
  if (to - from <= 10) {
    InsertionSort(a, from, to);
    return;
  }

咦,為什麼在陣列數量小於等於 10 的時候要用插入排序法呢?

要理解原因,我們先回想一下插入排序的原理。插入排序跟撲克牌整理牌的方式很像,每次拿起一張牌,找到一個最適當位置放入,每次的要插入的牌組都是已經整理好的,可以達到原址排序。

function insertionSort(arr) {
  for (var j = 1; j < arr.length; j++) {
    var key = arr[j]
    var i = j - 1
    while (i >= 0 && arr[i] > key) {
      arr[i + 1] = arr[i]
      i = i - 1
    }
    arr[i + 1] = key
  }
  return arr
}

插入排序雖然跟氣泡排序擁有相同的時間複雜度,不過在交換次數上有很大的不同,氣泡排序有O(n2)O(n^2)的交換次數,而插入排序最多只需要O(n)O(n)

回到最剛開始的問題,為什麼在陣列數量小於等於 10 的時候要用插入排序法呢?

對於小數量的陣列而言,如果已經排序好,或是相當接近有序的陣列,插入排序法是唯一可以達到時間複雜度O(n)O(n)的演算法。這是相當有效率的一件事。

結論

因為在工作上需要排序,因此開始深入理解了原生的 sort 在背後做了哪些事情。除了要注意 js 會預設轉為字串比較之外,在處理資料量大的陣列時,理解背後的實作方式就顯得相當重要。

同時我們也了解到,不同的排序演算法都有其適合的場景,在使用 sort 的時候要記得:

  • Quick sort 在實務上通常有最好的結果,但要注意 quick sort 並不是穩定的演算法
  • Merge sort 雖然能夠達到 O(nlogn)O(nlogn) 的時間複雜度,但是需要額外 O(n)O(n) 的空間做 merge
  • Insertion sort 在小數量的陣列排序上有不錯的效果,最好情形可以在O(n)O(n) 比較完成。