、夕月的博客

快速排序

2021/2/19

# Heading

    快速排序的基本思想是基于分治法的：在待排序表L[1...n]中任取一个元素 pivot 作为基准（通常取第一个），通过一趟排序将待排序表划分为独立的两部分L[1..k-1]和L[k+1..n],使得L[1..k-1]中的所有元素都小于 pivot，L[k+1..n]的所有元素都大于等于 pivot，则**pivot 放在了最终位置 L(K)**上，这个过程称为一趟快速排序。然后分别递归地对两个子序列重复这个过程，直到每个部分只有一个元素或空为止，即所有元素都放在了最终位置。

    快速排序算法的关键在于划分操作，性能也取决于划分操作的优劣：（最坏情况在实际排序中几乎不会发生）

    1. 第一个元素作为基准
    2. 三向切分：选取头中尾三个元素取中间值作为基准
    3. 随机地从当前表中选取基准元素
    4. TODO
    点击查看代码 
    /**
 * 快速排序
 * @param {*} arr 
 * @param {*} n 
 */
export function QuickSort(arr = [], n = 0) {
    const partition = (arr, low, high) => {//一趟划分
        let pivot = arr[low]//基准取第一个元素
        while (low < high) {
            while (low < high && arr[high] >= pivot) high--;
            arr[low] = arr[high]//比pivot小的元素交换到左边
            while (low < high && arr[low] <= pivot) low++;
            arr[high] = arr[low]//比pivot大的元素交换到右边
        }
        arr[low] = pivot
        return low
    }
    const QSort = (arr, low, high) => {
        if (low < high) {
            let pivotIdx = partition(arr, low, high)
            QSort(arr, 0, pivotIdx - 1);
            QSort(arr, pivotIdx + 1, high);
        }
    }
    QSort(arr, 0, n - 1)
    return arr
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26

    性能分析如下：

    • 空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存递归信息，其容量应与递归调用的最大深度一致。最好情况下为O（log2n）；最快情况下，因为要进行 n-1 次递归，所以栈的深度为O（n）；平均情况下，栈的深度为O（log2n）。
    • 时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含 n-1 个元素和 0 个元素时，这种最大程度的不对称性若发生在每层递归上，即对于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度O（n^2）。理想情况下，Partition 每次都做到最平衡的划分，得到的两个子问题大小都不大于 n/2，这种情况下，快排的速度将大大提升，此时时间复杂度为O(nlog2n)。一般来说平均情况下的运行时间和最佳情况很接近。快速排序是所有内部排序算法中平均性能最优的排序算法。
    • 稳定性：在划分算法中，若右端区间有两个关键字相同且小于基准值，则交换到左边后，它们的相对位置会发生变化。即快速排序是一种不稳定的排序算法。

    选择排序