js常见排序算法实现：冒泡排序，快速排序

摘要：冒泡排序原理：对数组进行遍历，根据相邻两个元素大小进行交换，每一次遍历都将最小值推至最前方，然后对剩下的值再次进行比较；快速排序原理：从数组中取一个基准值，将剩下的值与基准值比较

1.冒泡排序

原理：对数组进行遍历，根据相邻两个元素大小进行交换，每一次遍历都将最小值推至最前方，然后对剩下的值再次进行比较

空间复杂度：O(1)

时间复杂度：O(n^2)

稳定性：稳定

// 冒泡排序
function bubbleSort(arr) {
    let len = arr.length - 1, tmp
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i; j++) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = tmp
            }
        }
    }
    return arr
}

2.快速排序

原理：从数组中取一个基准值，将剩下的值与基准值比较，小于的放到左边，大于的放到右边，并对左右两边进行快速排序，重复直到左右两边只剩一个元素，最后合并

平均时间复杂度O(nlogn)

最坏时间复杂度：O(n^2)

稳定性：不稳定

// 快速排序
function quickSort(arr) {
    let len = arr.length
    if (len < 2) {
        return arr;
    }
    let index = Math.floor(len / 2);
    let pindex = arr.splice(index, 1)[0]; // 去除基准值
    let left = [], right = [];
    arr.forEach(item => {
        if (item > pindex) {
            right.push(item);
        } else {
            left.push(item);
        }
    })
    return quickSort(left).concat([pindex], quickSort(right))
}

本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！

链接: https://shenqiku.cn/article/FLY_10026