给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
package com.loo;
import java.util.Arrays;
public class ColorGroup {
private static final int RED = 0; private static final int WHITE = 1; private static final int BLUE = 2; public static void main(String[] args) { int[] array = new int[] { BLUE , RED , WHITE , WHITE , BLUE , RED , RED , RED , BLUE , BLUE , WHITE }; System.out.println(Arrays.toString(array)); sortColors(array); // sortColors2(array); System.out.println(Arrays.toString(array)); }
public static void sortColors(int[] colors) { if (colors == null || colors.length == 0) { return; } int len = colors.length; int c0 = 0; int c1 = 0; int c2 = 0; for (int i=0;i<len;i++) { if (colors[i] == RED) { c0++; } else if (colors[i] == WHITE) { c1++; } else { c2++; } } for (int i=0;i<len;i++) { if (i<c0) { colors[i] = RED; } else if (i>=c0 && i<(c0+c1)) { colors[i] = WHITE; } else { colors[i] = BLUE; } } }
public static void sortColors2(int[] colors) { if (colors == null || colors.length == 0) { return; } int len = colors.length; quickSort2(colors , 0 , len-1); }
// 三向切分的快速排序 public static void quickSort2(int[] arr , int low , int hight) { if (low >= hight) { return; } int lt = low; int gt = hight; int i = low + 1; int temp = arr[low]; while (i<=gt) { if (temp > arr[i]) { swap(arr , lt++ , i++); } else if (temp < arr[i]) { swap(arr , i , gt--); } else { i++; } } quickSort2(arr , low , lt - 1); quickSort2(arr , gt + 1 , hight); }
public static void swap(int[] colors , int a , int b) { int temp = colors[a]; colors[a] = colors[b]; colors[b] = temp; } }
