那些可以用快速排序秒杀的经典题（一）

vlambda
2021-05-10

那些可以用快速排序秒杀的经典题（一）

👇👇 关注后回复 “进群” ，拉你进程序员交流群 👇👇

架构师大咖

架构师大咖，打造有价值的架构师交流平台。分享架构师干货、教程、课程、资讯。架构师大咖，每日推送。

0篇原创内容

Official Account

算法专栏

算法专栏，每日推送。算法是程序员内功，分享算法知识、文章、工具、算法题、教程等

0篇原创内容

Official Account

作者丨袁厨

来源丨袁厨的算法小屋

我们今天先来说一下那个非常经典的荷兰国旗问题。

问题来源：

https://www.jianshu.com/p/356604b8903f

问题描述：

荷兰国旗是由红白蓝3种颜色的条纹拼接而成，如下图所示：

假设这样的条纹有多条，且各种颜色的数量不一，并且随机组成了一个新的图形，新的图形可能如下图所示，但是绝非只有这一种情况：

需求是：把这些条纹按照颜色排好，红色的在上半部分，白色的在中间部分，蓝色的在下半部分，我们把这类问题称作荷兰国旗问题。

我们把荷兰国旗问题用数组的形式表达一下是这样的：

给定一个整数数组，给定一个值 K，这个值在原数组中一定存在，要求把数组中小于 K 的元素放到数组的左边，大于K的元素放到数组的右边，等于K的元素放到数组的中间。

这不就是我们之前说过的三向切分吗？一模一样！

那么 leetcode 有没有相似问题呢？当然有的，我们一起来看下面这道题

leetcode 75 颜色分类

题目描述：

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

解题思路

这个题目我们使用 Arrays.sort() 解决，哈哈，但是那样太无聊啦，题目含义就是让我们将所有的 0 放在前面，2放在后面，1 放在中间，是不是和我们上面说的荷兰国旗问题一样。此时我们仅仅将 1 做为基准值。

下面我们直接看代码吧，和快速排序优化三向切分代码基本一致。

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int left = 0;
        //这里和三向切分不完全一致
        int i = left;
        int right = len-1;

        while (i <= right) {
             if (nums[i] == 2) {
                 swap(nums,i,right--);
             } else if (nums[i] == 0) {
                 swap(nums,i++,left++);
             } else {
                 i++;
             }
        }     
    }
    public void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

另外我们看这段代码，有什么问题呢？那就是我们即使完全符合时，仍会交换元素，这样会大大降低我们的效率。

例如：[0,0,0,1,1,1,2,2,2]

此时我们完全符合情况，不需要交换元素，但是按照我们上面的代码，0,2 的每个元素会和自己进行交换，所以这里我们可以根据 i 和 left 的值是否相等来决定是否需要交换，大家可以自己写一下。

下面我们看一下另外一种写法

这个题目的关键点就是，当我们 nums[i] 和 nums[right] 交换后，我们的 nums[right] 此时指向的元素是符合要求的，但是我们 nums[i] 指向的元素不一定符合要求，所以我们需要继续判断, nums[i] 是否还需要和 nums[left] 进行交换。

我们 2 和 0 交换后，此时 i 指向 0 ，0 应放在头部，所以不符合情况，所以 0 和 1 仍需要交换。下面我们来看一下动画来加深理解吧。

那些可以用快速排序秒杀的经典题（一）

代码

class Solution {
    public void sortColors(int[] nums) {

        int left = 0;
        int len = nums.length;
        int right = len - 1;
        for (int i = 0; i <= right; ++i) {
            if (nums[i] == 0) {             
                swap(nums,i,left);
                left++;
            }
            if (nums[i] == 2) {
                swap(nums,i,right);
                right--;
                //如果不等于 1 则需要继续判断，所以不移动 i 指针，i--
                if (nums[i] != 1) {
                    i--;
                }
            }
        }

    }
    public void swap (int[] nums,int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

好啦，这个问题到这就结束啦，是不是很简单啊。

-End-

最近有一些小伙伴，让我帮忙找一些面试题资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！

那些可以用快速排序秒杀的经典题（一）

程序员直聘

程序员直聘，一个程序员找工作平台。

21篇原创内容

Official Account

点击👆卡片，关注后回复【面试题】即可获取

在看点这里好文分享给更多人↓↓

vlambda博客
学习文章列表