常见前端排序方式对比-白红宇

常见前端排序方式对比

阅读量：6418 次

发布时间：2019-06-23

本文共 3668 字，大约阅读时间需要 12 分钟。

首先需要一个自动生成数组的函数

// 自动生成数组的函数    function randomArr (n) {        let arr = [];        for (let i = 1; i <= n; i++) {            arr.push(Math.floor(Math.random() * (i + 1)));        }        return arr;    }

执行上面函数，的到的arr1数组长度为50000，因为js执行速度很快，只有长度很大时，才能看到各个方法的执行速度的差别

注意 arr2到arr6不能简单的用赋值，否则arr1改变后，arr2到arr6也相应改变了

// 六个相同的数组 并且数组长度要足够大才能对比出来    let arr1 = randomArr(50000);    let arr2 = [...arr1];    let arr3 = [...arr1];    let arr4 = [...arr1];    let arr5 = [...arr1];    let arr6 = [...arr1];

接下来是我们常见的排序方式

// 选择排序    function pickSort (arr) {        let temp;        for (let i = 0; i < arr.length; i++) {            for (let j = i + 1; j < arr.length; j++) {                if (arr[i] > arr[j]) {                    temp = arr[i];                    arr[i] = arr[j];                    arr[j] = temp;                }            }        }        return arr;    }    // 冒泡排序    function bubleSort (arr) {        let temp, isSort;        for (let i = 1; i < arr.length; i++) {            isSort = false;            for (let j = 0; j < arr.length - i; j++) {                if (arr[j] > arr[j + 1]) {                    temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                    isSort = true;                }            }            if (!isSort) {                break;            }        }        return arr;    }    // 快速排序 快速排序方法同时也是递归    function quickSort (arr) {        if (arr.length <= 1) {            return arr;        }        let x = arr.splice(0, 1)[0];        let left = [], right = [];        for (let i = 0; i < arr.length; i++) {            if (arr[i] < x) {                left.push(arr[i]);            } else {                right.push(arr[i]);            }        }        return quickSort(left).concat([x]).concat(quickSort(right));    }    // 插入排序    function spliceSort (arr) {        let temp;        for (let i = 1; i < arr.length; i++) {            for (let j = i; j > 0; j--) {                if (arr[j] < arr[j - 1]) {                    temp = arr[j];                    arr[j] = arr[j - 1];                    arr[j - 1] = temp;                } else {                    break                }            }        }        return arr;    }    // 希尔排序    function shellSort (arr) {        let temp;        let gap = 1;        while (gap < arr.length) {            gap = 3 * gap + 1;        }        for (; gap > 0; gap = Math.floor(gap / 3)) {            for (let i = gap; i < arr.length; i ++) {                for (let j = i; j > 0; j -= gap) {                    if (arr[j] < arr[j - gap]) {                        temp = arr[j];                        arr[j] = arr[j - gap];                        arr[j - gap] = temp;                    } else {                        break                    }                }            }        }        return arr;    }

计算各个方法所花费的时间

最后，需要一个函数调用以上各种排序的方法，并进行时间计算

// 计算排序时间的函数    function calcTime (arr, fun) {        console.time(fun.name);        let newArr = fun(arr);        console.timeEnd(fun.name);    }        // 开始计算    calcTime(arr1,bubleSort);    calcTime(arr2,quickSort);    calcTime(arr3,pickSort);    calcTime(arr4,spliceSort);    calcTime(arr5,shellSort);

Array.protype.sort是js自带排序函数，也可以测试一下速度

// 看下array.prototype中排序的效率如何    console.time('Array.prototype.sort');    arr6.sort(function (a,b) {        return a-b;    });    console.timeEnd('Array.prototype.sort');