go - Go 中惯用的快速排序

Question

我正在研究 Go，并试图找到经典算法的惯用实现来感受这门语言。

我选择快速排序是因为我对数组与 slice 、就地与复制处理特别感兴趣。在我确定了一些概念之后，我想写一个并行实现。

谁能告诉我在 Go 中快速排序的惯用实现？

Answer 1

好吧，我最终得到了这个。我对 Go 的了解还不足以说它是地道的，但我使用了 slice 、单行交换和一个 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
}