JS

JS-数组排序

wujiawen 发布于

阅读量

JS-数组排序 Array.sort()

Array.sort() 基本使用

语法

1
arrayObject.sort(sortby)

参数 sortby：

  • 可选
  • 必须是函数

不传参数时，默认将按字母顺序对数组中的元素进行排序，说得更精确点，是按照字符编码(Unicode编码)的顺序进行排序
所以，若数组是数字，想按大小排序，不传参是无法实现的（内部比较的是字符编码的顺序）

如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值
然后返回一个用于说明这两个值的相对顺序的数字
比较函数应该具有两个参数 a 和 b，其返回值如下：

  • 若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值
  • 若 a 等于 b，则返回 0
  • 若 a 大于 b，则返回一个大于 0 的值

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function sortNumber (a, b) {
  return a - b
}
const arr = [1, 6, 3, 9, 7, 10]
arr.sort(sortNumber)
console.log(arr) // 排序后输出 [1, 3, 6, 7, 9, 10]

// 若比较的是对象数组
function sortObjArray (a, b) {
  return a.age - b.age
}
const arr = [
  { name: '张三', age: 20 },
  { name: '李四', age: 23 },
  { name: '王五', age: 18 }
]
arr.sort(sortObjArray)
console.log(arr)
/**
 * 输出：
 * {name: "王五", age: 18}
 * {name: "张三", age: 20}
 * {name: "李四", age: 23}
 */

返回值：

  • 返回对数组的引用
  • 请注意，数组在原数组上进行排序，不生成副本
关于localeCompare

语法

1
stringObject.localeCompare(target)

以本地特定的顺序，对字符串进行比较
同样的，返回值也是三种

  • stringObject 小于 target，则 localeCompare() 返回小于 0 的数
  • 两个字符串相等，或根据本地排序规则没有区别，该方法返回 0
  • 如果 stringObject 大于 target，则该方法返回大于 0 的数

(这里的大小，是指位置顺序大小)

使用场景：
通常用于姓名的排序上

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function sortObjArray (a, b) {
  return a.name.localeCompare(b.name)
}
const arr = [
  { name: '张三', age: 20 },
  { name: '李四', age: 23 },
  { name: '王五', age: 18 },
  { name: '张三', age: 18 }
]
arr.sort(sortObjArray)
/**
 * 输出：
 * {name: "李四", age: 23}
 * {name: "王五", age: 18}
 * {name: "张三", age: 20}
 * {name: "张三", age: 18}
 */

注意：
必须是字符串才能调用此方法

Array.sort() 实现原理

接下来了解一下 sort() 方法的内部实现，有助于更好地运用此方法

不同浏览器，对于 sort() 方法的实现有所不同

Mozilla/Firefox：

  • 归并排序（稳定排序）

Webkit：

  • 底层实现用了 C++ 库中的 qsort() 方法

chrome浏览器的话，V8 v7.0以前：

V8 v7.0之后：

  • 改进了排序算法
  • 换成了使用Torque实现的Timsort算法
  • 从V8 v7.0和Chrome 70开始可用
  • 改进之后的排序，是稳定的

v8博客-排序篇：
https://v8.dev/blog/array-sort

查资料参考：
https://zhuanlan.zhihu.com/p/81204554

小小科普：

  • 在Chrome中，只有Html的渲染采用了WebKit
  • JavaScript解析使用V8引擎
还有一个关于chrome浏览器排序会出现的小问题

当排序的是对象数组时，我们会传入自定义的比较函数，用对象的某一属性来作比较
若某个对象的该属性值为undefined，排序结果可能会与预期不符

看个示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function sortObjArray (a, b) {
  return a.age - b.age
}
const arr = [
  { id: 1, age: 20 },
  { id: 2, age: 16 },
  { id: 3, age: undefined },
  { id: 4, age: undefined },
  { id: 5, age: 18 },
  { id: 6, age: 25 },
  { id: 7, age: 17 },
  { id: 8, age: undefined },
  { id: 9, age: 23 }
]
arr.sort(sortObjArray)
console.log(arr)
/**
 * 输出：
 * {id: 2, age: 16}
 * {id: 1, age: 20}
 * {id: 3, age: undefined}
 * {id: 4, age: undefined}
 * {id: 7, age: 17}
 * {id: 5, age: 18}
 * {id: 9, age: 23}
 * {id: 6, age: 25}
 * {id: 8, age: undefined}
 */

arr2 = [
  { id: 1, age: 20 },
  { id: 2, age: undefined },
  { id: 3, age: undefined },
  { id: 4, age: 18 },
]
/**
 * 输出：
 * {id: 1, age: 20}
 * {id: 2, age: undefined}
 * {id: 3, age: undefined}
 * {id: 4, age: 18}
 */

会发现，2个undefined上下，并没有排序，原因也很简单
我们的排序函数是年龄相减，而 undefined 与任何数 相减都是 NaN
而 NaN 参与运算，都是 false
所以根据比较结果，会直接判断undefined属于该位置
所以，undefined前后的值，会出现排序断层

若我们修改一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
let arr = [
  { id: 1, age: 20 },
  { id: 2, age: 16 },
  { id: 3, age: undefined },
  { id: 4, age: undefined },
  { id: 5, age: 18 },
  { id: 6, age: 25 },
  { id: 7, age: 17 },
  { id: 8, age: undefined },
  { id: 9, age: 23 }
]
arr = arr.map(item => item.age)
arr.sort((a, b) => {
  return a - b
})
/**
 * 输出：
 * [20, 16, 18, 25, 17, 23, undefined, undefined, undefined]
 */

可以发现，我们用基本数据类型的数组排序的话，undefined是会放到最后，并且非undefined的数据都会排序
这是因为chrome浏览器对数组的值做了处理，若是undefined的话，会移到最后，并且不进行排序

关于排序算法的稳定性

  • 2个相等的数，排序前后，位置顺序不变的，就是稳定排序
    （这里的位置顺序，指的是前后位置顺序）

  • 例如：
    Ai = Aj
    排序前，Ai 在 Aj 前面
    排序之后，Ai 也要在 Aj 前面

  • 了解算法的稳定性后，我们才能知道，什么时候要用稳定排序，什么时候不需要用稳定排序
    比如，我们要排序的是一个对象数组，我们仅针对对象的年龄属性排序
    若用不稳定排序，当年龄相同时，该对象的相对位置却是不固定的
    若需要列表展示，姓名 + 年龄
    就会出现姓名列不断变动的情况，这是要避免的情况
    此时就需要用稳定排序了

排序算法实现思路

插入排序（InsertionSort）

时间复杂度：O(N^(1-2))

最优的情况：
当待排序数组是有序时，只需当前数跟前一个数比较一下就可以了
这时一共需要比较N- 1次，时间复杂度为 O(N)

最坏的情况：
待排序数组是逆序的，此时需要比较次数最多
总次数记为：1+2+3+…+N-1
所以，插入排序最坏情况下的时间复杂度为 O(N^2)

空间复杂度：O(1)

  • 思想：
    将数据分两个区间，已排序区间和未排序区间，初始已排序区间只有一个元素，就是数组的第一个元素
    在未排序区间中依次取出元素并插入到已排序区间的合适位置
    重复这个步骤直到未排序区间元素为空

  • 步骤

    1. 将第一个元素定为已排序数据，后面的都是未排序数据
    2. 取出下一个元素（从第二个元素开始），在已排序数据中，从右往左，依次比较
    3. 被取出元素与已排序数据比较，若满足排序条件（自定义），则被取元素插入到该已排序数据前
    4. 继续往左比较，重复步骤3，直到不满足排序条件，则被取元素位置确定
    5. 重复步骤2，3，4

实现(javaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 插入排序
 * 内部默认实现：比较函数返回值大于0，表示满足交换条件(即默认升序)
 */
// （写法一）
function insertionSort (arr, comparefn, orderFrom, orderTo) {
  const from = orderFrom || 0, to = orderTo || arr.length
  if (!comparefn) {
    comparefn = function (a, b) {
      return a - b
    }
  }
  for (let i = from + 1; i < to; i++) {
    const element = arr[i]
    for (let j = i - 1; j >= from; j-- ) {
      const order = comparefn(arr[j], element)
      if (order > 0) {
        arr[j + 1] = arr[j]
        arr[j] = element
      } else {
        break
      }
    }
  }
}

// （写法二）
function insertionSort (arr, comparefn, orderFrom, orderTo) {
  const from = orderFrom || 0, to = orderTo || arr.length
  if (!comparefn) {
    comparefn = function (a, b) {
      return a - b
    }
  }
  for (let i = from + 1; i < to; i++) {
    for (let j = i - 1; j >= from; j-- ) {
      const order = comparefn(arr[j], arr[j+1])
      if (order > 0) {
        const temp = arr[j+1]
        arr[j + 1] = arr[j]
        arr[j] = temp
      } else {
        break
      }
    }
  }
}

实现的时候，有一个要注意的点就是：

  • 在用未排序数据，对已排序数据进行扫描时（从第二个元素开始，依次往前扫描）
  • 要确保元素交换后，进行比较的还是原先的那个未排序数据的值
  • 可以先把该未排序元素保存起来，用保存的副本，与已排序数据进行比较（第一种写法）
  • 也可以每次比较，都用交换后的值与下一个未排序值比较（第二种写法）

建议亲自尝试写一下，就不会觉得乱了~

（未完待续…）
（持续更新…）