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

2 years ago

source link: https://labuladong.github.io/algo/2/19/42/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

快速排序详解及应用

通知：持续更新中，开始报名，开始预约。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

牛客	LeetCode	难度
-		🟠
-		🟠
-	-	🟠

———–

前文

通过二叉树的视角描述了归并排序的算法原理以及应用，很多读者大呼精妙，那我就趁热打铁，今天继续用二叉树的视角讲一讲快速排序算法的原理以及运用。

快速排序算法思路

首先我们看一下快速排序的代码框架：

void sort(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    // 对 nums[lo..hi] 进行切分
    // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    int p = partition(nums, lo, hi);
    // 去左右子数组进行切分
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

其实你对比之后可以发现，快速排序就是一个二叉树的前序遍历：

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    /****** 前序位置 ******/
    print(root.val);
    /*********************/
    traverse(root.left);
    traverse(root.right);
}

另外，前文

用一句话总结了归并排序：先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并。

同时我提了一个问题，让你一句话总结快速排序，这里说一下我的答案：

快速排序是先将一个元素排好序，然后再将剩下的元素排好序。

＿＿＿＿＿＿＿＿＿＿＿＿＿

应合作方要求，本文不便在此发布，请扫码关注回复关键词「快排」或

查看：