package main import ( "fmt" "math/rand" "sort" "time" ) // func partition(arr []int, start, end int) (p int) { // if start >= end { // return // } // // i, j, pivot := start, end, arr[start] // for i < j { // // 自右向左找一个小于等于基准的元素 // for i < j && arr[j] > pivot { // j-- // } // // // 自左向右找一个大于基准的元素 // for i < j && arr[i] <= pivot { // i++ // } // // if i < j { // // 交换位置 // arr[i], arr[j] = arr[j], arr[i] // } // } // // // 更新基准 // arr[i], arr[start] = arr[start], arr[i] // // return i // // } func partition(a []int, left, right int) int { pivot := a[right] i := left for j := left; j < right; j++ { // 如果比基准小就换到前面 if pivot > a[j] { // fmt.Println(i, j) a[j], a[i] = a[i], a[j] // i 记录换过的位置,i 之前都比基准小 i++ } } // 更新基准 a[i], a[right] = a[right], a[i] return i } func quickSort(a []int, lo, hi int) { if lo >= hi { return } p := partition(a, lo, hi) quickSort(a, lo, p-1) quickSort(a, p+1, hi) } func quickSort_go(a []int, lo, hi int, done chan struct{}, depth int) { if lo >= hi { done <- struct{}{} return } depth-- p := partition(a, lo, hi) if depth > 0 { childDone := make(chan struct{}, 2) go quickSort_go(a, lo, p-1, childDone, depth) go quickSort_go(a, p+1, hi, childDone, depth) <-childDone <-childDone } else { quickSort(a, lo, p-1) quickSort(a, p+1, hi) } done <- struct{}{} } func main() { rand.Seed(time.Now().UnixNano()) testData1, testData2, testData3 := make([]int, 0, 100000000), make([]int, 0, 100000000), make([]int, 0, 100000000) times := 100000000 for i := 0; i < times; i++ { val := rand.Intn(20000000) testData1 = append(testData1, val) testData2 = append(testData2, val) testData3 = append(testData3, val) } start := time.Now() quickSort(testData1, 0, len(testData1)-1) fmt.Println("single goroutine: ", time.Now().Sub(start)) if !sort.IntsAreSorted(testData1) { fmt.Println("wrong quick_sort implementation") } done := make(chan struct{}) start = time.Now() go quickSort_go(testData2, 0, len(testData2)-1, done, 5) <-done fmt.Println("multiple goroutine: ", time.Now().Sub(start)) if !sort.IntsAreSorted(testData2) { fmt.Println("wrong quickSort_go implementation") } start = time.Now() sort.Ints(testData3) fmt.Println("std lib: ", time.Now().Sub(start)) if !sort.IntsAreSorted(testData3) { fmt.Println("wrong std lib implementation") } }
[1]: https://colobu.com/2018/06/26/implement-quick-sort-in-golang/
本文标题:golang 实现的快速排序
版权声明:本文使用「署名 4.0 国际」创作共享协议,转载或使用请遵守署名协议。