ES6中如何实现两个数组的插入排序

Question

假设我有两个数组：

arr1 - [90, 44, 64, 16, 24, 20, 64, 86, 20, 64, 56, 72, 16]

和

arr2 - [21, 13, 9, 13, 15, 7, 17, 15, 9, 19, 7, 15, 9]

我想对两个数组实现插入排序，并接收排序后的结果数组：

[
  90, 86, 72, 64, 64, 64, 56, 44,
  24, 21, 20, 20, 19, 17, 16, 16,
  15, 15, 15, 13, 13,  9,  9,  9,
   7,  7
]

我知道我可以通过以下方式间接实现它：

resultArray = arr1.concat(arr2).sort(function(a, b) {return b - a});

但就性能而言，这不是最佳解决方案。

对于如何使用 ES6 实现上述假设的建议，我将不胜感激。

Answer 1

您可以分别对数组进行排序然后合并它们：

const sarr1 = arr1.sort((a, b) => b - a);
const sarr2 = arr2.sort((a, b) => b - a);
const tot = [];
let arr1i = 0;
let arr2i = 0;
while (arr1i < sarr1.length && arr2i < sarr2.length) {
    if (sarr1[arr1i] >= sarr2[arr2i]) {
        tot.push(sarr1[arr1i]);
        arr1i++;
    } else {
        tot.push(sarr2[arr2i]);
        arr2i++;
    }
}
while (arr1i < sarr1.length) {
    tot.push(sarr1[arr1i ++]);
}
while (arr2i < sarr2.length) {
    tot.push(sarr2[arr2i ++]);
}
// tot now contains the fully sorted array

Answer 2

使用扩展运算符连接，然后箭头函数排序：

let arr1 = [90, 44, 64, 16, 24, 20, 64, 86, 20, 64, 56, 72, 16];
let arr2 = [21, 13, 9, 13, 15, 7, 17, 15, 9, 19, 7, 15, 9];

let resultArray = [...arr1, ...arr2].sort((a, b) => b - a);

console.log("arr1:");
console.log("["+arr1.join(", ")+"]");
console.log("arr2:");
console.log("["+arr2.join(", ")+"]");
console.log("resultArray:");
console.log("["+resultArray.join(", ")+"]");

.as-console-wrapper { max-height: 100% !important; top: 0; }

测试更大的数组：

let arr1 = [90, 44, 64, 16, 24, 20, 64, 86, 20, 64, 56, 72, 16];
let arr2 = [21, 13, 9, 13, 15, 7, 17, 15, 9, 19, 7, 15, 9];

for(let i=0; i<10; i++) {
  arr1 = arr1.concat(arr1);
  arr2 = arr2.concat(arr2);
};

let start = null;
let resultArray = null;

start=new Date();
resultArray = [...arr1, ...arr2].sort((a, b) => b - a);
console.log("First resultArray took " + (Date.now() - start) + "ms");

start = null;
resultArray = null;
start=new Date();
resultArray = arr1.concat(arr2).sort(function(a, b) {return b - a});
console.log("Second resultArray took " + (Date.now() - start) + "ms");

.as-console-wrapper { max-height: 100% !important; top: 0; }

似乎 let resultArray = [...arr1, ...arr2].sort((a, b) => b - a); 比 resultArray = arr1.concat(arr2).sort(function(a, b) {return b - a}); 花费的时间更长...

ES6中如何实现两个数组的插入排序

How to implement insertion sort for two arrays in ES6

javascript

arrays

sorting

insertion-sort