go - Go 中惯用的快速排序

Question

我正在查看Go，并试图找到经典算法的惯用实现来感受该语言。

我选择快速排序是因为我对数组与切片、就地与复制交易特别感兴趣。在我解决了一些概念之后，我想编写一个并行 impl。

有人可以告诉我快速排序的惯用实现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
}

Answer 2

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

Answer 3

简单地从一种语言（例如 C）中获取代码，然后简单地将其转换为另一种语言（例如 Go），很少会产生惯用的代码。

Go排序包——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 使用短堆栈。

这是一个迭代快速排序解决方案。

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函数签名以使用 Gointerface类型。

Answer 4

我现在正在学习 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-routines 池而不是为每个分区生成一个新的 go-routine，如果 len(arr) 足够小或使用 []int 以外的其他东西，则使用插入排序进行排序。但总的来说，它看起来是一个不错的起点。

Answer 5

可以使用一些想法。

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
}