算法64-荷兰国旗问题

题目：

给定一个数组，如[1,2,3,2,3,2,1,2,3,2,1],给出一个int=2，这个值必须存在数组中，要求将数组中的元素按小于int的值在左边，等于int的值在中间，大于的在右边

问题来源：

分析：

在说 “荷兰国旗” 问题之前，首先来看一个引例。

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1）,时间复杂度 O(N）
分析： 设定一个小于等于区，从0开始比较，如果当前数字小于等于num ，让其与小于等于区的下一个值做交换，再将小于等于区扩大一位，直到将所有的数字都与num进行过比较。重新排好的数组就是所求的数组。如下给出示意过程：


最终就可以得到一个在num左边所有的数都小于等于num右边都大于num。
这个过程实际上可以看成是小于等于区域在推着大于等于区域向右走，而当遇到小于等于num的数时，进行的操作是，与大于区域的第一个数字做交换，这听起来就有些像堆排序的heapify过程。

荷兰国旗问题（直观的“分三块”的问题）
—— 有了上面这些问题的基础，荷兰国旗问题就会好想一些。

给定一个数组arr,和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
分析： 上一个题目要求将数组分成两块，而这个是将数组分成三块。上一个问题是在左边设置了一个大于等于区，这个问题可以在左边设置一个小于区，在右边设置一个大于区，不断向中间逼近，最终中间就是相等的数字。操作过程也和上一个问题是完全一样的。如下过程所示：


有了上面的分析，代码就很容易理解

代码：

package main

import (
	"fmt"
	// "math"
	// "sort"
	// "time"
)

func partition(list []int,num int) []int{
	more:=len(list)
	less:=-1
	index:=0
	for  index < more{
		// fmt.Println("here")
		if list[index]<num{
			fmt.Printf("exchange idex  %v   less %v  ",index+1,less+1)
			swap(list,index,less+1)
			less++
			index++
			//小于去必然小于等于index，将一个小于num的的数放进小于区，不会引起小于区的混乱，
			//小于去已经是检查过的区域，必然符合规则，不用重新检测index位置
		}else if list[index]>num{
			fmt.Printf("exchange idx  %v  more  %v  ",index,more-1)
			swap(list,index,more-1)
			more--//大于区的数未知，放到index位置的话可能引起混乱，所以index不推进，从当前index继续检测
		}else{//等于什么都不做，，所以不会引起任何混乱，直接推进index检查下一位
			index++
		}
		fmt.Println(index)

		fmt.Println(list)

	}
	fmt.Println(less+1,more-1)
	result:=[]int{less+1,more-1}
	return result
}

func swap(list []int,m,n int){
	tmp:=list[m]
	list[m]=list[n]
	list[n]=tmp
}
func main(){
	// list:=[]int{15, 11, 53, 2, 14, 4, 25, 27, 45, 0,30,99,2}
	list:=[]int{1,2,3,1,2,3,2,1,2,3,2,1,2,2}

	partition(list,2)

}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

总结：
1 此方法类似快排的思想，但又有所不同
2 重点在于小于 等于 大于 三种条件的处理完全不同

• 小于-因为小于区是已经排好的，并且当前index指向的值已经知道是小于的，而且index的范围，相当于小于等于区，交换实质是将小于等于区的数与小于等于区的数交换，交换后还是小于等于区，并不会引起混乱，所以直接index++推进
• 等于-index的指针就是等于区的边界，所以无需交换，推进index
• 大于-因为大于区的数是未知的，将当前index的数与大于区的数交换，交换过来的数有可能是大于或是小于的，因此index不能推进，要进入下一次循环重新检测index的值

less小于区，index实际相当于小于等于区

完全理解了上面的逻辑，coding才能进行下去，在此详细记录

参考