如何高效提取二维数组中指定索引处最小N值所在的行？

我有一个多维数组：

[
[11.7, 18.8, 10.5],
[4.8,   6.3,  3.6],
[6.6,   8.4,  5.2],
[37.8, 80.8, 41.8],
[12.3, 29.2, 10.6],
[16.9, 42.9, 14.8],
[12.8, 30.9, 11.6],
[30.9, 69.5, 32.4],
[5.3,   7.9,  4.7],
[25.4,   57, 25.7],
[11.9, 17.6, 10.4],
[8.8,  13.6,  7.7],
[4.2,   6.2,  3.4],
[7.6,  12.3,  9.6]
]

目标是返回索引0处值最小的N个完整行，并按该值从小到大排序。

原有实现及问题 #

我之前用jQuery的.sort和.slice简单实现：

.sort((a, b) => a[0] - b[0]) // 按指定列排序整个数组
.slice(0, n);  // 截取前N个最小行

当n取3时，结果符合预期：

[
[4.2,  6.2,  3.4],
[4.8,  6.3,  3.6],
[5.3,  7.9,  4.7]
]

但这种方法在数据量较大时效率极低——对整个数组排序的开销太高。我需要先筛选出索引0处值最小的N行，再对这个小集合排序，而非全量排序。

高效实现方案 #

核心思路是维护一个大小为N的“候选集合”，遍历原数组时只保留当前找到的最小N行，最后再对这个小集合排序：

function getTopNMinRows(arr, n) {
    const result = [];
    for (const row of arr) {
        const currentVal = row[0];
        // 候选集合未满，直接加入并按降序排序（方便快速找到当前最大值）
        if (result.length < n) {
            result.push(row);
            result.sort((a, b) => b[0] - a[0]);
        } else {
            // 当前值比候选集合中的最大值小，替换掉最大值
            if (currentVal < result[0][0]) {
                result.shift();
                result.push(row);
                result.sort((a, b) => b[0] - a[0]);
            }
        }
    }
    // 最后将候选集合按升序排序，得到最终结果
    return result.sort((a, b) => a[0] - b[0]);
}

// 测试调用
const originalArray = [
    [11.7, 18.8, 10.5],
    [4.8,   6.3,  3.6],
    [6.6,   8.4,  5.2],
    [37.8, 80.8, 41.8],
    [12.3, 29.2, 10.6],
    [16.9, 42.9, 14.8],
    [12.8, 30.9, 11.6],
    [30.9, 69.5, 32.4],
    [5.3,   7.9,  4.7],
    [25.4,   57, 25.7],
    [11.9, 17.6, 10.4],
    [8.8,  13.6,  7.7],
    [4.2,   6.2,  3.4],
    [7.6,  12.3,  9.6]
];

console.log(getTopNMinRows(originalArray, 3));

优势说明 #

这种方法不需要对整个大数组排序，仅在维护候选集合时做小范围排序（每次排序的元素最多N个）。当原数组规模很大、且N远小于数组长度时，时间复杂度从全排序的O(m log m)（m为数组行数）降到O(m log N)，效率提升显著。

内容的提问来源于stack exchange，提问作者Patrick Hennessey