Array.sort原理 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

0

Array.sort原理

javascript 演算法 array 排序

qpalzm 2021-10-20 14:41:58 ‧ 1353 瀏覽

分享至

關於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的時候,會因為提升效能而改用插入排序法而不是全都用快速排序法?

謝謝大家

登入發表討論

直播研討會

{{ item.subject }}

{{ item.channelVendor }} {{ item.webinarstarted }} |

{{ formatDate(item.duration) }}

直播中

1 個回答

3

海綿寶寶

iT邦大神 1 級 ‧ 2021-10-20 15:21:58

最佳解答

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

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

回應 3
分享
檢舉

qpalzm iT邦研究生 5 級 ‧ 2021-10-20 15:36:25 檢舉

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

海綿寶寶 iT邦大神 1 級 ‧ 2021-10-20 15:43:19 檢舉

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

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

也可以用遞迴寫 Insertion Sort

qpalzm iT邦研究生 5 級 ‧ 2021-10-20 16:10:55 檢舉

了解~謝謝海綿大大

登入發表回應

我要發表回答

立即登入回答

參賽組數

1064 組

團體組數

40 組

累計文章數

22201 篇

完賽人數

602 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js

IT邦幫忙