75.颜色分类

题目描述

题解

快排

这道题就是荷兰国旗 问题, 也是快排基本思想的体现.

利用快排的思路将数组排序即可

public void sortColors(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
}

private void quickSort(int[] nums, int left, int right) {
    if (left > right) {
        return;
    }

    int pIndex = partition(nums, left, right);
    quickSort(nums, left, pIndex - 1);
    quickSort(nums, pIndex + 1, right);
}

private int partition(int[] nums, int left, int right) {
    int pivot = nums[left];
    int lt = left;

    for (int i = left + 1; i <= right; i++) {
        if (nums[i]<pivot){
            lt++;
            swap(nums,lt, i);
        }
    }
    swap(nums, lt, left);
    return lt;
}

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