排序算法是计算机科学中的重要概念，它用于将一组数据按照指定的顺序排列。在 JavaScript 中，常见的排序算法包括冒泡排序、插入排序和快速排序等。本文将介绍一种高效的排序算法：merge-sort，并展示如何在 ECMAScript 2021 中实现它。
什么是 merge-sort
Merge-sort 是一种分而治之的排序算法，它将待排序的数组分成两个子数组，分别排序，然后合并两个有序数组。这个过程不断地递归执行，直到所有的子数组排序完成。
Merge-sort 算法的时间复杂度为 O(nlogn)，是一种非常高效的排序算法。它是稳定的，也就是说，排序前相等的数据，在排序后它们的相对位置不会改变。
ECMAScript 2021 中的 merge-sort
在 ECMAScript 2021 中，Array 原型已经新增了 sort() 方法，该方法采用“tim sort”算法来排序数组。Tim sort 算法将用到 merge-sort 算法的实现。我们可以使用这个方法来排序 JavaScript 数组。
下面是一个简单的示例：
let arr = [5, 2, 8, 4, 1]; arr.sort((a, b) => a - b); // 升序排列 console.log(arr); // [1, 2, 4, 5, 8]
sort() 方法采用一个比较函数，该函数用于确定两个元素之间的顺序。如果 a 小于 b，则比较函数返回一个负数，如果 a 大于 b，则返回一个正数，如果 a 等于 b，则返回 0。
上面的代码用 sort() 方法将数组升序排列。如果要降序排列，则可以改变比较函数的返回值。
自己实现 merge-sort
虽然 sort() 方法的性能已经很好，但有时候我们可能需要自己手动实现 merge-sort，例如我们需要排序的不是数组，而是一个 JavaScript 对象数组，我们需要指定按照哪个属性排序。
下面是一个使用 ECMAScript 2021 实现 merge-sort 的示例代码：
function mergeSort(arr, compareFn) {
if (arr.length < 2) return arr;
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left, compareFn), mergeSort(right, compareFn), compareFn);
}
function merge(left, right, compareFn) {
let i = 0, j = 0;
const result = [];
while (i < left.length && j < right.length) {
result.push(compareFn(left[i], right[j]) < 0 ? left[i++] : right[j++]);
}
return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}mergeSort() 函数实现了递归的分治思想。它将数组分成两半，然后将两个子数组递归排序。当子数组长度小于 2 时停止递归，此时已经排好序的两个子数组可以使用 merge() 函数合并。
merge() 函数接受两个有序数组，它将它们合并成一个有序数组。它使用了双指针技巧，不断比较两个数组的首元素，将较小的元素放入结果数组中，直到一个数组为空。
总结
本文介绍了 JavaScript 中的一个高效排序算法：merge-sort，该算法具有 O(nlogn) 的时间复杂度和稳定性。在 ECMAScript 2021 中，我们可以使用 Array.sort() 方法来实现 merge-sort。如果需要自己手动实现 merge-sort，我们可以使用递归的分治思想和双指针技巧。拥有了这些知识后，我们可以更好地理解 JavaScript 中的排序算法，并且可以在工作中更高效地处理排序问题。
来源：JavaScript中文网 ，转载请注明来源 本文地址：https://www.javascriptcn.com/post/65a5e90dadd4f0e0ffe7b782