原生JS数组sort()排序方法内部原理探究

11,829 阅读4分钟

sort()方法在原数组上进行排序,不生成副本(即会改变原数组)

无参时的使用

此时排序的方式是按照ascii码进行排序,它会先将数组里的元素全部转为字符串(不影响原值),方便比较。

let arr = [23, 12, 32, 5, 21, 7, 1]
    
arr.sort()
//此时原数组已经被改变
console.log(arr)

打印结果

有参数时的使用

先看一下w3school所给的定义

这TM讲的啥??a指代啥?b指的啥?内部用怎样的方法实现的排序??接下来的就是我们研究的重点
首先我们来看一下a指代的到底是什么

let arr = [23, 12, 32, 5, 21, 7, 1]

console.log(arr)
arr.sort((a, b) => {
    console.log("a:" + a)
    return 1
})
console.log(arr)

打印结果

很容易看出a的范围是[arr[1],arr[arr.length-1]](为了避免偶然,我另外还做了许多测试,在这里就不一一列举了)
另外我们还能看出当函数返回一个正值时,数组并没有发生变化(0也是,这里就不演示了)

接下来我么再看一下b指的是什么

let arr = [23, 12, 32, 5, 21, 7, 1]

console.log(arr)
arr.sort((a, b) => {
    console.log("b:" + b)
    return -1
})
console.log(arr)

打印结果

b的范围[arr[0],arr[arr.length-2]另外在这里我们还拾得一个使数组反序的方法(另外一个是数组的reverse()方法) a和b的范围就这样被我们简单的确定了,但在真正排序的时候就不是这样简单了,我们一起来看一下吧

let arr = [23, 12, 32, 5, 21, 7, 1]

console.log(arr)
arr.sort((a, b) => {
    console.log("b:" + b)
    console.log("a:" + a)
    return a - b
})
console.log(arr)

打印结果

惊不惊喜,意不意外??
别慌 我们先把数据整理一下

到了这里我就在猜想sort()内部有没有可能是插入排序,于是我就开始了我的验证

在这里我们证明了,sort()内部采用了 二分法插入排序,不过我在网上查阅的资料上说,如果数组的大小超过了10,就会采用快速排序的方法,我们从下面的测试可以侧面推敲出这一结论

接下来比较一下sort排序和其他排序的性能
sort()

let arr = []
for(let i = 0 ; i < 100000 ; i++){
    arr.push(parseInt(Math.random() * 10000))
}
//performance.now()H5的一个新的api,效果相当于Date.now(),不过它更强大
let startTime = performance.now()
arr.sort((a, b) => {
    return a - b
})
let endTime = performance.now()

console.log(endTime - startTime)

数值有波动,在这里我取得使众数,有兴趣的小伙伴可以自己测试

快排

function quickSort(arr) {
    var len = arr.length;
    //结束递归的条件
    if (len <= 1) return arr;
    var left = [];
    var right = [];
    //中间基数
    var midindex = Math.floor(len / 2);
    var mid = arr[midindex];
    for (var i = 0; i < len; i++) {
        if (arr[i] == mid) continue;
        else if (arr[i] < mid) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return quickSort(left).concat([mid], quickSort(right));
}

let arr = []
for(let i = 0 ; i < 100000 ; i++){
    arr.push(parseInt(Math.random() * 10000))
}

let startTime = performance.now()
quickSort(arr)
let endTime = performance.now()

console.log(endTime - startTime)

插入排序

function insertSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        var k = i;
        //前提: 1  前面必须有内容
        //前提: 2  当前这个元素,比左边小,交换1次
        while (k - 1 >= 0 && arr[k] < arr[k - 1]) {
            var temp = arr[k];
            arr[k] = arr[k - 1];
            arr[k - 1] = temp;
            k--;
        }
    }
    return arr;
}

let arr = []
for(let i = 0 ; i < 100000 ; i++){
    arr.push(parseInt(Math.random() * 10000))
}

let startTime = performance.now()
insertSort(arr)
let endTime = performance.now()

console.log(endTime - startTime)

冒泡排序

 let arr = []
for(let i = 0 ; i < 100000 ; i++){
    arr.push(parseInt(Math.random() * 10000))
}

function bubbleSort(arr) {
    var len = arr.length - 1;//循环次数
    for (var j = len; j > 0; j--) {
        //比较 交换
        for (var i = 0; i < j; i++) {
            if (arr[i] > arr[i + 1]) {
                var tamp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tamp;
            }
        }
    }
    return arr;
    }
let startTime = performance.now()
bubbleSort(arr)
let endTime = performance.now()

console.log(endTime - startTime)

总结

  1. sort()方法没有参数时,按照ascii码进行排序
  2. 通过给sort()的参数返回一个负值可以实现数组reverse()效果
  3. sort(next,prev) 参数返回 next - prev时,数组是升序,返回-(next - prev)prev - next时,数组是降序
  4. 通过以上的比较我们还是可以看出sort()方法效率还是挺高的,可以直接使用
  5. 一般情况下,对数组进行排序使用快速排序或者sort(),在已知数据规律时才考虑其他排序方式