75.颜色分类

算法解析：荷兰国旗问题与三色排序

问题描述

给定一个包含红色、白色和蓝色元素的数组，我们需要将它们按照红、白、蓝的顺序进行排序。在本题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

解决方案分析

方法思路

本文介绍的是一种简单直观的双遍扫描排序方法：

1. 第一遍扫描：将所有的0（红色）移动到数组的最前面

2. 第二遍扫描：将所有的1（白色）移动到已经排好序的0之后的区域

这样，剩余的2（蓝色）自然就排在了数组的最后面。

        代码：

class Solution {
public:void sortColors(vector<int>& nums) {int ptr = 0;int n = nums.size();for (int i = 0;i < n;i++) {if (nums[i] == 0) {swap(nums[ptr],nums[i]);++ptr;}}for (int i = 0;i < n;i++) {if (nums[i] == 1) {swap(nums[ptr],nums[i]);++ptr;}}}
};

       时间复杂度：O(n),两次线性扫描

       空间复杂度：O(1),使用了两个额外变量

        快排：

class Solution {
public:void quick(vector<int>& nums,int start,int end) {if (start >= end) return;int i = start - 1;int j = end + 1;int temp = nums[start];int index = start;while (index < j) {if (temp < nums[index]) {swap(nums[index++],nums[++i]);}else if (temp > nums[index]){swap(nums[index],nums[--j]);}else {index++;}}quick(nums,start,i);quick(nums,j,end);}void sortColors(vector<int>& nums) {quick(nums,0,nums.size() - 1);ranges::reverse(nums);}
};