首页 专题 文章 代码 归档

【三大排序】JavaScript的三大排序实现

1. 前言

经典的排序算法,怎么也要掌握

三大排序:冒泡 、插入 、 快速

1.1. 冒泡

// 冒泡
function bubble(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            let tmp = arr[i]
            // > 从小到大
            // < 就从大到小
            if (arr[i] > arr[j]) {
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    return arr;
}

最最经典的一种排序算法,借助两重for循环和一个第三方变量保存值,就可以排序了

1.2. 插入

有大佬说,理解为打扑克

//插入
function insert(arr) {
    if (arr.length === 0) {
        return;
    }

    let new_arr = [arr[0]]
    for (let i = 1; i < arr.length; i++) {
        //下面这个for是代表从小到大排序
        //     for (let j = 0; j < new_arr.length; j++) {
        //         if (arr[i] > new_arr[j]) {
        //             new_arr.push(arr[i]);
        //             break;
        //         }
        //         if (j === new_arr.length - 1) {
        //             new_arr.unshift(arr[i])
        //         }
        //     }
        // }
        //如果是从大到小,那么就for里面的条件反过来
        for (let j = new_arr.length - 1; j >= 0; j--) {
            if (arr[i] < new_arr[j]) {
                new_arr.push(arr[i]);
                break;
            }
            if (j === new_arr.length - 1) {
                new_arr.unshift(arr[i])
            }
        }
    }
    return new_arr;
}

还是有两个for循环,然后就是第二重for循环中,判断大小,压入新数组中

1.3. 快速

这是一个借助递归的方法

// 快速排序(递归)
function quick(arr) {
    //出口
    if (arr.length <= 1) {
        return arr;
    }
    let m = Math.ceil(arr.length / 2);
    let middleValue = arr.splice(m, 1)[0];
    let leftArr = [], rightArr = [];
    for (let i = 0; i < arr.length; i++) {
        //> 从大到小
        //< 从小到大
        if (arr[i] > middleValue)
            leftArr.push(arr[i])
        else
            rightArr.push(arr[i])
    }
    return quick(leftArr).concat([middleValue], quick(rightArr));
}

原理就是找中间值,比中间值小的压入左边(或右边),大的压入右边(或左边)

然后,递归次过程,直到数组中只有一个元素为止

此文阅读完毕,您可以:分享
二维码图片 扫描关注我们哟