时间复杂度为 O(m + n) ，可简称为 O(n)
排序流程
- 在两个数组中，从第一项开始，各自设一个指针
- 将两指针对应的元素进行比较，将较小的放入最终数组中，若两元素相同，就都放入最终数组中，若有一个指针没有数据，则将有数据的指针放入最终数组中
- 比较完成后，移除元素的数组的指针右移，直至两个指针都不再有元素。
代码实现
function twoPointerSort(arr1, arr2) { const result = []; let i = 0; let j = 0; // 只要 arr1 或 arr2 还有值，就继续循环 while (arr1[i] != null || arr2[j] != null) { const v1 = arr1[i]; const v2 = arr2[j]; // arr1 和 arr2 都没有值了，则停止 if (v1 == null && v2 == null) { break; } if (v1 < v2 || v2 == null) { // v1 较小，则只拼接 v1 result.push(v1); i++; } if (v1 > v2 || v1 == null) { // v2 较小，则只拼接 v2 result.push(v2); j++; } if (v1 === v2) { // v1 v2 相等，则都拼接 result.push(v1); i++; result.push(v2); j++; } } return result; }
测试效果
const arr1 = [1, 3, 5, 7, 9]; const arr2 = [2, 4, 6, 8]; const finalArray = twoPointerSort(arr1, arr2); console.log(finalArray);
结果
[ 1, 2, 3, 4, 5, 6, 7, 8, 9]
为什么不用 concat + sort 实现 ？
因为时间复杂度高，至少是 O(n*logn)
const res = arr1.concat(arr2).sort((a, b) => a - b) console.log(res)
