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
}
func quickSort(data Interface, a, b, maxDepth int) {
// . . .
// Avoiding recursion on the larger subproblem guarantees
// a stack depth of at most lg(b-a).
// . . .
}
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 *)")
}
}
}
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)
}
}
8条答案
按热度按时间798qvoo81#
最后我写了这个。我不知道足够的
Go
来说它是 * 惯用的 *,但是我使用了切片、单行交换和range
子句。这对我来说是非常有用的,所以我想我应该分享一下。scyqe7ek2#
看看标准库中sort package的源代码,特别是sort.sort。
35g0bw713#
简单地从一种语言(例如C)中提取代码,然后简单地将其转换为另一种语言(例如Go),很少会产生符合习惯的代码。
转到sort package--sort.c源文件
这句话暗示了实现递归可能不是最好的策略,Go语言使用的是短栈。
下面是一个迭代Quicksort解决方案。
显然,还有很多工作要做,例如,改进分区算法,将
qsort
函数签名改为Gointerface
类型。clj7thdc4#
我现在刚刚开始学习Go语言,并决定将qsort作为一个简单的任务来实现,使用通道和并行性,因为在qsort中,你可以在对数组进行旋转后同时对两部分进行排序。
这里还有很多改进的空间,比如使用一个go例程池,而不是为每个分区生成一个新的go例程,如果len(arr)足够小,则使用插入排序,或者使用[] int以外的其他方法。
luaexgnf5#
你可以好好想想。
c2e8gylq6#
对于Go语言1.18及以上版本,使用泛型:
用法:
iibxawm47#
f0brbegy8#
下面是我根据Grokking算法一书中的Python例子构建的一个解决方案,感觉不那么复杂,所以我想分享一下。
您可以在Go Playground here上运行它。