简介
ECMAScript 2019（ES10）是 JavaScript 的最新版本，它增加了一些新的特性和语法，包括 Array.prototype.flat()、Array.prototype.flatMap()、String.prototype.trimStart()、String.prototype.trimEnd() 等。在这篇文章中，我们将重点介绍如何使用 Array.prototype.sort() 进行稳定的排序。
稳定的排序
在进行排序时，有时我们需要保持相等元素的相对顺序，这种排序方式被称为稳定的排序。例如，我们有一个数组 [5, 2, 3, 5, 1]，如果我们对它进行非稳定的排序，它可能会变成 [1, 2, 3, 5, 5] 或者 [2, 1, 3, 5, 5]，但如果我们对它进行稳定的排序，它将会变成 [1, 2, 3, 5, 5]。
Array.prototype.sort() 方法
在 JavaScript 中，我们可以使用 Array.prototype.sort() 方法对数组进行排序。该方法可以接收一个可选的比较函数作为参数，用于指定排序规则。如果不传递比较函数，则会将数组元素转换成字符串并按照 Unicode 顺序进行排序。
以下是一个简单的示例：
const arr = [5, 2, 3, 5, 1]; arr.sort(); // [1, 2, 3, 5, 5]
但是，这种排序方式是非稳定的，如果我们想要进行稳定的排序，就需要传递一个比较函数作为参数。比较函数接收两个参数，表示要比较的两个元素，如果第一个元素应该排在第二个元素之前，则返回一个负数，如果第一个元素应该排在第二个元素之后，则返回一个正数，如果两个元素相等，则返回 0。
以下是一个使用比较函数进行稳定排序的示例：
const arr = [{ name: 'Alice', age: 25 }, { name: 'Bob', age: 20 }, { name: 'Charlie', age: 25 }];
arr.sort((a, b) => a.age - b.age); // [{ name: 'Bob', age: 20 }, { name: 'Alice', age: 25 }, { name: 'Charlie', age: 25 }]在上面的示例中，我们传递了一个比较函数，该函数按照元素的 age 属性进行比较，所以最终结果是按照 age 升序排列的。
实现稳定排序
在 JavaScript 中，实现稳定排序的方式有很多种，下面我们将介绍两种常见的方式。
1. 辅助数组法
辅助数组法是一种比较简单的实现稳定排序的方式。它的基本思想是，创建一个与原数组大小相同的辅助数组，然后将原数组的元素复制到辅助数组中，并在复制时记录原数组中每个元素的下标。然后对辅助数组进行排序，最后再根据记录的下标将排序后的元素复制回原数组。
以下是一个使用辅助数组法实现稳定排序的示例：
-- -------------------- ---- -------
-------- --------------- -------- -
----- --- - -----------
----- ------- - --- -----------
--- ---- - - -- - - ---- ---- -
---------- - --
-
---------------- -- -- --------------- ------- -- - - ---
----- ------ - --- -----------
--- ---- - - -- - - ---- ---- -
--------- - ----------------
-
------ -------
-
----- --- - -- ----- -------- ---- -- -- - ----- ------ ---- -- -- - ----- ---------- ---- -- ---
--------------- --- -- -- ----- - ------- -- -- ----- ------ ---- -- -- - ----- -------- ---- -- -- - ----- ---------- ---- -- --在上面的示例中，我们定义了一个 stableSort 函数，该函数接收一个数组和一个比较函数作为参数，返回一个经过稳定排序后的新数组。在函数内部，我们首先创建了一个与原数组大小相同的 indexes 数组，用于记录每个元素的下标。然后对 indexes 数组进行排序，排序规则是先按照比较函数进行比较，如果比较结果为 0，则按照下标进行比较。最后根据排序后的 indexes 数组，将原数组的元素复制到 result 数组中，返回 result 数组。
2. 归并排序法
归并排序是一种比较高效的实现稳定排序的方式。它的基本思想是，将原数组分成两个部分，分别进行排序，然后将两个有序数组合并成一个有序数组。在合并时，如果两个数组中有相等的元素，我们可以选择将前一个数组中的元素放在前面，这样就可以保持相等元素的相对顺序。
以下是一个使用归并排序法实现稳定排序的示例：
-- -------------------- ---- -------
-------- --------------- -------- -
-- ----------- -- -- -
------ ----
-
----- --- - --------------------- - ---
----- ---- - ------------ -----
----- ----- - ---------------
------ ---------------------- --------- ----------------- --------- ---------
-
-------- ----------- ------ -------- -
----- ------ - ---
--- - - --
--- - - --
----- -- - ----------- -- - - ------------- -
-- ----------------- --------- -- -- -
-----------------------
- ---- -
------------------------
-
-
----- -- - ------------ -
-----------------------
-
----- -- - ------------- -
------------------------
-
------ -------
-
----- --- - -- ----- -------- ---- -- -- - ----- ------ ---- -- -- - ----- ---------- ---- -- ---
--------------- --- -- -- ----- - ------- -- -- ----- ------ ---- -- -- - ----- -------- ---- -- -- - ----- ---------- ---- -- --在上面的示例中，我们定义了一个 stableSort 函数，该函数接收一个数组和一个比较函数作为参数，返回一个经过稳定排序后的新数组。在函数内部，我们首先判断数组长度是否小于等于 1，如果是，则直接返回原数组。否则，我们将原数组分成两个部分，分别进行排序，然后将两个有序数组合并成一个有序数组。在合并时，我们使用比较函数进行比较，如果两个元素相等，则将前一个数组中的元素放在前面。
结论
在本文中，我们介绍了 ECMAScript 2019（ES10）中如何使用 Array.prototype.sort() 进行稳定的排序。我们首先介绍了稳定排序的概念，然后介绍了 Array.prototype.sort() 方法和比较函数的使用。最后，我们介绍了两种常见的实现稳定排序的方式，辅助数组法和归并排序法。这些内容对于前端开发人员来说具有深度和学习以及指导意义，可以帮助我们更好地理解 JavaScript 的排序机制，并提高代码的效率和可读性。
来源：JavaScript中文网 ，转载请注明来源 https://www.javascriptcn.com/post/676691fa76af2b9a20f8d691