iT邦幫忙

0

Array.sort原理

關於Chrome V8 引擎的 source code 所實作背後的運作原理:

function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 10) arrays, insertion sort is used for efficiency.
  if (!IS_CALLABLE(comparefn)) {
    comparefn = function (x, y) {
      if (x === y) return 0;
      if (%_IsSmi(x) && %_IsSmi(y)) {
        return %SmiLexicographicCompare(x, y);
      }
      x = TO_STRING(x);
      y = TO_STRING(y);
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
}

註釋寫著他是用「Quick Sort」,而當陣列長度<=10 時,為了提升效能會改用「Insertion Sort」。

問題:對於陣列的排序為甚麼在陣列長度<=10的時候,會因為提升效能而改用插入排序法而不是全都用快速排序法?

謝謝大家/images/emoticon/emoticon41.gif

1 個回答

3
海綿寶寶
iT邦大神 1 級 ‧ 2021-10-20 15:21:58
最佳解答

當問題的資料量較小時(欲排序的元素之數目較小),使用Insertion Sort會很有效率,這是因為和Quick Sort、Merge Sort、Heap Sort相比,Insertion Sort不具有「遞迴」形式,因此不需要系統的stack

資料來源

其實如果只有10筆
用QuickSort應該也沒有什麼差

kekeke iT邦新手 3 級 ‧ 2021-10-20 15:36:25 檢舉

所以只差在Insertion Sort沒有「遞迴」,沒有遞迴效能則較佳,可以這樣解釋嗎?

不同的 sort 代表不同的方法
「遞迴」是實作 sort 時選擇的方法(即:可用可不用)

像這個
可以不用遞迴寫 Quick Sort

也可以用遞迴寫 Insertion Sort

kekeke iT邦新手 3 級 ‧ 2021-10-20 16:10:55 檢舉

了解~謝謝海綿大大/images/emoticon/emoticon41.gif

我要發表回答

立即登入回答