从三色旗到快排

三色旗问题

使用一次遍历将一堆0，1，2的数字按序放在不同区域，形成0..01..12..2的数组，这个问题解决方法可以两个指针分别指向下一个 0 要占据的坐标、下一个 1 要占据的坐标：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func partition(nums []int){
    p0, p1 := 0,0
    for i := 0; i < len(nums);i++{
        if nums[i] == 0 {
            // 当前数为0则占据p0现在的位置，并将数据交换
            nums[p0], nums[i] = nums[i], nums[p0]
            // 如果p1>p0代表最少有一个1也就是当前序列是0...0 1...1 xxxxxx
            // 此时p0指向的是第一个1的位置，发生替换相当于将第一个1换到了0，
            // 然后第一个1去了i的位置,这个时候需要换回来
            if p1  > p0{
                nums[p1], nums[i] = nums[i], nums[p1]
            }
            p1++
            p0++
        }
        if nums[i] == 1{
            nums[p1], nums[i] =  nums[i], nums[p1]
            p1++
        }
    }
}

这个过程和快速排序的找到中间数据所在位置的过程类似，我们可以以此实现快速排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func QuickSort(nums []int){
    partition(nums, 0, len(nums) - 1)
}
func partition(nums []int, left, right int){
    pivot := nums[left]
    p0, p1 := left, left
    for i := 0; i < len(nums);i++{
        if nums[i] == pivot {
            nums[p0], nums[i] = nums[i], nums[p0]
            if p1  > p0{
                nums[p1], nums[i] = nums[i], nums[p1]
            }
            p1++
            p0++
        }
        if nums[i] == pivot{
            nums[p1], nums[i] =  nums[i], nums[p1]
            p1++
        }
    }
    partition(nums, left, p0-1)
    partition(nums, p1, right)
}