题解 | #颜色分类#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param colors int整型一维数组 
     * @return int整型一维数组
     */
    public int[] sortColor(int[] colors) {
        // write code here
        if (1 == colors.length) {
            return colors;
        }
        quickSort(colors, 0, colors.length - 1);
        return colors;
    }

    // 快排
    public void quickSort(int[] colors, int start, int end) {
        if (start >= end) {
            return;
        }
        int l = start - 1;
        int r = end + 1;
        int p = start;
        int val = colors[end];
        while (p < r) {
            if (colors[p] < val) {
                int swap = colors[p];
                colors[p] = colors[l + 1];
                colors[l + 1] = swap;
                l++;
                p++;
            } else if (colors[p] > val) {
                int swap = colors[p];
                colors[p] = colors[r - 1];
                colors[r - 1] = swap;
                r--;
            } else {
                p++;
            }
        }
        quickSort(colors, start, l);
        quickSort(colors, r, end);
    }
}