颜色分类

1. 题目描述

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

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

2. 思路

1. 思路一
   • 快速排序
2. 思路二
   • 桶排序
3. 思路三
   • 移动零.md

3. 实现

3.1. 快速排序

func sortColors(nums []int)  {
    quickSort(nums, 0, len(nums)-1)
}

func quickSort(nums []int, left, right int) {
    if left >= right {
        return
    }

    p := partition(nums, left, right)
    quickSort(nums, left, p-1)
    quickSort(nums, p+1, right)
}

func partition(nums []int, left, right int) int {
    pivot := nums[left]
    for left < right {
        for left < right && nums[right] >= pivot {
            right--
        }
        nums[left] = nums[right]
        for left < right && nums[left] <= pivot {
            left++
        }
        nums[right] = nums[left]
    }
    nums[left] = pivot
    return left
}

3.2. 桶排序

func sortColors(nums []int)  {
    bucket := []int{0,0,0}
    for _, num := range nums {
        bucket[num]++
    }
    i:=0
    for num, count := range bucket {
        for j := 0; j < count; j++{
            nums[i] = num
            i++
        }
    }
}

3.3. 移动零

func sortColors(nums []int)  {
    index := 0
    for i:=0; i<len(nums); i++{
        if nums[i] == 0 {
            nums[i],nums[index] = nums[index],nums[i]
            index++
        }
    }
    for i:=index; i<len(nums); i++{
        if nums[i] == 1 {
            nums[i],nums[index] = nums[index],nums[i]
            index++
        }
    }

}

4. 参考

• 颜色分类 - 颜色分类 - 力扣（LeetCode）