Go 是这两年出来的一门语言。比较稚嫩,但还是可以一玩。 复习数据结构之余,顺手写个快速排序--用go实现。

package main

import "fmt"

type ElemType int

func main() {
    data := make([]ElemType, 600000) // ALL ZERO
    var i int = 0
    var dlen int = len(data)
    for i = 0; i < dlen; i++ {
        data[i] = (ElemType)(dlen - i - 1)
    }
    fmt.Println("Start ...", len(data))
    for i = 0; i < 100; i++ {
        fmt.Printf("%d ", data[i])
    }
    fmt.Println()
    QuickSort(data, 0, dlen-1)

    fmt.Println("End ...")
    for i = 0; i < 100; i++ {
        fmt.Printf("%d ", data[i])
    }
    fmt.Println()
}

func QuickSort(A []ElemType, low, high int) {
    if low < high {
        // Partition() is the operation of divide A[low ... high]
        // one to two arrays which can be used as QuickSort Again
        pivotpos := Partition(A, low, high)
        QuickSort(A, low, pivotpos-1)
        QuickSort(A, pivotpos+1, high)
    }
}

func Partition(A []ElemType, low, high int) int {
    var pivot ElemType = A[low]
    var tmp ElemType
    //Method I:
    //for low < high {
    //  for low < high && A[high] >= pivot { high-- ; }
    //  A[low] = A[high];
    //  for low < high && A[low] < pivot { low++; }
    //  A[high] = A[low];
    //}
    //end of MI

    //Method II:
    for (low < high) && (A[high] > pivot) {
        high--
    }
    for (low < high) && (A[low] < pivot) {
        low++
    }
    for low < high {
        // swap A[low] & A[high]
        tmp = A[low]
        A[low] = A[high]
        A[high] = tmp
        low++
        high--
    }
    //end of MII

    A[low] = pivot
    return low
}

执行输出如下:

[yu@argcandargv-com quicksort]$ go build quicksort.go 
[yu@argcandargv-com quicksort]$ ls
quicksort  quicksort.go
[yu@argcandargv-com quicksort]$ time ./quicksort
Start ... 600000
599999 599998 599997 599996 599995 599994 599993 599992 599991 599990 599989 599988 599987 599986 599985 599984 599983 599982 599981 599980 599979 599978 599977 599976 599975 599974 599973 599972 599971 599970 599969 599968 599967 599966 599965 599964 599963 599962 599961 599960 599959 599958 599957 599956 599955 599954 599953 599952 599951 599950 599949 599948 599947 599946 599945 599944 599943 599942 599941 599940 599939 599938 599937 599936 599935 599934 599933 599932 599931 599930 599929 599928 599927 599926 599925 599924 599923 599922 599921 599920 599919 599918 599917 599916 599915 599914 599913 599912 599911 599910 599909 599908 599907 599906 599905 599904 599903 599902 599901 599900 
End ...
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 

real    1m55.564s
user    1m55.215s
sys 0m0.052s
Categories: Code

Yu

Ideals are like the stars: we never reach them, but like the mariners of the sea, we chart our course by them.

8 Comments

二学长 · March 21, 2015 at 12:06

Google Chrome 41.0.2272.89 Google Chrome 41.0.2272.89 GNU/Linux x64 GNU/Linux x64

都写了,为什么不来个和C语言版的快速排序做个对比呢?哪个效率更高?

    yu · March 21, 2015 at 13:27

    Google Chrome 41.0.2272.89 Google Chrome 41.0.2272.89 Mac OS X  10.10.2 Mac OS X 10.10.2

    @二学长 当时玩了几天go然后随手找个东西试试手艺来着…

    yu · March 23, 2015 at 10:34

    Google Chrome 41.0.2272.89 Google Chrome 41.0.2272.89 Mac OS X  10.10.2 Mac OS X 10.10.2

    @二学长 有记录cookie的…
    嵌套样式略麻烦

    yu · June 12, 2015 at 18:16

    Google Chrome 43.0.2357.81 Google Chrome 43.0.2357.81 Mac OS X  10.10.3 Mac OS X 10.10.3

    @二学长 和C同样的代码相比,编译参数不加-O时间为4m2.828s和1m30.577s,加上-O3后为1m48.042s和0m37.186s.

    另外,我代码写屎了…系统的qsort秒出结果….

二学长 · March 23, 2015 at 10:39

Google Chrome 31.0.1650.63 Google Chrome 31.0.1650.63 GNU/Linux GNU/Linux

@yuik 用户体验不好,吐槽.

    yu · March 23, 2015 at 10:52

    Google Chrome 41.0.2272.89 Google Chrome 41.0.2272.89 Mac OS X  10.10.2 Mac OS X 10.10.2

    @二学长 回复从来不过百,没有动力….

    yu · March 23, 2015 at 10:53

    Google Chrome 41.0.2272.89 Google Chrome 41.0.2272.89 Mac OS X  10.10.2 Mac OS X 10.10.2

    @二学长 另外,想要@人,得评论框右上角reply才行,直接@这个高级功能我还没做…

      二学长 · June 12, 2015 at 18:19

      Google Chrome 31.0.1650.63 Google Chrome 31.0.1650.63 GNU/Linux GNU/Linux

      @yu 没做赶紧做啊!!!哈哈哈,提高用户体验.

Leave a Reply

Your email address will not be published. Required fields are marked *