【排序算法】v8 引擎中 sort 排序算法

[slogeor]

算法实现思路

• 1.数组长度小于10，插入排序比快速排序更高效，v8 选择的是插入排序算法
• 2.数组长度大于10，优先使用快速排序
  • 2.1数组长度小于1000，分区点去的是中间位置的元素 pivot = from + ((to - from) >> 1)
  • 2.2数组长度大于1000，分区点的方法见 GetThirdIndex
• 3.循环执行step2

[slogeor]

排序算法的选择标准

• 1.对于小规模数据进行排序，一般选择时间复杂度为 O(n^2) 的插入排序算法；
• 2.对于大规模数据进行排序，一般选择时间复杂度为 O(nlogn) 的快速排序算法；
• 3.对于任意规模数据进行排序，一般选择时间复杂度为 O(nlogn) 的快速排序算法；

[slogeor]

如何优化快速排序

最理想的分区是：被分区点分开的两个分区中，数据的数量差不多。

1.三数取中法
从区间的首、尾、中间分别取出一个数，然后对比大小，取这3个数的中间值作为分区点。

2.随机法
每次从要排序的区间中，随机选择一个元素作为分区点。

[slogeor]

GetThirdIndex

var GetThirdIndex = function (a, from, to) {
    var t_array = [];
    // Use both 'from' and 'to' to determine the pivot candidates.
    // 计算步长
    var increment = 200 + ((to - from) & 15);
    var j = 0;
    from += 1;
    to -= 1;
    for (var i = from; i < to; i += increment) {
        t_array[j] = [i, a[i]];
        j++;
    }
    
    // 对数组进行排序
    t_array.sort(function (a, b) {
        return a[1] - b[1];
    });
    // 取数组中间结点的位置
    var third_index = t_array[t_array.length >> 1][0];
    return third_index;
}