Go中的Quicksort

Question

I'm learning Go, and tried to implement a quicksort, however it doesn't return a complete list. To my understanding of Go it matches with a functioning Ruby implementation I wrote.

My code is:

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
  }
}

I am very puzzled as to what in this doesn't work.

Answer 1

The bug you have is that you never append the pivot value to the returned slice. So for each recursive call, you will lose the pivot.

Make the following change to the code and it will work:

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