js 快速排序算法|极客笔记

js 快速排序算法

快速排序是一种常用的排序算法，采用分治的策略，通过将数组分割成较小的子数组来实现排序。它具有高效的性能和简洁的实现方式，是解决排序问题的首选算法之一。

算法原理

快速排序的基本思想是选择一个基准值，将数组分成两部分，一部分的元素都小于基准值，一部分的元素都大于基准值，然后对这两部分分别进行排序。具体步骤如下：

选择一个基准值（pivot），通常选择数组中的第一个元素。
将数组中小于基准值的元素放在基准值的左边，大于基准值的元素放在右边。
对左右两个子数组分别递归进行快速排序。
合并左右两个子数组。

算法实现

JavaScript实现

下面是使用JavaScript实现快速排序算法的示例代码：

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[0];
    const left = [];
    const right = [];

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return quickSort(left).concat(pivot, quickSort(right));
}

// 测试
const arr = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(arr)); // [1, 1, 2, 3, 6, 8, 10]

在上面的代码中，定义了一个quickSort函数来实现快速排序。首先判断数组长度是否小于等于1，若是则直接返回该数组。然后选择数组的第一个元素作为基准值，遍历数组将小于基准值的元素放在左边，大于基准值的元素放在右边。最后递归对左右两个子数组进行快速排序，最终合并左右两个子数组得到排序后的结果。