JavaScript中Sort函数

由于昨天看了几个排序,又想到 JavaScript 常用Array.sort进行排序,所以搜索了一下 JavaScript 中 sort 函数使用了那种排序方法。

sort() 方法在适当的位置对数组进行排序,并返回数组,同时 sort 排序不一定是稳定的 – MDN 文档

语法

arr.sort()

arr.sort(compareFunction)

sort()函数默认根据字符串 Unicode 码点进行排序

比如

arr.sort()

1
2
3
4
5
6
7
8
var a = ['cherries', 'apples', 'bananas']

a.sort(); //['apples', 'bananas', 'cherries']

var b = [1, 10, 21, 2];

b.sort(); //[1, 10, 2, 21]
// 因为在Unicode指针顺序中'10'在'2'之前

这种这种按 Unicode 顺序排序一般不符合使用要求。 所以大多都会使用

arr.sort(compareFunction)

给 sort 函数传一个比较函数

如果指明了 compareFunction ,那么数组会按照调用该函数的返回值排序。即 a 和 b 是两个将要被比较的元素:

如果 compareFunction(a, b) 小于 0 ,那么 a 会被排列到 b 之前; 如果 compareFunction(a, b) 等于 0 , a 和 b 的相对位置不变。备注: ECMAScript 标准并不保证这一行为,而且也不是所有浏览器都会遵守(例如 Mozilla 在 2003 年之前的版本); 如果 compareFunction(a, b) 大于 0 , b 会被排列到 a 之前。 compareFunction(a, b) 必须总是对相同的输入返回相同的比较结果,否则排序的结果将是不确定的。

谷歌搜了一下在谷歌浏览器的 v8 引擎中 sort 只有两种方法 对于长度小于等于 10 的数组使用插入排序, 长度大于 10 的数组使用快速排序。 具体看V8 源码

我看不懂

看了很多博客介绍

插入排序

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

function insertionSort(arr) {
// 声明一个函数函数接受一个数组作为参数
for (var i = 1; i < arr.length; i++) {
// 使用for进行循环
var element = arr[i];
// 储存当前循环的值
for (var j = i - 1; j >= 0; j--) {
// 嵌套循环,获取arr[i]的前一个
var tmp = arr[j];
var order = tmp - element;
// 对比前一个和当前的值
if (order > 0) {
// 如果前一位大于后一位
arr[j + 1] = tmp;
// 将前一位放到后一位的位置
} else {
break;
}
}
arr[j + 1] = element;
}
return arr;
}

var arr = [6, 5, 4, 3, 2, 1];
console.log(insertionSort(arr));