Go 并行快速排序的死锁分析与解决方案

func quicksort(nums []int, ch chan int, level int, threads int)  {
  level *= 2;
  if len(nums) == 1 {  ch<- nums[0]; close(ch); return } // 基础情况：单个元素

  less := make([]int, 0)
  greater := make([]int,0)
  pivot := nums[0]
  nums = nums[1:] // 移除枢轴元素

  for _,i := range nums{
    switch{
    case i <= pivot:
      less = append(less,i)
    case i > pivot:
      greater = append(greater,i)
    }
  }

  ch1 := make(chan int, len(less))
  ch2 := make(chan int, len(greater))

  // 根据level和threads限制并行深度
  if(level <= threads){
    go quicksort(less, ch1, level, threads)
    go quicksort(greater,ch2, level, threads)
  }else{
    quicksort(less,ch1, level, threads) // 递归调用，非并行
    quicksort(greater,ch2, level, threads)
  }

  // 从子通道读取结果并写入当前通道
  for i := range ch1{
    ch<-i;
  }
  ch<-pivot // 写入枢轴元素
  for i := range ch2{
    ch<-i;
  }
  close(ch) // 关闭当前通道
  return
}

func quicksort(nums []int, ch chan int, level int, threads int)  {
  // 基础情况1: 空切片，直接关闭通道并返回
  if len(nums) == 0 {
    close(ch)
    return
  }
  // 基础情况2: 单个元素切片，写入元素，关闭通道并返回
  if len(nums) == 1 {
    ch <- nums[0]
    close(ch)
    return
  }

  // ... 后续逻辑不变

func main() {
    x := []int{3, 1, 4, 1, 5, 9, 2, 6}
    ch := make(chan int) // 仍然可以是无缓冲通道

    // 关键修正：在独立的协程中启动 quicksort
    go quicksort(x, ch, 0, 0)

    // 主协程现在可以从通道读取结果
    var sortedNums []int
    for v := range(ch) {
        sortedNums = append(sortedNums, v)
    }
    fmt.Println("Sorted:", sortedNums)
}

func quicksort(nums []int, ch chan int, level int, threads int)  {
  // 增加level，用于控制并发深度
  currentLevel := level + 1

  // 基础情况1: 空切片，直接关闭通道并返回
  if len(nums) == 0 {
    close(ch)
    return
  }
  // 基础情况2: 单个元素切片，写入元素，关闭通道并返回
  if len(nums) == 1 {
    ch <- nums[0]
    close(ch)
    return
  }

  // 选择枢轴并分区
  pivot := nums[0]
  less := make([]int, 0)
  greater := make([]int, 0)

  for _, i := range nums[1:] { // 从第二个元素开始遍历
    if i <= pivot {
      less = append(less, i)
    } else {
      greater = append(greater, i)
    }
  }

  // 创建子通道
  chLess := make(chan int, len(less)) // 缓冲通道可以减少阻塞
  chGreater := make(chan int, len(greater)) // 缓冲通道可以减少阻塞

  // 根据并发深度限制决定是否启动新协程
  if currentLevel <= threads {
    go quicksort(less, chLess, currentLevel, threads)
    go quicksort(greater, chGreater, currentLevel, threads)
  } else {
    // 达到并发深度限制，退化为串行递归
    quicksort(less, chLess, currentLevel, threads)
    quicksort(greater, chGreater, currentLevel, threads)
  }

  // 从子通道收集结果
  for val := range chLess {
    ch <- val
  }
  ch <- pivot // 写入枢轴元素
  for val := range chGreater {
    ch <- val
  }
  close(ch) // 完成所有写入，关闭当前通道
}