Go中的惯用快速排序

huangapple
go评论121阅读模式
英文:

Idiomatic quicksort in Go

问题

我正在研究Go，并试图寻找经典算法的惯用实现，以便对这种语言有所了解。

我选择了快速排序，因为我对数组与切片、原地排序与复制排序很感兴趣。在我弄清楚一些概念之后，我想编写一个并行实现。

有人可以展示一下Go中的快速排序的惯用实现吗？

英文:

I'm taking a look at Go, and was trying to find idiomatic implementations of classic algorithms to get a feel for the language.

I chose quicksort because I'm particularly interested in the arrays vs slices, in-place vs copy deal. After I settle some concepts down, I want to write a parallel impl.

Can someone please show me an idiomatic implementation of quicksort in Go?

答案1

得分: 37

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

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

// 选择一个基准点
pivotIndex := rand.Int() % len(a)

// 将基准点移到右边
a[pivotIndex], a[right] = a[right], a[pivotIndex]

// 将比基准点小的元素堆放在左边
for i := range a {
if a[i] < a[right] {
a[i], a[left] = a[left], a[i]
left++
}
}

// 将基准点放在最后一个较小元素之后
a[left], a[right] = a[right], a[left]

// 递归调用
qsort(a[:left])
qsort(a[left + 1:])

return a
}

英文:

Well, I ended up with this. I don't know enough Go to say it's idiomatic, but I used slices, one-line swaps and a range clause. It's been pretty informative for me to write, so I thought I should share.

  1. func qsort(a []int) []int {
  2.   if len(a) &lt; 2 { return a }
  4.   left, right := 0, len(a) - 1
  6.   // Pick a pivot
  7.   pivotIndex := rand.Int() % len(a)
  9.   // Move the pivot to the right
  10.   a[pivotIndex], a[right] = a[right], a[pivotIndex]
  12.   // Pile elements smaller than the pivot on the left
  13.   for i := range a {
  14.     if a[i] &lt; a[right] {
  15.       a[i], a[left] = a[left], a[i]
  16.       left++
  17.     }
  18.   }
  20.   // Place the pivot after the last smaller element
  21.   a[left], a[right] = a[right], a[left]
  23.   // Go down the rabbit hole
  24.   qsort(a[:left])
  25.   qsort(a[left + 1:])
  28.   return a
  29. }

答案2

得分: 4

看一下标准库中的sort包的源代码，特别是sort.Sort函数。

英文:

Take a look at the source of the sort package from the standard library, particularily sort.Sort.

答案3

得分: 1

只返回翻译好的部分：

仅仅将代码从一种语言（例如C）简单地转换为另一种语言（例如Go），很少会产生习惯用法的代码。

这个注释是一个提示，实现递归解决方案可能不是最佳策略。Go使用短栈。

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

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/rand"
  6. 	"time"
  7. )
  9. type Item int
  10. type Items []Item
  12. // 算法与数据结构，N. Wirth
  13. // http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf
  14. // 2.3.3 Partition Sort, Quicksort, NonRecursiveQuickSort.
  15. func qSort(a Items) {
  16. 	const M = 12
  17. 	var i, j, l, r int
  18. 	var x Item
  19. 	var low, high = make([]int, 0, M), make([]int, 0, M)
  21. 	low, high = append(low, 0), append(high, len(a)-1)
  22. 	for { // (*从栈中取出顶部请求*)
  23. 		l, low = low[len(low)-1], low[:len(low)-1]
  24. 		r, high = high[len(high)-1], high[:len(high)-1]
  25. 		for { // (*对a[l] ... a[r]进行分区*)
  26. 			i, j = l, r
  27. 			x = a[l+(r-l)/2]
  28. 			for {
  29. 				for ; a[i] < x; i++ {
  30. 				}
  31. 				for ; x < a[j]; j-- {
  32. 				}
  33. 				if i <= j {
  34. 					a[i], a[j] = a[j], a[i]
  35. 					i++
  36. 					j--
  37. 				}
  38. 				if i > j {
  39. 					break
  40. 				}
  41. 			}
  42. 			if i < r { // (*将右分区的请求压入栈*)
  43. 				low, high = append(low, i), append(high, r)
  44. 			}
  45. 			r = j // (*现在l和r界定了左分区*)
  46. 			if l >= r {
  47. 				break
  48. 			}
  49. 		}
  50. 		if len(low)+len(high) == 0 {
  51. 			break
  52. 		}
  53. 	}
  54. }
  56. func main() {
  57. 	nItems := 4096
  58. 	a := make(Items, nItems)
  59. 	rand.Seed(time.Now().UnixNano())
  60. 	for i := range a {
  61. 		a[i] = Item(rand.Int31())
  62. 	}
  63. 	qSort(a)
  64. 	for i := range a[1:] {
  65. 		if a[i] > a[i+1] {
  66. 			fmt.Println("(* 排序错误 *)")
  67. 		}
  68. 	}
  69. }

显然，还有更多工作要做。例如，改进分区算法并更改qsort函数的签名以使用Go的interface类型。

英文:

Simply taking code from one language, for example C, and simplistically converting it to another language, for example Go, rarely produces idiomatic code.

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

This comment is a clue that implementing a recursive solution may not be the best strategy. Go uses short stacks.

Here's an iterative Quicksort solution.

  1. package main
  2. import (
  3. &quot;fmt&quot;
  4. &quot;math/rand&quot;
  5. &quot;time&quot;
  6. )
  7. type Item int
  8. type Items []Item
  9. // Algorithms and Data Structures, N. Wirth
  10. // http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf
  11. // 2.3.3 Partition Sort, Quicksort, NonRecursiveQuickSort.
  12. func qSort(a Items) {
  13. const M = 12
  14. var i, j, l, r int
  15. var x Item
  16. var low, high = make([]int, 0, M), make([]int, 0, M)
  17. low, high = append(low, 0), append(high, len(a)-1)
  18. for { // (*take top request from stack*)
  19. l, low = low[len(low)-1], low[:len(low)-1]
  20. r, high = high[len(high)-1], high[:len(high)-1]
  21. for { // (*partition a[l] ... a[r]*)
  22. i, j = l, r
  23. x = a[l+(r-l)/2]
  24. for {
  25. for ; a[i] &lt; x; i++ {
  26. }
  27. for ; x &lt; a[j]; j-- {
  28. }
  29. if i &lt;= j {
  30. a[i], a[j] = a[j], a[i]
  31. i++
  32. j--
  33. }
  34. if i &gt; j {
  35. break
  36. }
  37. }
  38. if i &lt; r { // (*stack request to sort right partition*)
  39. low, high = append(low, i), append(high, r)
  40. }
  41. r = j // (*now l and r delimit the left partition*)
  42. if l &gt;= r {
  43. break
  44. }
  45. }
  46. if len(low)+len(high) == 0 {
  47. break
  48. }
  49. }
  50. }
  51. func main() {
  52. nItems := 4096
  53. a := make(Items, nItems)
  54. rand.Seed(time.Now().UnixNano())
  55. for i := range a {
  56. a[i] = Item(rand.Int31())
  57. }
  58. qSort(a)
  59. for i := range a[1:] {
  60. if a[i] &gt; a[i+1] {
  61. fmt.Println(&quot;(* sort error *)&quot;)
  62. }
  63. }
  64. }

Clearly, there is more to be done. For example, improving the partitioning algorithm and changing the qsort function signature to use a Go interface type.

答案4

得分: 1

我现在只是学习go，并决定实现qsort作为一个简单的任务，使用通道和并行性，因为在qsort中，在对数组进行枢轴划分后，可以同时对两个子数组进行排序。我最终得到了以下代码：

  1. package main
  2. import (
  3. "fmt"
  4. "math/rand"
  5. "time"
  6. )
  7. func qsort_pass(arr []int, done chan int) []int{
  8. if len(arr) < 2 {
  9. done <- len(arr)
  10. return arr
  11. }
  12. pivot := arr[0]
  13. i, j := 1, len(arr)-1
  14. for i != j {
  15. for arr[i] < pivot && i!=j{
  16. i++
  17. }
  18. for arr[j] >= pivot && i!=j{
  19. j--
  20. }
  21. if arr[i] > arr[j] {
  22. arr[i], arr[j] = arr[j], arr[i]
  23. }
  24. }
  25. if arr[j] >= pivot {
  26. j--
  27. }
  28. arr[0], arr[j] = arr[j], arr[0]
  29. done <- 1;
  30. go qsort_pass(arr[:j], done)
  31. go qsort_pass(arr[j+1:], done)
  32. return arr
  33. }
  34. func qsort(arr []int) []int {
  35. done := make(chan int)
  36. defer func() {
  37. close(done)
  38. }()
  39. go qsort_pass(arr[:], done)
  40. rslt := len(arr)
  41. for rslt > 0 {
  42. rslt -= <-done;
  43. }
  44. return arr
  45. }
  46. func main() {
  47. fmt.Println("About to sort.")
  48. rand.Seed(time.Now().UTC().UnixNano())
  49. arr_rand := make([]int, 20)
  50. for i := range arr_rand {
  51. arr_rand[i] = rand.Intn(10)
  52. }
  53. fmt.Println(arr_rand)
  54. qsort(arr_rand)
  55. fmt.Println(arr_rand)
  56. }

这里有很多可以改进的地方，比如使用go协程池而不是为每个分区生成一个新的go协程，并且如果len(arr)足够小，可以使用插入排序进行排序，或者使用其他类型而不是[]int。但总体上看起来是一个不错的起点。

英文:

I'm just learning go right now and decided to implement qsort as a simple task, using channels and parallelism since in qsort you can sort both halves concurrently after pivoting the array. I ended up with smth like that:

  1. package main
  2. import (
  3. &quot;fmt&quot;
  4. &quot;math/rand&quot;
  5. &quot;time&quot;
  6. )
  7. func qsort_pass(arr []int, done chan int) []int{
  8. if len(arr) &lt; 2 {
  9. done &lt;- len(arr)
  10. return arr
  11. }
  12. pivot := arr[0]
  13. i, j := 1, len(arr)-1
  14. for i != j {
  15. for arr[i] &lt; pivot &amp;&amp; i!=j{
  16. i++
  17. }
  18. for arr[j] &gt;= pivot &amp;&amp; i!=j{
  19. j--
  20. }
  21. if arr[i] &gt; arr[j] {
  22. arr[i], arr[j] = arr[j], arr[i]
  23. }
  24. }
  25. if arr[j] &gt;= pivot {
  26. j--
  27. }
  28. arr[0], arr[j] = arr[j], arr[0]
  29. done &lt;- 1;
  30. go qsort_pass(arr[:j], done)
  31. go qsort_pass(arr[j+1:], done)
  32. return arr
  33. }
  34. func qsort(arr []int) []int {
  35. done := make(chan int)
  36. defer func() {
  37. close(done)
  38. }()
  39. go qsort_pass(arr[:], done)
  40. rslt := len(arr)
  41. for rslt &gt; 0 {
  42. rslt -= &lt;-done;
  43. }
  44. return arr
  45. }
  46. func main() {
  47. fmt.Println(&quot;About to sort.&quot;)
  48. rand.Seed(time.Now().UTC().UnixNano())
  49. arr_rand := make([]int, 20)
  50. for i := range arr_rand {
  51. arr_rand[i] = rand.Intn(10)
  52. }
  53. fmt.Println(arr_rand)
  54. qsort(arr_rand)
  55. fmt.Println(arr_rand)
  56. }

There's plenty of room for improvement here like using a pool of go-routines instead of spawning a new go-routine for each partition, and sorting with insertion sort if len(arr) is small enough or using something other than []int. But generally it looks like a good place to start.

答案5

得分: 0

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

  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

  1. for j := low; j < high; j++ {
  2. if arr[j] <= pivot {
  3. i++
  4. arr[i], arr[j] = arr[j], arr[i]
  5. }
  6. }
  7. arr[i+1], arr[high] = arr[high], arr[i+1]
  8. return i+1

}

英文:

Could use some thoughts on this.

  1. func quickSort(arr []int) []int {
  2. sort(arr, 0, len(arr) - 1)
  3. return arr
  4. }
  5. func sort(arr []int, low, high int) {
  6. if low &lt; high {
  7. pi := partition(arr, low, high)
  8. sort(arr, low, pi-1)
  9. sort(arr, pi+1, high)
  10. }
  11. }
  12. func partition(arr []int, low, high int) int {
  13. pivot := arr[high]
  14. i := low-1
  15. for j := low; j &lt; high; j++ {
  16. if arr[j] &lt;= pivot {
  17. i++
  18. arr[i], arr[j] = arr[j], arr[i]
  19. }
  20. }
  21. arr[i+1], arr[high] = arr[high], arr[i+1]
  22. return i+1
  23. }

答案6

得分: 0

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

  1. import (
  2. 	"golang.org/x/exp/constraints"
  3. )
  5. func QuickSort[T constraints.Ordered](a []T) {
  6. 	if len(a) > 1 {
  7. 		quickSort(a, 0, len(a)-1)
  8. 	}
  9. }
  11. func quickSort[T constraints.Ordered](a []T, lo, hi int) {
  12. 	if lo < hi {
  13. 		p := partition(a, lo, hi)
  14. 		quickSort(a, lo, p-1)
  15. 		quickSort(a, p+1, hi)
  16. 	}
  17. }
  19. func partition[T constraints.Ordered](a []T, lo, hi int) int {
  20. 	l, p := lo, findPivot(a, lo, hi)
  21. 	for r := lo; r < hi; r++ {
  22. 		if a[r] < a[p] {
  23. 			a[l], a[r] = a[r], a[l]
  24. 			l++
  25. 		}
  26. 	}
  27. 	a[l], a[p] = a[p], a[l]
  28. 	return l
  29. }
  31. // 三数取中法
  32. func findPivot[T constraints.Ordered](a []T, lo, hi int) int {
  33. 	mi := (lo + hi) / 2
  34. 	if a[lo] > a[mi] {
  35. 		a[lo], a[mi] = a[mi], a[lo]
  36. 	}
  37. 	if a[lo] > a[hi] {
  38. 		a[lo], a[hi] = a[hi], a[lo]
  39. 	}
  40. 	if a[mi] > a[hi] {
  41. 		a[mi], a[hi] = a[hi], a[mi]
  42. 	}
  43. 	a[mi], a[hi-1] = a[hi-1], a[mi]
  44. 	return hi - 1
  45. }

用法：

  1. a := []int{1, 8, 4, 9, 6, 3, 5, 2, 7, 0}
  2. fmt.Println(a, "(原始)")
  3. QuickSort(a)
  4. fmt.Println(a, "(排序)")
  6. b := []string{"tuv", "abc", "jkl", "ghi", "mno", "wxyz", "def", "pqrs"}
  7. fmt.Println(b, "(原始)")
  8. QuickSort(b)
  9. fmt.Println(b, "(排序)")
英文:

For Go 1.18 and above, using generics:

  1. import (
  2. &quot;golang.org/x/exp/constraints&quot;
  3. )
  4. func QuickSort[T constraints.Ordered](a []T) {
  5. if len(a) &gt; 1 {
  6. quickSort(a, 0, len(a)-1)
  7. }
  8. }
  9. func quickSort[T constraints.Ordered](a []T, lo, hi int) {
  10. if lo &lt; hi {
  11. p := partition(a, lo, hi)
  12. quickSort(a, lo, p-1)
  13. quickSort(a, p+1, hi)
  14. }
  15. }
  16. func partition[T constraints.Ordered](a []T, lo, hi int) int {
  17. l, p := lo, findPivot(a, lo, hi)
  18. for r := lo; r &lt; hi; r++ {
  19. if a[r] &lt; a
     {
  20. a[l], a[r] = a[r], a[l]
  21. l++
  22. }
  23. }
  24. a[l], a
     = a
    , a[l]
  25. return l
  26. }
  27. // median of three technique
  28. func findPivot[T constraints.Ordered](a []T, lo, hi int) int {
  29. mi := (lo + hi) / 2
  30. if a[lo] &gt; a[mi] {
  31. a[lo], a[mi] = a[mi], a[lo]
  32. }
  33. if a[lo] &gt; a[hi] {
  34. a[lo], a[hi] = a[hi], a[lo]
  35. }
  36. if a[mi] &gt; a[hi] {
  37. a[mi], a[hi] = a[hi], a[mi]
  38. }
  39. a[mi], a[hi-1] = a[hi-1], a[mi]
  40. return hi - 1
  41. }

Usage:

  1. a := []int{1, 8, 4, 9, 6, 3, 5, 2, 7, 0}
  2. fmt.Println(a, &quot;(original)&quot;)
  3. QuickSort(a)
  4. fmt.Println(a, &quot;(sorted)&quot;)
  5. b := []string{&quot;tuv&quot;, &quot;abc&quot;, &quot;jkl&quot;, &quot;ghi&quot;, &quot;mno&quot;, &quot;wxyz&quot;, &quot;def&quot;, &quot;pqrs&quot;}
  6. fmt.Println(b, &quot;(original)&quot;)
  7. QuickSort(b)
  8. fmt.Println(b, &quot;(sorted)&quot;)

答案7

得分: 0

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

  1. for m := 1; m < aLen; m += m {
  2. i = 0
  3. j = 0 + m
  4. hi = 0
  5. if hSave {
  6. tmpHelp = helpArr
  7. tmpArr = arr
  8. } else {
  9. tmpHelp = arr
  10. tmpArr = helpArr
  11. }
  12. for i < aLen && j < aLen {
  13. i2 := i + m
  14. j2 := j + m
  15. for i < i2 && i < aLen && j < j2 && j < aLen {
  16. if tmpArr[i] > tmpArr[j] {
  17. tmpHelp[hi] = tmpArr[j]
  18. hi++
  19. j++
  20. } else {
  21. tmpHelp[hi] = tmpArr[i]
  22. hi++
  23. i++
  24. }
  25. }
  26. for i < i2 && i < aLen {
  27. tmpHelp[hi] = tmpArr[i]
  28. hi++
  29. i++
  30. }
  31. for j < j2 && j < aLen {
  32. tmpHelp[hi] = tmpArr[j]
  33. hi++
  34. j++
  35. }
  36. i += m
  37. j += m
  38. }
  39. for i < aLen {
  40. tmpHelp[hi] = tmpArr[i]
  41. hi++
  42. i++
  43. }
  44. for j < aLen {
  45. tmpHelp[hi] = tmpArr[j]
  46. hi++
  47. j++
  48. }
  49. hSave = !hSave
  50. }
  51. if !hSave {
  52. copy(arr, helpArr)
  53. }

}

英文: 
  1. func QuickSortArr(arr []int) {
  2. var i int
  3. var j int
  4. var hi int
  5. var hSave bool
  6. aLen := len(arr)
  7. helpArr := make([]int, aLen)
  8. hSave = true
  9. var tmpHelp []int
  10. var tmpArr []int
  11. for m := 1; m &lt; aLen; m += m {
  12. i = 0
  13. j = 0 + m
  14. hi = 0
  15. if hSave {
  16. tmpHelp = helpArr
  17. tmpArr = arr
  18. } else {
  19. tmpHelp = arr
  20. tmpArr = helpArr
  21. }
  22. for i &lt; aLen &amp;&amp; j &lt; aLen {
  23. i2 := i + m
  24. j2 := j + m
  25. for i &lt; i2 &amp;&amp; i &lt; aLen &amp;&amp; j &lt; j2 &amp;&amp; j &lt; aLen {
  26. if tmpArr[i] &gt; tmpArr[j] {
  27. tmpHelp[hi] = tmpArr[j]
  28. hi++
  29. j++
  30. } else {
  31. tmpHelp[hi] = tmpArr[i]
  32. hi++
  33. i++
  34. }
  35. }
  36. for i &lt; i2 &amp;&amp; i &lt; aLen {
  37. tmpHelp[hi] = tmpArr[i]
  38. hi++
  39. i++
  40. }
  41. for j &lt; j2 &amp;&amp; j &lt; aLen {
  42. tmpHelp[hi] = tmpArr[j]
  43. hi++
  44. j++
  45. }
  46. i += m
  47. j += m
  48. }
  49. for i &lt; aLen {
  50. tmpHelp[hi] = tmpArr[i]
  51. hi++
  52. i++
  53. }
  54. for j &lt; aLen {
  55. tmpHelp[hi] = tmpArr[j]
  56. hi++
  57. j++
  58. }
  59. hSave = !hSave
  60. }
  61. if !hSave {
  62. copy(arr, helpArr)
  63. }
  64. }

答案8

得分: 0

这是我根据《算法图解》一书中的Python示例编写的解决方案。感觉它没有那么令人费解，所以我想分享一下。

  1. package main
  2. import "fmt"
  3. func main() {
  4. list := []int{33, 10, 15, 45, 65, 16, 5}
  5. fmt.Println(quicksort(list))
  6. }
  7. func quicksort(list []int) []int {
  8. if len(list) < 2 {
  9. return list
  10. }
  11. if len(list) == 2 {
  12. left, right := 0, len(list)-1
  13. if list[0] > list[1] {
  14. list[left], list[right] = list[right], list[left]
  15. }
  16. return list
  17. }
  18. pivot := list[0]
  19. var less []int
  20. var greater []int
  21. for i := range list {
  22. if list[i] < pivot {
  23. less = append(less, list[i])
  24. }
  25. if list[i] > pivot {
  26. greater = append(greater, list[i])
  27. }
  28. }
  29. return append(append(quicksort(less), pivot), quicksort(greater)...)
  30. }

你可以在Go Playground上运行它这里。

英文:

Here's a solution I built following the Python examples in the book Grokking algorithms. It felt a little less mind bending, so I thought I'd share.

  1. package main
  2. import &quot;fmt&quot;
  3. func main() {
  4. list := []int{33, 10, 15, 45, 65, 16, 5}
  5. fmt.Println(quicksort(list))
  6. }
  7. func quicksort(list []int) []int {
  8. if len(list) &lt; 2 {
  9. return list
  10. }
  11. if len(list) == 2 {
  12. left, right := 0, len(list)-1
  13. if list[0] &gt; list[1] {
  14. list[left], list[right] = list[right], list[left]
  15. }
  16. return list
  17. }
  18. pivot := list[0]
  19. var less []int
  20. var greater []int
  21. for i := range list {
  22. if list[i] &lt; pivot {
  23. less = append(less, list[i])
  24. }
  25. if list[i] &gt; pivot {
  26. greater = append(greater, list[i])
  27. }
  28. }
  29. return append(append(quicksort(less), pivot), quicksort(greater)...)
  30. }

You can run it on the Go Playground here.

huangapple
  • 本文由 发表于 2013年4月4日 13:04:02
  • 转载请务必保留本文链接：https://go.coder-hub.com/15802890.html
  • go
  • quicksort
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定