从三色旗到快排
三色旗问题
使用一次遍历将一堆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 { nums[p0], nums[i] = nums[i], nums[p0] 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) }
|