Record

机会是留给有准备的人

另一种使用Go 实现快速排序与goroutine版

刚看了这篇文章使用 Go 实现快速排序,发现他的实现算法与我之前写的有点不一样 快速排序之golang实现

这篇文章的快速排序:

基准元素是从最后一个算,然后for循环从头开始跟基准元素比较,大的基准函数就往前移动,
直到一边小于基准元素,一边大于基准元素,再左右递归排序完成。

另一种快速排序:

以第一个为基准元素,然后用2个for循环从二边开始查找跟基准元素比较,先从右边找出小于基准元素的元素跟从左边找出大于基准元素 的元素进行交换,再左右递归排序完成。
经过测试发现从二边查找交换的速度稍快。

代码里面还通过goroutine实现:

其实goroutine只是在递归时用到,就是左右二边递归数据并不影响,就可以利用goroutine分别执行。经测试goroutine在大数据排序的情况下比没goroutine占优势,毕竟goroutine也有性能消耗。其实goroutine不是减少排序步骤,而是更好的利用cpu等资源

下面代码是套用他的goroutine改写的

    package main

    import (
        "fmt"
        "time"
    )

    func partition(arr []int,start ,end int)(p int)  {

        if start > end {
            return
        }

        i,j,temp := start,end ,arr[start]

        for i<j  {

            for i < j && arr[j] >temp  {
                j--
            }

            for i < j && arr[i] <= temp  {
                i++
            }

            if i < j {
                arr[i] ,arr[j] = arr[j],arr[i]
            }

        }

        arr[i],arr[start] = arr[start],arr[i]

        return i

    }


    func quickSort3(a []int, lo, hi int) {
        if lo >= hi {
            return
        }
        p := partition(a, lo, hi)
        quickSort3(a, lo, p-1)
        quickSort3(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 {
            quickSort3(a, lo, p-1)
            quickSort3(a, p+1, hi)
        }
        done <- struct{}{}
    }

    func main()  {

        testData2 := []int{3, 7, 4, 1, 5, 9, 2, 6,8}
        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))

    }