安妮的心动录的园子
0%

Go常见手搓demo

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

博客:cbb777.fun

全平台账号:安妮的心动录

github: https://github.com/anneheartrecord

下文中我说的可能对，也可能不对，鉴于笔者水平有限，请君自辨。有问题欢迎大家找我讨论

手搓快排

需要注意的点有两个
1.循环里两数交换的条件为 i < j 意味着左指针还在右指针的左侧 即两者还没相遇
2.递归的时候一个是j  一个是j+1 把数组一分为二进行递归

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
func main() {
	nums := []int{3, 1, 2, 4, 6, 5}
	quickSort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}

func quickSort(nums []int, l, r int) {
	if l >= r {
		return
	}
	i, j, mid := l-1, r+1, nums[(l+r)/2]
	for i < j {
		i++
		for nums[i] < mid {
			i++
		}
		j--
		for nums[j] > mid {
			j--
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	quickSort(nums, l, j)
	quickSort(nums, j+1, r)
}

手搓堆排

需要注意的点：
1.heapify用来递归做调整 其中heapSize表示堆大小 i表示要操作的节点下标 left 和 right 的值分别是 2_i+1 与 2_i+2
2.buildHeap和heapify都传参都是i,n，而堆排的时候是维护一个当前大小的堆，所以是0,i

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
func main() {
	nums := []int{3, 1, 2, 4, 6, 5}
	heapSort(nums)
	fmt.Println(nums)
}

func buildHeap(nums []int, heapSize int) {
	for i := heapSize / 2; i >= 0; i-- {
		heapify(nums, i, heapSize)
	}
}

func heapSort(nums []int) {
	heapSize := len(nums)
	buildHeap(nums, heapSize)
	for i := heapSize - 1; i >= 0; i-- {
		nums[i], nums[0] = nums[0], nums[i]
		heapify(nums, 0, i)
	}
}

func heapify(nums []int, i, heapSize int) {
	largest := i
	left, right := 2*i+1, 2*i+2
	if left < heapSize && nums[left] > nums[largest] {
		largest = left
	}
	if right < heapSize && nums[right] > nums[largest] {
		largest = right
	}
	if largest != i {
		nums[largest], nums[i] = nums[i], nums[largest]
		heapify(nums, largest, heapSize)
	}
}

实现一个生产者-消费者模型

要注意的就是
通过select来实现一有消息就读，如果读完就退出
那怎么判断是否读完呢？这里就需要生产者主动关闭channel了

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
func main() {
	ch := make(chan int,10)
	go Processor(ch)
	go Consumer(ch)
  //睡一会
	time.Sleep(15 * time.Second)
}

func Processor(ch chan int) {
	for i := 0; i < 10; i++ {
		ch <- i
		// 模拟发时间的时延 这里可有可无
		//time.Sleep(1 * time.Second)
		fmt.Println("process:", i)
	}
	close(ch)
}

func Consumer(ch chan int) {
	for {
		select {
  	// 有数据就读出来 关闭了就退出
		case i, ok := <-ch:
			if ok {
				fmt.Println("consumer:", i)
			} else {
				fmt.Println("over!")
				return
			}
		}
	}
}

实现两个goroutine打印奇偶数

需要注意的点是
关闭通道的时候需要异步进行，也就是异步Wait()，然后立马关掉ch
同步的话会有一个问题就是Even和Odd都往这个ch中写东西了，但是没有人去消费它，所以我们只能选择手动关闭。但是等待for range完毕，然后同步关闭的话会导致ch阻塞（因为for range不是消费）

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
func Even(wg *sync.WaitGroup, ch chan int) {
	defer wg.Done()
	for i := 0; i <= 100; i += 2 {
		ch <- i
	}
}

func Odd(wg *sync.WaitGroup, ch chan int) {
	defer wg.Done()
	for i := 1; i <= 100; i += 2 {
		ch <- i
	}
}

func main() {
	var wg sync.WaitGroup
	ch := make(chan int)
	wg.Add(2)
	go Even(&wg, ch)
	go Odd(&wg, ch)
	go func() {
		wg.Wait()
		close(ch)
	}()
	for v := range ch {
		fmt.Println("number:", v)
	}
}

实现两个goroutine交替打印奇偶数

需要注意的点：
通道必须得是有缓冲的，不然在main goroutine中往里面<-1就会阻塞住，下面的go协程就不会执行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func Even(ch chan int) {
	for i := 0; i <= 100; i += 2 {
		<-ch
		fmt.Println("number:", i)
		ch <- 1
	}
}

func Odd(ch chan int) {
	for i := 1; i <= 100; i += 2 {
		<-ch
		fmt.Println("number:", i)
		ch <- 1
	}
}

func main() {
	ch := make(chan int, 1)
	ch <- 1
	go Even(ch)
	go Odd(ch)
	time.Sleep(time.Second)
}