快速排序:单/双边循环法、栈实现

June 8, 2022

快速排序是不稳定的排序

双边循环法

function qsortWrapper1<T = number>(arr: T[], start?: number, end?: number): T[] {
    function qsort<T>(arr: T[], start: number, end: number) {
        if (start >= end) return;
        const pivotIndex = partition(arr, start, end);
        qsort(arr, start, pivotIndex - 1);
        qsort(arr, pivotIndex + 1, end);
    }

    // 双边循环法
    function partition<T>(arr: T[], start: number, end: number): number {
        const pivot = arr[start];
        // 基准元素可以设置为任意元素，直接设为首元素即可
        let left = start;
        let right = end;
        // left 和 right 指针首先指向数组两端

        // 我们的最终目的是左边的元素比基准元素都小，右边的元素比基准元素都大
        // 所以双边循环法对两端进行遍历，一旦找到右指针指向的元素比基准元素小，并且有左指针指向的元素比基准元素大
        // 就将这两个指针指向的元素交换，终止条件很明显就是指针相等
        while (left !== right) {
            // 强调一下 left < right 条件，保证左右指针的顺序
            while (left < right && arr[right] > pivot) right--;
            while (left < right && arr[left] <= pivot) left++;
            // 这里的判断是保证指针相等时，不交换元素，不做无意义的交换
            if (left < right) [arr[left], arr[right]] = [arr[right], arr[left]];
        }
        // 最终，左右指针相等，指向一个比基准元素小的元素
        arr[start] = arr[left];
        arr[left] = pivot;
        // 将指针指向的元素与基准元素交换 (这里用 left 指针和 right 指针皆可)
        return left;
    }

    if (typeof start !== "number") start = 0;
    if (typeof end !== "number") end = arr.length - 1;
    qsort(arr, start, end);
    return arr;
}

console.log(qsortWrapper1([1, 5, 8, 2, 4, 6, 3, 7, 0, 9]));

单边循环法

function qsortWrapper2<T = number>(arr: T[], start?: number, end?: number): T[] {
    function qsort<T>(arr: T[], start: number, end: number) {
        if (start >= end) return;
        const pivotIndex = partition(arr, start, end);
        qsort(arr, start, pivotIndex - 1);
        qsort(arr, pivotIndex + 1, end);
    }

    // 单边循环法
    function partition<T>(arr: T[], start: number, end: number): number {
        const pivot = arr[start];
        // 基准元素可以设置为任意元素，直接设为首元素即可

        let mark = start; // mark 指针首先指向数组起始位置，我们的目标是 mark 指针指向小于基准元素的区域边界 (其指向的元素也小于基准元素)

        for (let i = start + 1; i < end; i++)
            if (arr[i] < pivot) {
                // 遍历的元素小于基准元素，则边界扩大了
                // 令 mark 自增。当前 mark 指向的元素必然大于或等于遍历的元素，交换后保证小于基准元素的当前遍历元素在边界内部 (闭区间)
                mark++;
                [arr[mark], arr[i]] = [arr[i], arr[mark]];
                // 快速排序是不稳定的排序，无需保证稳定性
            }

        arr[start] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

    if (typeof start !== "number") start = 0;
    if (typeof end !== "number") end = arr.length - 1;
    qsort(arr, start, end);
    return arr;
}

console.log(qsortWrapper2([1, 5, 8, 2, 4, 6, 3, 7, 0, 9]));

栈实现

partition 函数任选单/双边循环法

interface Param {
    start: number;
    end: number;
}

function qsort<T>(arr: T[], start: number, end: number) {
    const stack: Array<Param> = [{ start, end }]; // 栈初始化

    while (stack.length > 0) {
        const param: Param = stack.pop()!; // stack 非空，断言必然成立
        const pivotIndex = partition(arr, param.start, param.end);
        if (param.start < pivotIndex - 1) stack.push({ start, end: pivotIndex - 1 });
        if (pivotIndex + 1 < param.end) stack.push({ start: pivotIndex + 1, end });
    }
}

←Back to home

This work is licensed under CC BY-NC-SA 4.0