Go中的惯用法快速入门

Question

我正在看一下Go,并试图找到经典算法的惯用实现来感受语言.

我之所以选择quicksort,是因为我对数组与切片,就地与复制交易特别感兴趣.在我解决了一些概念后,我想写一个平行的impl.

有人可以告诉我一个惯用的quicksort实现Go吗？

Answer 1

好吧,我最终得到了这个.我不知道Go说它是惯用语,但我使用了切片,单行交换和一个range子句.这对我来说非常有用,所以我想我应该分享.

func qsort(a []int) []int {
  if len(a) < 2 { return a }

  left, right := 0, len(a) - 1

  // Pick a pivot
  pivotIndex := rand.Int() % len(a)

  // Move the pivot to the right
  a[pivotIndex], a[right] = a[right], a[pivotIndex]

  // Pile elements smaller than the pivot on the left
  for i := range a {
    if a[i] < a[right] {
      a[i], a[left] = a[left], a[i]
      left++
    }
  }

  // Place the pivot after the last smaller element
  a[left], a[right] = a[right], a[left]

  // Go down the rabbit hole
  qsort(a[:left])
  qsort(a[left + 1:])


  return a
}