JS `Array.prototype.sort()` 的稳定排序 (ES2019)：保持相同元素相对顺序

各位听众，早上好/下午好/晚上好！今天咱们来聊聊 JavaScript 里一个既熟悉又有点小神秘的家伙：Array.prototype.sort()。这玩意儿大家天天用，但要说把它摸透了，能准确预测它排序后的结果，很多人可能就得挠头了。

特别地，我们要聚焦在 ES2019 引入的一个重要特性：稳定排序。这可不是什么玄学魔法，而是一个实实在在的改进，让 sort() 变得更加可预测和可靠。

sort() 的老脾气：不稳定排序的那些年

在 ES2019 之前，JavaScript 的 sort() 方法在不同浏览器、不同 JavaScript 引擎下的实现可能是不一样的。这意味着，对于那些“相等”的元素（根据你的比较函数判断），它们的相对顺序可能会被打乱。

举个例子，假设我们有一个数组，表示员工信息：

const employees = [
  { name: 'Alice', department: 'Sales', seniority: 5 },
  { name: 'Bob', department: 'Marketing', seniority: 3 },
  { name: 'Charlie', department: 'Sales', seniority: 3 },
  { name: 'David', department: 'Engineering', seniority: 5 },
];

我们想按照 seniority (资历) 对员工进行排序，如果资历相同，我们不在乎他们的相对顺序。

employees.sort((a, b) => a.seniority - b.seniority);
console.log(employees);

在 ES2019 之前的环境中，你可能会发现，虽然 Alice 和 David 的资历都是 5，Bob 和 Charlie 的资历都是 3，但每次运行的结果中，Alice 和 David 的相对顺序、Bob 和 Charlie 的相对顺序都可能不一样！这就是不稳定排序的特点。

这种不确定性在某些情况下可能会导致问题。比如，如果你依赖于原始数据的顺序进行后续处理，不稳定排序可能会破坏你的逻辑。

ES2019 的福音：稳定排序来了！

ES2019 (ECMAScript 2019) 规范明确要求 Array.prototype.sort() 必须是稳定排序。这意味着，对于那些比较结果相等的元素，它们在排序后的数组中的相对顺序，必须与它们在原始数组中的相对顺序保持一致。

还是上面的例子，在 ES2019+ 的环境中，无论你运行多少次，Alice 永远会在 David 前面，Bob 永远会在 Charlie 前面。

稳定排序的优势：可预测性和可靠性

稳定排序的最大优势在于它的可预测性和可靠性。它消除了排序结果的不确定性，让你可以更加放心地使用 sort() 方法，而不用担心它会破坏你的数据结构或算法逻辑。

如何判断你的环境是否支持稳定排序？

虽然 ES2019 规范要求稳定排序，但并非所有浏览器和 JavaScript 引擎都立即实现了这一特性。你可以通过以下方式来判断你的环境是否支持稳定排序：

function isStableSortSupported() {
  const array = [{ value: 1 }, { value: 1 }, { value: 1 }];
  const sortedArray = array.sort((a, b) => a.value - b.value);
  return sortedArray[0] === array[0] && sortedArray[1] === array[1] && sortedArray[2] === array[2];
}

console.log("Is stable sort supported?", isStableSortSupported());

这段代码创建了一个包含三个相同对象的数组，然后对它进行排序。如果排序是稳定的，那么排序后的数组应该与原始数组完全相同（因为所有元素的 value 都相等）。如果排序是不稳定的，那么排序后的数组中的元素顺序可能会发生变化。

更实际的例子：多条件排序

稳定排序在多条件排序的场景下尤其有用。假设我们需要先按照部门 (department) 排序，然后按照资历 (seniority) 排序。

const employees = [
  { name: 'Alice', department: 'Sales', seniority: 5 },
  { name: 'Bob', department: 'Marketing', seniority: 3 },
  { name: 'Charlie', department: 'Sales', seniority: 3 },
  { name: 'David', department: 'Engineering', seniority: 5 },
  { name: 'Eve', department: 'Marketing', seniority: 5 },
  { name: 'Frank', department: 'Engineering', seniority: 3 },
];

employees.sort((a, b) => {
  const departmentComparison = a.department.localeCompare(b.department);
  if (departmentComparison !== 0) {
    return departmentComparison;
  }
  return a.seniority - b.seniority;
});

console.log(employees);

在支持稳定排序的环境中，这段代码会先按照部门排序，然后在每个部门内部按照资历排序。例如，Engineering 部门的员工会排在 Marketing 部门的员工前面，而 Engineering 部门内部，Frank 会排在 David 前面，因为 Frank 的资历是 3，David 的资历是 5。

如果没有稳定排序，即使我们先按照部门排序，然后再按照资历排序，结果也可能不是我们想要的。例如，Engineering 部门内部的 Frank 和 David 的相对顺序可能会被打乱。

稳定排序的实现原理 (简要版)

稳定排序的实现方式有很多种，常见的包括归并排序 (Merge Sort) 和插入排序 (Insertion Sort) 的变种。这些算法都保证了在比较过程中，不会改变相等元素的相对顺序。

JavaScript 引擎通常会选择一种高效且稳定的排序算法来实现 Array.prototype.sort()。具体实现细节可能因引擎而异，但最终结果必须符合 ES2019 规范的要求。

sort() 的比较函数：你的排序规则

sort() 方法接受一个可选的比较函数作为参数。这个比较函数决定了数组元素的排序规则。比较函数应该接受两个参数 (a, b)，并返回以下值：

如果 a 应该排在 b 之前，则返回一个小于 0 的值。
如果 a 应该排在 b 之后，则返回一个大于 0 的值。
如果 a 和 b 相等 (相对顺序无关紧要)，则返回 0。

如果你不提供比较函数，sort() 方法会默认将数组元素转换为字符串，并按照 Unicode 编码进行排序。这通常不是我们想要的行为，所以建议始终提供比较函数。

一些 sort() 的使用技巧

数字排序： 使用 (a, b) => a - b 进行升序排序，使用 (a, b) => b - a 进行降序排序。

const numbers = [3, 1, 4, 1, 5, 9, 2, 6];
numbers.sort((a, b) => a - b); // 升序
console.log(numbers); // [1, 1, 2, 3, 4, 5, 6, 9]
numbers.sort((a, b) => b - a); // 降序
console.log(numbers); // [9, 6, 5, 4, 3, 2, 1, 1]

字符串排序： 使用 localeCompare() 方法进行字符串排序，它可以处理不同语言的排序规则。

const names = ['Alice', 'Bob', 'Charlie', 'David'];
names.sort((a, b) => a.localeCompare(b)); // 升序
console.log(names); // ["Alice", "Bob", "Charlie", "David"]

对象排序： 根据对象的属性进行排序。

const products = [
  { name: 'Laptop', price: 1200 },
  { name: 'Mouse', price: 25 },
  { name: 'Keyboard', price: 75 },
];
products.sort((a, b) => a.price - b.price); // 按照价格升序
console.log(products);

多条件排序： 按照多个属性进行排序。

const employees = [
  { name: 'Alice', department: 'Sales', seniority: 5 },
  { name: 'Bob', department: 'Marketing', seniority: 3 },
  { name: 'Charlie', department: 'Sales', seniority: 3 },
  { name: 'David', department: 'Engineering', seniority: 5 },
];
employees.sort((a, b) => {
  const departmentComparison = a.department.localeCompare(b.department);
  if (departmentComparison !== 0) {
    return departmentComparison;
  }
  return a.seniority - b.seniority;
});
console.log(employees);

sort() 的性能：需要注意的地方

虽然 sort() 方法很方便，但它的性能并不是最好的。sort() 的平均时间复杂度是 O(n log n)，在最坏情况下可能会达到 O(n^2)。对于大型数组，排序可能会比较耗时。

如果你需要对性能要求很高的场景进行排序，可以考虑使用其他更高效的排序算法，例如快速排序 (Quick Sort) 或堆排序 (Heap Sort)。当然，这些算法的实现也更加复杂。

sort() 的一些“坑”

sort() 会修改原始数组： 这是 sort() 方法的一个重要特点。如果你不想修改原始数组，可以先创建一个副本，然后再对副本进行排序。

const originalArray = [3, 1, 4, 1, 5, 9, 2, 6];
const sortedArray = [...originalArray].sort((a, b) => a - b); // 创建副本
console.log("Original Array:", originalArray); // [3, 1, 4, 1, 5, 9, 2, 6]
console.log("Sorted Array:", sortedArray);   // [1, 1, 2, 3, 4, 5, 6, 9]

比较函数必须一致： 比较函数必须始终返回一致的结果。如果比较函数返回的结果不一致，sort() 方法的行为将是未定义的。

总结

Array.prototype.sort() 是 JavaScript 中一个非常常用的方法，用于对数组进行排序。ES2019 引入的稳定排序特性让 sort() 变得更加可预测和可靠。在使用 sort() 方法时，需要注意以下几点：

始终提供比较函数，以确保排序结果符合你的预期。
了解 sort() 会修改原始数组，如果不想修改原始数组，需要先创建一个副本。
考虑 sort() 的性能，对于大型数组，可以考虑使用其他更高效的排序算法。

特性	ES2019 之前	ES2019 之后
稳定性	不稳定	稳定
修改原始数组	是	是
默认排序	字符串	字符串

希望今天的讲解能够帮助大家更好地理解和使用 Array.prototype.sort() 方法。掌握了稳定排序的特性，你就能更加自信地驾驭 JavaScript 中的排序操作，写出更加健壮和可靠的代码。

谢谢大家！

发表回复 取消回复

发表回复取消回复