Golang并发排序：使用Goroutines实现数字排序

GreyShatter:

behaviour

好问题，结果不同是因为 Go 协程的竞态条件，我有 4 个协程，每次都是其中一个先进行追加操作。

我刚刚找到一篇关于这个问题的好文章 🙂

Go 的 append 操作并非总是线程安全的

问题示例

阅读时间：3 分钟

你的代码存在数据竞争问题。divideList 函数中的 append 使用方式不正确，导致切片共享底层数组，当多个 goroutine 同时修改时会产生不可预测的结果。

主要问题在于：

1. divideList 函数没有创建新的底层数组
2. 切片 s1, s2, s3, s4 可能共享内存
3. 并发排序时数据相互覆盖

这是修复后的代码：

package main

import (
	"fmt"
	"sort"
)

// 创建切片的副本，避免共享底层数组
func divideList(list []int, cut int) ([]int, []int) {
	tmp := make([]int, len(list)-cut)
	copy(tmp, list[cut:])
	s := make([]int, cut)
	copy(s, list[:cut])
	return tmp, s
}

func sortList(list []int, c chan []int) {
	// 创建副本进行排序
	sorted := make([]int, len(list))
	copy(sorted, list)
	sort.Ints(sorted)
	c <- sorted
}

func main() {
	size := 5
	list := []int{-9, -11, 12, 13, 9}
	fmt.Println("Your digits input : ", list)

	// 创建独立的切片
	cut := size / 4
	remaining, s1 := divideList(list, cut)
	
	cut = len(remaining) / 3
	remaining, s2 := divideList(remaining, cut)
	
	cut = len(remaining) / 2
	remaining, s3 := divideList(remaining, cut)
	
	// s4 需要创建副本
	s4 := make([]int, len(remaining))
	copy(s4, remaining)

	// 在不同的Go协程中排序
	c := make(chan []int, 4)
	go sortList(s1, c)
	go sortList(s2, c)
	go sortList(s3, c)
	go sortList(s4, c)

	sortedS1 := <-c
	sortedS2 := <-c
	sortedS3 := <-c
	sortedS4 := <-c

	fmt.Println("Sorted slices:")
	fmt.Println(sortedS1)
	fmt.Println(sortedS2)
	fmt.Println(sortedS3)
	fmt.Println(sortedS4)
	fmt.Println("-----------------------")

	// 合并4个已排序的切片
	sortedList1 := append(sortedS1, sortedS2...)
	fmt.Println("First merge:", sortedList1)
	sortedList2 := append(sortedS3, sortedS4...)
	fmt.Println("Second merge:", sortedList2)
	finalList := append(sortedList1, sortedList2...)
	fmt.Println("Final merge:", finalList)

	// 最终排序
	sort.Ints(finalList)
	fmt.Println("Here your digits sorted: ", finalList)
}

更简洁的并发排序实现：

package main

import (
	"fmt"
	"sort"
	"sync"
)

func concurrentSort(numbers []int) []int {
	if len(numbers) <= 1 {
		return numbers
	}

	// 将切片分成4部分
	partSize := len(numbers) / 4
	var wg sync.WaitGroup
	results := make([][]int, 4)
	
	for i := 0; i < 4; i++ {
		wg.Add(1)
		go func(idx int) {
			defer wg.Done()
			start := idx * partSize
			end := start + partSize
			if idx == 3 {
				end = len(numbers)
			}
			
			// 创建副本进行排序
			part := make([]int, end-start)
			copy(part, numbers[start:end])
			sort.Ints(part)
			results[idx] = part
		}(i)
	}
	
	wg.Wait()
	
	// 合并结果
	var merged []int
	for _, part := range results {
		merged = append(merged, part...)
	}
	
	sort.Ints(merged)
	return merged
}

func main() {
	numbers := []int{-9, -11, 12, 13, 9, 5, -3, 0, 7, 8}
	fmt.Println("Original:", numbers)
	
	sorted := concurrentSort(numbers)
	fmt.Println("Sorted:", sorted)
}

关键点：

1. Go 切片是引用类型，共享底层数组
2. 并发操作时必须创建数据副本
3. append 在不扩容时会修改原切片
4. 使用 make 和 copy 创建独立的数据副本