golang 实现的快速排序

文章目录 (?) [+]

    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 实现的快速排序
    本文链接:https://lanseyujie.com/post/implement-quick-sort-in-golang.html
    版权声明:本文使用「署名 4.0 国际」创作共享协议,转载或使用请遵守署名协议。
    点赞 0 分享 0