75. 颜色分类

描述

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

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

链接

75. 颜色分类 - 力扣（LeetCode） (leetcode-cn.com)

解法：快速排序的思想

 1 class Solution {
 2     public void sortColors(int[] nums) {
 3         int left =  0;
 4         int right = nums.length - 1;
 5         int index = 0;
 6         // 核心思想在于 选基准值，pivot
 7         while (index <= right) {
 8             int cur = nums[index];
 9             if(cur == 0) {
10                 swap (nums, left , index);
11                 index++;
12                 left++;
13             }
14             else if (cur == 1) {
15                 index++;
16             }
17             else if (cur == 2) {
18                 swap(nums, index, right);
19                 right--;
20             }
21         }
22     }
23 
24     public void swap (int[] nums, int i, int j) {
25         int temp = nums[i];
26         nums[i] = nums[j];
27         nums[j] = temp;
28     }
29 }

题解链接

吴师兄