最后我写了这个。我不知道足够的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
}

看看标准库中sort package的源代码，特别是sort.sort。

简单地从一种语言（例如C）中提取代码，然后简单地将其转换为另一种语言（例如Go），很少会产生符合习惯的代码。
转到sort package--sort.c源文件

func quickSort(data Interface, a, b, maxDepth int) {
    // . . .
    // Avoiding recursion on the larger subproblem guarantees
    // a stack depth of at most lg(b-a). 
    // . . . 
}

这句话暗示了实现递归可能不是最好的策略，Go语言使用的是短栈。
下面是一个迭代Quicksort解决方案。

package main

import (
    "fmt"
    "math/rand"
    "time"
)

type Item int
type Items []Item

// Algorithms and Data Structures, N. Wirth
// http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf
// 2.3.3 Partition Sort, Quicksort, NonRecursiveQuickSort.
func qSort(a Items) {
    const M = 12
    var i, j, l, r int
    var x Item
    var low, high = make([]int, 0, M), make([]int, 0, M)

    low, high = append(low, 0), append(high, len(a)-1)
    for { // (*take top request from stack*)
        l, low = low[len(low)-1], low[:len(low)-1]
        r, high = high[len(high)-1], high[:len(high)-1]
        for { // (*partition a[l] ... a[r]*)
            i, j = l, r
            x = a[l+(r-l)/2]
            for {
                for ; a[i] < x; i++ {
                }
                for ; x < a[j]; j-- {
                }
                if i <= j {
                    a[i], a[j] = a[j], a[i]
                    i++
                    j--
                }
                if i > j {
                    break
                }
            }
            if i < r { // (*stack request to sort right partition*)
                low, high = append(low, i), append(high, r)
            }
            r = j // (*now l and r delimit the left partition*)
            if l >= r {
                break
            }
        }
        if len(low)+len(high) == 0 {
            break
        }
    }
}

func main() {
    nItems := 4096
    a := make(Items, nItems)
    rand.Seed(time.Now().UnixNano())
    for i := range a {
        a[i] = Item(rand.Int31())
    }
    qSort(a)
    for i := range a[1:] {
        if a[i] > a[i+1] {
            fmt.Println("(* sort error *)")
        }
    }
}

显然，还有很多工作要做，例如，改进分区算法，将qsort函数签名改为Go interface类型。

我现在刚刚开始学习Go语言，并决定将qsort作为一个简单的任务来实现，使用通道和并行性，因为在qsort中，你可以在对数组进行旋转后同时对两部分进行排序。

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func qsort_pass(arr []int, done chan int) []int{
    if len(arr) < 2 {
        done <- len(arr)
        return arr
    }
    pivot := arr[0]
    i, j := 1, len(arr)-1
    for i != j {
        for arr[i] < pivot && i!=j{
            i++
        }
        for arr[j] >= pivot && i!=j{
            j--
        }
        if arr[i] > arr[j] {
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    if arr[j] >= pivot {
        j--
    }
    arr[0], arr[j] = arr[j], arr[0]
    done <- 1;

    go qsort_pass(arr[:j], done)
    go qsort_pass(arr[j+1:], done)
    return arr
}

func qsort(arr []int) []int {
    done := make(chan int)
    defer func() {
        close(done)
    }()

    go qsort_pass(arr[:], done)

    rslt := len(arr)
    for rslt > 0 {
        rslt -= <-done;
    }
    return arr
}

func main() {
    fmt.Println("About to sort.")
    rand.Seed(time.Now().UTC().UnixNano())
    arr_rand := make([]int, 20)
    for i := range arr_rand {
        arr_rand[i] = rand.Intn(10)
    }
    fmt.Println(arr_rand)
    qsort(arr_rand)
    fmt.Println(arr_rand)
}

这里还有很多改进的空间，比如使用一个go例程池，而不是为每个分区生成一个新的go例程，如果len（arr）足够小，则使用插入排序，或者使用[] int以外的其他方法。

你可以好好想想。

func quickSort(arr []int) []int {
    sort(arr, 0, len(arr) - 1)

    return arr
}

func sort(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high)
        sort(arr, low, pi-1)
        sort(arr, pi+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low-1

    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }

    arr[i+1], arr[high] = arr[high], arr[i+1]

    return i+1
}

对于Go语言1.18及以上版本，使用泛型：

import (
    "golang.org/x/exp/constraints"
)

func QuickSort[T constraints.Ordered](a []T) {
    if len(a) > 1 {
        quickSort(a, 0, len(a)-1)
    }
}

func quickSort[T constraints.Ordered](a []T, lo, hi int) {
    if lo < hi {
        p := partition(a, lo, hi)
        quickSort(a, lo, p-1)
        quickSort(a, p+1, hi)
    }
}

func partition[T constraints.Ordered](a []T, lo, hi int) int {
    l, p := lo, findPivot(a, lo, hi)
    for r := lo; r < hi; r++ {
        if a[r] < a[p] {
            a[l], a[r] = a[r], a[l]
            l++
        }
    }
    a[l], a[p] = a[p], a[l]
    return l
}

// median of three technique
func findPivot[T constraints.Ordered](a []T, lo, hi int) int {
    mi := (lo + hi) / 2
    if a[lo] > a[mi] {
        a[lo], a[mi] = a[mi], a[lo]
    }
    if a[lo] > a[hi] {
        a[lo], a[hi] = a[hi], a[lo]
    }
    if a[mi] > a[hi] {
        a[mi], a[hi] = a[hi], a[mi]
    }
    a[mi], a[hi-1] = a[hi-1], a[mi]
    return hi - 1
}

用法：

a := []int{1, 8, 4, 9, 6, 3, 5, 2, 7, 0}
fmt.Println(a, "(original)")
QuickSort(a)
fmt.Println(a, "(sorted)")

b := []string{"tuv", "abc", "jkl", "ghi", "mno", "wxyz", "def", "pqrs"}
fmt.Println(b, "(original)")
QuickSort(b)
fmt.Println(b, "(sorted)")

func QuickSortArr(arr []int) {
    var i int
    var j int
    var hi int
    var hSave bool
    aLen := len(arr)
    helpArr := make([]int, aLen)
    hSave = true
    var tmpHelp []int
    var tmpArr []int

    for m := 1; m < aLen; m += m {
        i = 0
        j = 0 + m
        hi = 0
        if hSave {
            tmpHelp = helpArr
            tmpArr = arr
        } else {
            tmpHelp = arr
            tmpArr = helpArr
        }
        for i < aLen && j < aLen {
            i2 := i + m
            j2 := j + m
            for i < i2 && i < aLen && j < j2 && j < aLen {
                if tmpArr[i] > tmpArr[j] {
                    tmpHelp[hi] = tmpArr[j]
                    hi++
                    j++
                } else {
                    tmpHelp[hi] = tmpArr[i]
                    hi++
                    i++
                }
            }
            for i < i2 && i < aLen {
                tmpHelp[hi] = tmpArr[i]
                hi++
                i++
            }
            for j < j2 && j < aLen {
                tmpHelp[hi] = tmpArr[j]
                hi++
                j++
            }

            i += m
            j += m
        }

        for i < aLen {
            tmpHelp[hi] = tmpArr[i]
            hi++
            i++
        }
        for j < aLen {
            tmpHelp[hi] = tmpArr[j]
            hi++
            j++
        }

        hSave = !hSave
    }

    if !hSave {
        copy(arr, helpArr)
    }
}

下面是我根据Grokking算法一书中的Python例子构建的一个解决方案，感觉不那么复杂，所以我想分享一下。

package main

import "fmt"

func main() {
    list := []int{33, 10, 15, 45, 65, 16, 5}

    fmt.Println(quicksort(list))
}

func quicksort(list []int) []int {
    if len(list) < 2 {
        return list
    }
    if len(list) == 2 {
        left, right := 0, len(list)-1
        if list[0] > list[1] {
            list[left], list[right] = list[right], list[left]
        }
        return list
    }

    pivot := list[0]
    var less []int
    var greater []int

    for i := range list {
        if list[i] < pivot {
            less = append(less, list[i])
        }
        if list[i] > pivot {
            greater = append(greater, list[i])
        }
    }

    return append(append(quicksort(less), pivot), quicksort(greater)...)
}

您可以在Go Playground here上运行它。