JavaScript 基于排序描述符对数组进行排序

2021-01-05 | 次 |

JavaScript 中的排序

在 JavaScript 中为数组排序很简单：

1 2	let array = [3, 1, 2] array.sort() // [ 1, 2, 3 ]

Array.prototype.sort() 方法将数组中的元素排序并返回排序后的数组。需要注意的是：此方法会修改原数组。

博文中引用的 Demo 已经上传到 github 上面了，有需要的小伙伴可以去下载

数组的默认排序

当不带参数调用 sort() 方法时，数组元素以 字母表 顺序排序。对于数组中非字符串的元素，会将其转化为字符串后再进行比较。

let array1 = ['banana', 'cherry', 'apple']
array1.sort()  // [ 'apple', 'banana', 'cherry' ]
 
let array2 = [33, 4, 1111, 222]
array2.sort()  // [ 1111, 222, 33, 4 ]
 
let array3 = [NaN, 10, undefined, null, 'Nc']
array3.sort()  // [ 10, NaN, 'Nc', null, undefined ]

注：如果数组中包含 undefined 元素，它们会被排到数组的尾部。

使用比较函数进行排序

通常情况下，这个无参的 sort() 方法可能并不是我们想要的。如果我们想用其它方式而非字母表顺序对数组进行排序，则需要提供一个 比较函数 给 sort() 方法。

1
2
3

let array = [33, 4, 1111, 222]
array.sort((a, b) => a - b)   // 数值升序排列：[ 4, 33, 222, 1111 ]
array.sort((a, b) => b - a)   // 数值降序排列：[ 1111, 222, 33, 4 ]

比较函数 决定了它的两个参数在排好序的数组中的先后顺序。如果想要第一个参数在前，则比较函数需要返回一个小于 0 的数值。反之，则需要返回一个大于 0 的数值。如果是想要保持顺序不变，则需要返回 0。我们可以使用任意的比较函数来对数组进行排序，而这使得 JavaScript 的排序非常强大。

这里我们先实现一个稍微复杂一点的例子，对一个自定义的对象数组进行排序，后面会对它进行重构，并使用排序描述符的方式对它排序。

我们先定义一个数组，其中包含了不同名字和年龄的人：

const person = (first, last, age) => ({ first, last, age })

let people = [
  person('Emmy', 'Yahn', 19),
  person('Lucy', 'Jhon', 27),
  person('Andy', 'Brown', 8),
  person('Robbert', 'Keaven', 36),
  person('Andy', 'Jhon', 31),
  person('Andy', 'Brown', 5)
]

我们想要对这个数组进行排序，规则是先按照姓排序，再按照名排序，最后是年龄。常见的做法是在 比较函数 中依次对需要排序的字段进行处理，如果相同，则继续比较下一个需要排序的字段，直至比较出不同的结果。

我们先对对象中的某一个属性进行排序，实现起来也非常简单：

// 按照 last 属性升序列表
people.sort((p0, p1) => {
  if (p0.last > p1.last)  return 1
  if (p0.last < p1.last)  return -1
  return 0
})

people
/*
[
  { first: 'Andy', last: 'Brown', age: 8 },
  { first: 'Andy', last: 'Brown', age: 5 },
  { first: 'Lucy', last: 'Jhon', age: 27 },
  { first: 'Andy', last: 'Jhon', age: 31 },
  { first: 'Robbert', last: 'Keaven', age: 36 },
  { first: 'Emmy', last: 'Yahn', age: 19 }
]
*/

接下来，我们在 比较函数 中加入新的排序项，同时比较姓和名。先按照 last 属性进行比较，如果相同，则比较 first 属性：

people.sort((p0, p1) => {
  // 按照 last 升序
  if (p0.last > p1.last)  return 1
  if (p0.last < p1.last)  return -1

  // last 相同，按照 first 升序
  if (p0.first > p1.first)  return 1
  if (p0.first < p1.first)  return -1

  return 0
})

people
/*
[
  { first: 'Andy', last: 'Brown', age: 8 },
  { first: 'Andy', last: 'Brown', age: 5 },
  { first: 'Andy', last: 'Jhon', age: 31 },
  { first: 'Lucy', last: 'Jhon', age: 27 },
  { first: 'Robbert', last: 'Keaven', age: 36 },
  { first: 'Emmy', last: 'Yahn', age: 19 }
]
*/

通过这种方式，我们可以实现任何我们想要的排序规则，从而得到我们所期望的排序结果。但问题同样也很明显：随着排序项的增多，比较函数 中的判断逻辑也会随之增加。当需要排序的字段很多时，我们很难直观地看出 比较函数 所要传递出来的意思，这为以后我们修改其中的排序项带来了不便。

使用排序描述符进行排序

前面我们已经介绍过如何通过 比较函数 来对自定义的对象数组进行排序，不过它还存在很大的改善空间，这里我们尝试使用另外一种方式来实现我们想要的效果。

值得一提的是，我们并不会选择去写一个更复杂的函数来进行排序，实际上排序的算法是由 Array 来实现的，我们只是向它传递出了要按照怎样的方式去排序，比如：按照字符串或数字的大小，进行升序、降序排序。

相比于直接将排序的逻辑定义在 比较函数 中，通过定义一组用来描述如何对数组元素进行排序的描述符会是更好的选择。每个描述符中定义了对象的排序规则，通过它可以表达出各自的排序标准。由于 JavaScript 中函数是 一等公民，因此我们可以定义一个描述对象顺序的函数来做为描述符。其中，最简单的一种实现就是接受两个对象作为参数，并在它们顺序正确的时候，返回一个正数。这个函数的结构与 sort() 方法中 比较函数 的结构是一致的。

接下来，让我们回到前面的例子，看如何通过排序描述符来达到我们想要的效果。

// 按照 last 升序
const sortByLast = (p0, p1) => {
  if (p0.last < p1.last)  return -1
  if (p0.last > p1.last)  return 1
  return 0
}

// 按照 first 升序
const sortByFirst = (p0, p1) => {
  if (p0.first < p1.first)  return -1
  if (p0.first > p1.first)  return 1
  return 0
}

这里的 sortByLast 和 sortByFirst 都是一个排序描述符，它们分别描述了用何种方式去对 last 与 first 进行排序。这个地方你可能会有疑惑，这和之前的 比较函数 中的代码并没有什么区别，无非是这里我们将它搬到了指定的函数中。是的，目前来看这样做对我们代码量的减少确实没有太大的作用，不过将具体的排序规则抽离到单独的函数中是有意义的，至少在可读性上面要清晰不少，稍后我们再对它进行优化。

除了手写这些排序描述符外，我们也可以创建一个函数来生成它们。将相同的属性写两次并不太好，比如在 sortByLast 中，我们很容易就会不小心弄成 p0.last 和 p1.first 进行比较。而且写排序描述符本身也挺无聊的：想要通过 first 来排序的时候，很可能你就把 last 排序的 sortByLast 复制粘贴一下，然后再进行修改。

为了避免复制粘贴，我们可以定义一个函数，它接收两个函数作为参数。第一个参数是一个名为 transform 的函数，正如它的名字一样，此函数转换的能力，它接收一个正在排序的数组的元素，并返回这个排序符所要处理的属性值。然后，我们使用第二个参数 orderBy 函数来比较 transform 函数返回的结果。最后，返回我们需要的排序描述符：

1	const descriptor = (transform, orderBy) => (lhs, rhs) => orderBy(transform(lhs), transform(rhs))

transform 函数描述了如何深入一个任意对象的元素，并提取出一个和特定排序步骤相关的值。

有了这个函数，我们就可以用另外一种方式来定义 sortByLast 与 sortByFirst 了：

// 按照 last 升序
const sortByLast = descriptor(item => item.last, (lhs, rhs) => {
  if (lhs > rhs)  return 1
  if (lhs < rhs)  return -1
  return 0
})

// 按照 first 升序
const sortByFirst = descriptor(item => item.first, (lhs, rhs) => {
  if (lhs > rhs)  return 1
  if (lhs < rhs)  return -1
  return 0
})

people.sort(sortByLast)
/*
[
  { first: 'Andy', last: 'Brown', age: 8 },
  { first: 'Andy', last: 'Brown', age: 5 },
  { first: 'Lucy', last: 'Jhon', age: 27 },
  { first: 'Andy', last: 'Jhon', age: 31 },
  { first: 'Robbert', last: 'Keaven', age: 36 },
  { first: 'Emmy', last: 'Yahn', age: 19 }
]
*/

people.sort(sortByFirst)
/*
[
  { first: 'Andy', last: 'Brown', age: 8 },
  { first: 'Andy', last: 'Jhon', age: 31 },
  { first: 'Andy', last: 'Brown', age: 5 },
  { first: 'Emmy', last: 'Yahn', age: 19 },
  { first: 'Lucy', last: 'Jhon', age: 27 },
  { first: 'Robbert', last: 'Keaven', age: 36 }
]
*/

这看上去要比之前的那种方式稍微好一点了，不过仍然存在改善的空间：对于某个已经确定的排序规则，它们的逻辑代码是完全相同的，比如这里的 sortByLast 与 sortByFirst 中的进行比较的代码，它们都是按照 升序 的规则对 last 或 first 进行比较。因此，我们可以将具体描述排序规则的代码抽离出来：升序、降序。

不过在此之前，我们先解决一件事：通过正数、负数来描述两个元素的相对位置可能并不是那么直观，因此，让我们来给它们重新命名一下。由于 JavaScript 中没有枚举的概念，这里我们用一个常量对象来达到同样的效果。

const ComparisonResult = {
  orderedAscending: -1,
  orderedSame: 0,
  orderedDescending: 1
}

然后，我们将 升序 和 降序 的逻辑抽离出来：

// 升序
const ascendingOrder = (a, b) => {
  if (a == b)   return ComparisonResult.orderedSame
  if (a < b)    return ComparisonResult.orderedAscending
  if (a > b)    return ComparisonResult.orderedDescending
}

// 降序
const descendingOrder = (a, b) => {
  if (a == b)   return ComparisonResult.orderedSame
  if (a < b)    return ComparisonResult.orderedDescending
  if (a > b)    return ComparisonResult.orderedAscending
}

甚至，我们还可以再写一个函数专门处理这些比较的逻辑：

const orderBy = (a, b, order) => {
  if (a == b)   return ComparisonResult.orderedSame
  if (a > b)    return order * ComparisonResult.orderedAscending
  if (a < b)    return order * ComparisonResult.orderedDescending
}

最终，我们看到的的函数应该是这个样子的：

// 升序排列
const ascendingOrder = (a, b) => orderBy(a, b, ComparisonResult.orderedAscending)
// 降序排列
const descendingOrder = (a, b) => orderBy(a, b, ComparisonResult.orderedDescending)

const descriptor = (transform = item => item, orderBy = ascendingOrder) => (lhs, rhs) => orderBy(transform(lhs), transform(rhs))

这样，我们就可以用简短清晰得多的方式来重写 sortByLast 和 sortByFirst 了：

const sortByLast = descriptor(item => item.last)
const sortByFirst = descriptor(item => item.first)

people.sort(sortByLast)
/*
[
  { first: 'Andy', last: 'Brown', age: 8 },
  { first: 'Andy', last: 'Brown', age: 5 },
  { first: 'Lucy', last: 'Jhon', age: 27 },
  { first: 'Andy', last: 'Jhon', age: 31 },
  { first: 'Robbert', last: 'Keaven', age: 36 },
  { first: 'Emmy', last: 'Yahn', age: 19 }
]
*/

people.sort(sortByFirst)
/*
[
  { first: 'Andy', last: 'Brown', age: 8 },
  { first: 'Andy', last: 'Brown', age: 5 },
  { first: 'Andy', last: 'Jhon', age: 31 },
  { first: 'Emmy', last: 'Yahn', age: 19 },
  { first: 'Lucy', last: 'Jhon', age: 27 },
  { first: 'Robbert', last: 'Keaven', age: 36 }
]
*/

如果需要添加其它的排序方式也非常简单：

// 按照 `last` 降序排列：
const sortByLastDesc = descriptor(item => item.last, descendingOrder)

people.sort(sortByLastDesc)
/*
[
  { first: 'Emmy', last: 'Yahn', age: 19 },
  { first: 'Robbert', last: 'Keaven', age: 36 },
  { first: 'Lucy', last: 'Jhon', age: 27 },
  { first: 'Andy', last: 'Jhon', age: 31 },
  { first: 'Andy', last: 'Brown', age: 8 },
  { first: 'Andy', last: 'Brown', age: 5 }
]
*/

let array = [1, 9, 3, 7]

array.sort(descriptor())    // [ 1, 3, 7, 9 ]

目前，我们只能用一个单一的 descriptor 函数对数组进行排序。如果想要同时对多个属性进行排序，实现起来也很简单：我们定义了一个把多个排序描述符合并为一个的函数。它首先会使用第一个描述符，并检查比较的结果。如果相等，再使用第二个，第三个，直到全部用完：

const combine = (...descriptors) => {
  return (lhs, rhs) => {
    let result = ComparisonResult.orderedSame
    for (const descriptor of descriptors) {
      result = descriptor(lhs, rhs)
      if (result == ComparisonResult.orderedSame)   continue
      return result
    }
    return result
  }
}

现在我们可以把一开始的例子重写为这样：

// 按照 last 升序
const sortByLast = descriptor(item => item.last)
// 按照 first 升序
const sortByFirst = descriptor(item => item.first)
// 按照 age 降序
const sortByAge = descriptor(item => item.age, descendingOrder)
// 依次按照 last 升序、first 升序、age 降序的规则进行排序
const combined = combine(sortByLast, sortByFirst, sortByAge)

people.sort(combined)
/*
[
  { first: 'Andy', last: 'Brown', age: 8 },
  { first: 'Andy', last: 'Brown', age: 5 },
  { first: 'Andy', last: 'Jhon', age: 31 },
  { first: 'Lucy', last: 'Jhon', age: 27 },
  { first: 'Robbert', last: 'Keaven', age: 36 },
  { first: 'Emmy', last: 'Yahn', age: 19 }
]
*/

通过定义一个个用来描述特定排序规则的描述符，我们可以非常方便地完成对多个属性的排序。而且这种方式的可读性更高，也更容易维护，将来如果需要添加新的排序项，只需再生成一个排序描述符即可。

小结

函数作为 JavaScript 中的一等公民，把函数作为数据来传递的这种方式，为我们实现那些复杂的功能带来了很大的便携性。在本文中，我们通过定义一个个用来描述排序规则的函数，并最终将它们装配到一起，来完成我们想要的效果。我们也看到了合并其它函数的函数的用武之地，它也是函数式编程的构建模块之一。例如：combine() 函数接收一组排序描述符的序列，并将它们合并成了单个的排序描述符。在很多不同的应用场景下，这项技术都非常强大。

1. JavaScript 中的排序
2. 数组的默认排序
3. 使用比较函数进行排序
4. 使用排序描述符进行排序
5. 小结