golang实现快速排序

快速排序的原理就不介绍了。在网上看到一个有趣的视频，大家可以看看，非常详细且有趣。
快速排序视频
代码：https://play.golang.org/p/Fw5gtzrPj0

package main

import (
    "fmt"
)

func main() {
    var sortArray = []int{3,41,24,76,11,45,3,64,21,69,19,36}
    fmt.Println(sortArray)
    qsort(sortArray,len(sortArray)-1)
    fmt.Println(sortArray)
}

func qsort(array []int,low,high int) {
    if low < high {
        m := partition(array,high)
        // fmt.Println(m)
        qsort(array,m-1)
        qsort(array,m+1,high)
    }
}

func partition(array []int,high int) int {
    key := array[low]
    tmpLow := low
    tmpHigh := high
    for {
        //查找小于等于key的元素，该元素的位置一定是tmpLow到high之间，因为array[tmpLow]及左边元素小于等于key，不会越界
        for array[tmpHigh] > key {
            tmpHigh--
        }
        //找到大于key的元素，该元素的位置一定是low到tmpHigh+1之间。因为array[tmpHigh+1]必定大于key
        for array[tmpLow] <= key && tmpLow < tmpHigh {
            tmpLow++
        }

        if tmpLow >= tmpHigh {
            break
        }
        // swap(array[tmpLow],array[tmpHigh])
        array[tmpLow],array[tmpHigh] = array[tmpHigh],array[tmpLow]
        fmt.Println(array)
    }
    array[tmpLow],array[low] = array[low],array[tmpLow]
    return tmpLow
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!