快速排序

快速排序（Quick Sort）是一种高效的排序算法，它采用分而治之的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。快速排序的平均时间复杂度为 O(n log n)，但最坏情况下的时间复杂度为 O(n^2)，这通常发生在输入数组已经接近排序好的情况下。

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        // 通过设置枢轴值的位置对数组进行分区
        const partitionIndex = partition(arr, left, right);

        // 排序左侧
        quickSort(arr, left, partitionIndex - 1);

        // 排序右侧
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
}

function partition(arr, left, right) {
    // 选择最右边的元素作为基准值
    const pivot = arr[right];
    let i = left - 1; // 较小元素的索引

    for (let j = left; j < right; j++) {
        // 如果当前元素小于或等于基准值
        if (arr[j] <= pivot) {
            i++; // 增加较小元素的索引

            // 交换 arr[i] 和 arr[j]
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }

    // 将基准值交换到中间
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];

    return i + 1;
}

快速排序 ​

算法描述 ​

代码实现 ​

快速排序

算法描述

代码实现