计数排序解法

// 计数排序
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画效果还不错

正确的:

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

//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
        }
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接