快速排序详解及应用 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：快速排序详解及应用

评论礼仪 见这里，违者直接拉黑。

[wy-luke]

while (i < hi && nums[i] <= pivot) {
    i++;
    // 此 while 结束时恰好 nums[i] > pivot
}

不知道我的理解是否正确

对于数组 [5,1,2,3,4] 排序时，经过这个循环，i 指向 4 ，并不满足 nums[i] > pivot，但是会由 if (i >= j) break; 终止 swap，结果是一样的

对于数组 [5,1,2,3,4,8] 排序时，就没问题了

试了一下，这里使用 i <= hi 也能AC，感觉这里之所以用 i < hi 是因为能够减少一次循环，因为hi元素的大小会在下面的j循环得到对比

对于数组 [5,1,2,3,4] 排序时，使用 i <= hi ，经过上面的循环i会指向4后面，但是依然会由 if (i >= j) break; 终止 swap，结果是一样的

而 j > lo 是因为 lo 元素就是 pivot，无须比较

[labuladong]

@wy-luke 给你的思考点赞！关于你说的 使用 i <= hi 也能AC，确实是这样的，我简单说下我的分析：

这里的关键是控制 j 指针的位置，因为外层 while 结束之后需要把 pivot 换到 nums[j] 的位置上去。你对 i 的边界情况有微调，只要不影响 j 的位置，同时能够保证触发 if (i >= j) break; 的终止条件，则最终的结果都是正确的。

[wy-luke]

@labuladong 谢谢东哥！

[cheng-miao]

nice

[David-qiuwenhui]

912. 排序数组 javascript version

var sortArray = function(nums) {
    // 为了避免出现耗时的极端情况 先随机打乱数组
    randomShuffle(nums);
    // 排序整个数组（原地修改）
    sort(nums, 0, nums.length - 1);
    return nums;

    // 排序数组nums
    function sort(nums, lo, hi) {
        if (lo >= hi) {
            return;
        }

        /****** 前序位置 ******/
        // 对nums[lo...hi]进行切分
        // 使得nums[lo...p-1] <= nums[p] < nums[p+1..hi]
        let p = partition(nums, lo, hi);
        /*********************/

        sort(nums, lo, p - 1);
        sort(nums, p + 1, hi);
    }

    // 对nums[lo...hi]进行切分
    function partition(nums, lo, hi) {
        // 取第一个位置的元素作为基准元素
        let pivot = nums[lo];
        // 这里把left, right定义为开区间
        // 同时定义 [lo, left) <= pivot; (right, hi] > pivot
        // 之后都要正确维护这个边界区间的定义
        let left = lo + 1;
        let right = hi;
        
        // 当left > right时结束循环 以保证区间[lo, hi]都被覆盖
        while(left <= right) {
            while(left < hi && nums[left] <= pivot) {
                left++;
                // 此while循环结束时 恰好 nums[left] > pivot
            }
            while(right > lo && nums[right] > pivot) {
                right--;
                // 此while循环结束时 恰好 nums[right] <= pivot
            }
            // 此时[lo, left) <= pivot && (right, hi] > pivot

            if (left >= right) {
                break;
            }
            swap(nums, left, right)
        }
        // 将pivot放到合适的位置 即pivot左边元素较小 右边元素较大
        swap(nums, lo, right);
        return right;
    }

    // 随机打乱数组
    function randomShuffle(nums) {
        let len = nums.length;
        for (let i; i < len; i++) {
            // 随机生成[i, n - i]的随机数
            let index = i + Math.floor(Math.random * (len - i));
            swap(nums, i, index);
        }
    }

    // 原地交换数组中的两个元素
    function swap(nums, i, j) {
        let temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

215. 数组中的第K个最大元素 javascript version

var findKthLargest = function(nums, k) {
    // 转化成升序排名第targetIndex的元素
    let targetIndex = nums.length - k;
    let start = 0;
    let end = nums.length - 1;
    /** 在nums[start, end]中选择一个分界点 */
    let index = partition(nums, start, end);

    while (index != targetIndex) {
        if (index > targetIndex) {
            // 第k大的元素在nums[start, index - 1]中
            end = index - 1;
        } else {
            // 第k大的元素在nums[index + 1, end]中
            start = index + 1;
        }
        // 在nums[start, end]中选一个分界点
        index = partition(nums, start, end);
    }
    // 找到第k大的元素
    return nums[index];
}

/****** 对nums[start, end]进行切分 ******/
function partition(arr, startIndex, endIndex) {
    // 取第一个位置的元素作为基准元素
    let pivot = arr[startIndex];
    // 设置一个mark指针指向数组的起始位置 最终mark指针代表小于基准元素的区域边界
    let mark = startIndex;
    for (let i = startIndex+1; i <= endIndex; i++) {
        if (arr[i] < pivot) {
            mark++;
            // 交换两个元素
            [arr[mark], arr[i]] = [arr[i], arr[mark]];
        }
    }
    // 更新分界点的值
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}

[wercyle]

东哥，算时间复杂度那，是等比数列，不是等差数列

[labuladong]

@wercyle 感谢指出，是我写错了，已修复~

[615lyw]

这个分区容易理解点，有点双指针技巧含义，选最后一个元素作为分区点，指针 i 表示比分区值小的元素应该放的位置，指针 j 只用来遍历。当 j 遍历到比分区值小的元素时，放到指针 i 的位置（通过交换实现）。当 j 遍历完时，[lo, i - 1] 都是比分区值小的元素，[i, hi - 1] 都是比分区值大的元素，最后交换一下分区值和 i 所指向的元素便实现了 pivot 左边都是比它小的元素，右边都是比它大的元素。

private static int partition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo, j = lo;
    while (j < hi) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
        j++;
    }
    swap(arr, i, hi);
    return i;
}

[wanaxe]

对我这个更易于理解。而且换用这个实现，912 和 215 两题都不会超时。

[victoriatan89]

感觉东哥的分区用的是左右指针，这个用的是快慢指针，确实简化了边界的处理，厉害厉害！

[Goolloo]

笔记：
partition 里面有while(i <= j) {，等号的目的是解决array的长度只有2的edge case，其中一个被抓去做了pivot，另一个必须得验证一下是不是比pivot大，不是的话还是要swap一下。
如果长度只有1，那么进不了这个while循环

quick select里面还有一个while(i <= j) {， 等号的目的是解决array长度只有1的edge case。理论上应该返回0，如果不加等号会返回-1。

[suifengqh]

东哥，现在912题快速排序算法会超时，应该是加入了输入是基本有序的数组case导致的

[labuladong]

我这没看到超时，但确实速度比较慢。原因应该不是基本有序的 case，因为我在解法中先 shuffle 打乱顺序了。我猜测是 case 里有大量重复的元素，导致快排效率下降。可以尝试使用 归并排序。

[zhaoedf]

是的，现在有一个case是 [2,2,...,2]，很多个，这时候哪怕加入shuffle也会超时。

[DJofOUC]

学习到了，nice

[DJofOUC]

求第K大的数时，重复元素多，使用快排也会超时，何解？

[hughxx]

超时会不会因为partition中判断太多，与lo和high以及i=j的case其实很少，btw，这块也没那么好理解，

[Youareblind]

ruby版

def sort_array nums
	shuffle nums
	quick_sort nums, 0, nums.length - 1
end

def quick_sort nums, lo, hi
	return if lo >= hi
	p = partition nums, lo, hi

	quick_sort nums, lo, p - 1
	quick_sort nums, p + 1, hi
end

def partition nums, lo, hi
	pivot = nums[lo]

	i, j = lo + 1, hi

	while i <= j do
		while i < hi && nums[i] <= pivot do
			i += 1
		end
		while j > lo && nums[j] > pivot do
			j -= 1
		end
		break if i >= j
		nums[i], nums[j] = nums[j], nums[i]
	end

	nums[lo], nums[j] = nums[j], nums[lo]
	j
end

def shuffle nums
	ran_num = Random.new
	n = nums.length
	n.times do |i|
		r = ran_num.rand i...n
		nums[i], nums[r] = nums[r], nums[i]
	end
end

[jacobwwang]

如果纸质书上有归并和快排就好了

[bruceeewong]

20230203打卡！本篇的快排是两路快排（两个指针，切分成 <=和>两部分），其实存在局限：如果重复值过多，容易右侧递归深度大于左边导致时间复杂度退化。leetcode912, run time: 2262 ms
写了个Java三路快排，leetcode912, run time: 28 ms，思路是用三个指针lt, i, gt，分别把数组拆成 [lo, lt] < pivot, (lt, i) == pivot, [gt, hi] > pivot

void quicksort(int[] nums, int lo, int hi) {
    if (lo >= hi) return;

    int pivot = nums[lo];
    int lt = lo; // [lo+1, lt]  < pivot
    int i = lo + 1;  // (lt, i)  == pivot
    int gt = hi + 1;  // [gt, hi]  > pivot

    while (i < gt) {
        if (nums[i] < pivot) {
            lt ++;
            swap(nums, i, lt);
            i ++;
        } else if (nums[i] > pivot) {
            gt --;
            swap(nums, i, gt);
        } else {
            i ++;
        }
    }
    swap(nums, lo, lt);
    
    quicksort(nums, lo, lt - 1);
    quicksort(nums, gt, hi); 
}

[yangshining]

哥们，CHATGPT生成的吧

[wowwm]

python一直有个“222222……”的用例超时，改成三路快排。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        lo, hi = 0, len(nums)-1
        random.shuffle(nums)

        def qsort(nums, lo, hi):
            if lo >= hi:
                return nums
            p, q = partition(nums, lo, hi)
            qsort(nums, lo, p-1)
            qsort(nums, q+1, hi)

        # 划分
        def partition(nums, lo, hi):
            tar = nums[hi]
            i, j, k = lo, lo, hi-1
            # 三路快排
            # [lo, i-1] < tar
            # [k+1, hi-1] > tar
            # [i, k] = tar
            while j <= k:
                if nums[j] < tar:
                    nums[j], nums[i] = nums[i], nums[j]
                    i += 1
                    j += 1
                elif nums[j] > tar:
                    nums[j], nums[k] = nums[k], nums[j]
                    k -= 1
                else:
                    j += 1
            nums[hi], nums[i] = nums[i], nums[hi]
            return i, k
                

        qsort(nums, lo, hi)
        return nums