Go实现的三向切分快排

这几天在学Golang,然后就用Golang撸了一个三向切分的快排,感觉Golang的语法还是比较简单的

代码

package main

import (
    "fmt"
    "math/rand"
)

func qsort(a []int, le int, ri int) {
    if le >= ri {
        return
    }
    lt, rt, i := le, ri, le + 1
    v := a[le]
    for i <= rt {
        cmp := a[i] - v
        if cmp < 0 {
            a[lt], a[i] = a[i], a[lt]
            lt++
            i++
        } else if cmp > 0 {
            a[i], a[rt] = a[rt], a[i]
            rt--
        } else {
            i++
        }
    }
    qsort(a, le, lt - 1)
    qsort(a, rt + 1, ri)

}
func Qsort(a []int) {
    qsort(a, 0, len(a) - 1)
}

func isSorted(a []int) {
    for i := 0; i < len(a) - 2; i++ {
        if a[i] > a[i + 1] {
            fmt.Println("is not sorted")
            return
        }
    }
    fmt.Println("is sorted")
}

func main() {
    d := make([]int, 20000)
    for i := 0; i < 20000; i++ {
        d[i] = rand.Int()
    }
    isSorted(d)
    Qsort(d)
    isSorted(d)
}
文章目录
  1. 1. 代码