蓝色域界

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/