计数排序解法

​

// 计数排序
func sortColors1(nums []int) {
    //make a map store each color number
    //iterate get numbers
    //iterate with 0 1 2 order , fill in arr
​
    map1 := make(map[int]int)
​
    for _, v := range nums {
        map1[v]++
    }
​
    pointer := 0
    for _, v := range []int{0, 1, 2} {
        for i := 1; i <= map1[v]; i++ {
            nums[pointer] = v
            pointer++
        }
    }
}

​

三路快排解法

​

画图/变量定义 , 区间定义/伪代码

使用keynote画效果还不错
​
正确的:

Leetcode Sort Colors

​
第一次画把0和1的位置搞反了 , 还好大部分定义不变
​

Leetcode Sort Colors
​
​

//three way partition
func sortColors(nums []int) {
    j := -1
    i := j + 1
    k := len(nums)-1+1
​
    for i <= k-1 {
        if nums[i] == 0 {
            tmp1 := nums[i]
            nums[i] = nums[j+1]
            nums[j+1] = tmp1
            i++
            j++
            continue
        }
        if nums[i] == 1 {
            i++
            continue
        }
        if nums[i] == 2 {
            k--
            tmp2 := nums[i]
            nums[i] = nums[k]
            nums[k] = tmp2
            continue
        }
    }
}