Go中的Quicksort

Question

我正在学习Go,并尝试实施快速排序,但它没有返回完整列表.根据我对Go的理解,它与我编写的正常运行的Ruby实现相匹配.

我的代码是:

func quickSort(data []string) []string {
  if len(data) > 1 {
    pivot := data[0]
    smaller := make([]string, 0, len(data))
    equal := make([]string, 0, len(data))
    larger := make([]string, 0, len(data))
    for i := 1; i < len(data); i++ {
      if data[i] > pivot {
        larger = append(larger, data[i])
      } else if data[i] < pivot {
        smaller = append(smaller, data[i])
      } else {
        equal = append(equal, data[i])
      }
    }
    return append(append(quickSort(smaller), equal...), quickSort(larger)...)
  } else {
    return data
  }
}

我很困惑,因为这不起作用.

Answer 1

您遇到的错误是您永远不会将透视值附加到返回的切片.因此,对于每个递归调用,您将失去支点.

对代码进行以下更改,它将起作用:

equal := make([]string, 1, len(data))
equal[0] = pivot