Nodejs V8 7.0 数组开始使用 TimSort 排序算法

发布于 1周前 作者 wuwangju 来自 nodejs/Nestjs

Nodejs V8 7.0 数组开始使用 TimSort 排序算法

V8 Blog 原文

博客中说他们以前使用的快速排序算法在性能上并不稳定，相同长度的数组在理想情况和最差情况下的排序性能相差较大，于是改用 TimSort 算法。

这个算法是非常有名的一个算法，在保证高性能的同时还能保证性能稳定。

TimSort 的设计思路很新颖（当然也可能借鉴了其他算法）：既然单个算法会遇到最好情况和最差情况导致性能不稳定，那么是不是可以先分析数组特征，然后扬长避短在多种算法中选取合适的算法进行排序呢？

所以实际上 TimSort 是多种排序算法+分块算法+翻转，是一种“混合排序算法调度算法”。

有很多语言引擎默认使用 TimSort 作为原生排序算法，如 Python （ 2.3 开始）、Java SE 7、Android platform、GNU Octave。


Harmonyos Next教程
6 回复

据说 Python 里的 TimSort 算法实现得非常优秀（当时来说）。


因为 Python 里面的 TimSort 是 TimSort 算法作者写的，他写完之后才有 TimSort

真心牛逼

It was implemented by Tim Peters in 2002 for use in the Python programming language.

流畅的 Python 中有写

在 Node.js V8 7.0 版本中，数组的排序算法从之前的快速排序（QuickSort）或插入排序（Insertion Sort）混合算法改为了 TimSort 算法。TimSort 是一种混合排序算法，结合了归并排序（Merge Sort）和插入排序（Insertion Sort）的优点，特别适合对实际数据（通常是部分有序的）进行排序。

以下是 TimSort 算法的一些关键特点及其简单实现的示例（注意，这只是一个非常简化的示例，实际的 V8 实现要复杂得多）：

function timSort(arr) {
    let n = arr.length;
    let run = [];

    // Step 1: Create runs of sorted elements
    for (let i = 0; i < n; i++) {
        if (run.length === 0 || arr[i] >= run[run.length - 1]) {
            run.push(arr[i]);
        } else {
            mergeRuns(run, [arr[i]]);
            i--; // Adjust index since arr[i] is now in a merged run
        }
    }

    // Step 2: Merge runs to produce a single sorted array
    while (run.length > 1) {
        let minRun = Math.min(...run.map(r => r.length));
        let tempRuns = [];
        for (let r of run) {
            if (r.length === minRun) {
                tempRuns.push(r.splice(0)); // Copy the run
            } else {
                let newRun = r.splice(0, minRun);
                tempRuns.push(newRun);
                r.splice(0, minRun);
            }
        }
        run = mergeRuns(...tempRuns);
    }

    return run[0];
}

function mergeRuns(...runs) {
    // Implement merge logic here (simplified)
    return runs.flat(); // Placeholder for actual merge
}

// Example usage:
console.log(timSort([3, 6, 8, 10, 1, 2, 1]));

此代码仅为示例，未实现完整的 TimSort 逻辑。完整的 TimSort 实现涉及复杂的优化和边界条件处理。

回到顶部