快速排序

介绍

快速排序（Quicksort）是一种高效的排序算法，其基本思想是通过选择一个枢纽元素（pivot），将数组分割成两个子数组，其中一个子数组的所有元素都小于枢纽元素，另一个子数组的所有元素都大于枢纽元素。然后，递归地对这两个子数组进行排序，直到整个数组有序。

动图演示

基本步骤

选择枢纽元素：从数组中选择一个元素作为枢纽元素（pivot）。通常选择数组的第一个元素、最后一个元素或者随机位置的元素作为枢纽元素。
分区操作：重新排列数组，将比枢纽元素小的元素放到枢纽元素的左侧，比枢纽元素大的元素放到右侧，枢纽元素位于两个子数组的中间位置。在分区操作之后，枢纽元素所在的位置通常称为分区点（partition point）。
递归排序：递归地对枢纽元素左侧的子数组和右侧的子数组进行快速排序。
合并结果：由于快速排序是一种原址排序算法，不需要显式合并步骤。当递归排序完成后，整个数组也就有序了。

复杂度

快速排序的时间复杂度取决于每次分区操作的平均情况。在平均情况下，快速排序的时间复杂度为O(n log n)。

计算方法如下：

递归树：快速排序算法的递归过程可以看作是一棵二叉树，每次递归调用都会将数组分成两个子数组，直到子数组的大小为1或0。这棵递归树的高度就是递归调用的次数。由于每次划分操作都会将数组大小减半，所以递归树的高度为O(log n)。
分区操作的时间复杂度：在每一层递归中，都需要对整个数组进行一次分区操作。分区操作的时间复杂度取决于数组的大小n。在每次分区操作中，需要线性地遍历数组元素，并根据枢纽元素进行划分。因此，每次分区操作的时间复杂度为O(n)。

然而，在最坏情况下（即每次选择的枢纽元素都是数组中的最小或最大元素），时间复杂度会退化为O(n^2)。为了避免最坏情况的发生，通常采用随机化的方法来选择枢纽元素。

实现

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr; // 基线条件：如果数组长度为1或更小，则已经有序，无需排序
    }

    const pivot = arr[arr.length - 1]; // 选择最后一个元素作为枢纽元素
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]); // 比枢纽元素小的元素放到左侧数组
        } else {
            right.push(arr[i]); // 比枢纽元素大的元素放到右侧数组
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)]; // 递归地对左右数组进行快速排序，并将结果合并
}

const arr = [12, 7, 14, 9, 10, 11];
console.log('Original array:', arr);
const sortedArr = quickSort(arr);
console.log('Sorted array:', sortedArr);

快速排序 ​

介绍 ​

动图演示 ​

基本步骤 ​

复杂度 ​

实现 ​

快速排序

介绍

动图演示

基本步骤

复杂度

实现