快速排序 Go语言实现经典算法


快速排序原理

快速排序使用分治法(Divide and conquer)策略,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,最终整个数据变成有序序列。

效率

平均时间复杂度 O(nlogn)
最坏O(n^2)当划分不均匀时候 逆序and排好序都是最坏情况
最好O(n) 当划分均匀
空间复杂度O(logn)

稳定性

快速排序是不稳定排序

快速排序的Go语言实现代码

package main

import "fmt"
import "time"
import "math/rand"

func quickSort(numArr []int,start int, end int){
    if start >= end {
        return
    }
    mid := numArr[start]
    left,right := start+1,end
    for left < right{
        for numArr[left] > mid && left < right{
            left++
        }
        for numArr[right] <= mid && left < right{
            right--
        }
        numArr[left],numArr[right] = numArr[right],numArr[left]
    }
    if numArr[left] < mid{
        left--
    }
    numArr[start],numArr[left] = numArr[left],numArr[start]
    quickSort(numArr,start,left-1)
    quickSort(numArr,left+1,end)
}

// 快速排序
func main(){
    numArr := make([]int,9)

    rand.Seed(time.Now().UnixNano())
    for i := range numArr{
        numArr[i] = rand.Intn(100)
    }
    fmt.Println("排序前数组:",numArr)
    quickSort(numArr,0,8)
    fmt.Println("排序后数组:",numArr)
}

本文发表于2019年12月09日 14:56
阅读 212 讨论 0 喜欢 0

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

8022 3605572
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

人活一辈子,不是一年两年。时间是有连续性的,做抉择的时候要多看几步。保持警惕,大丈夫有所为,有所不为。

跟人接触,不要想:我能从你身上得到什么,要想:我能给你什么。 想通了,内核就稳了。

这个世界上,别人只会看你现在的样子而不是以后的样子。你以后的样子只有自己才相信。如果没有执行力,一切都是虚妄。

对普通人来说,人和人相处其实最重要的是感觉。感觉不好,你说什么都没用,怎么解释都没用,越说越错,反正最后不好的锅都往你身上扣。所谓“说你行你就行,不行也行。说你不行,你就不行,行也不行”就是这个意思。狼要吃人根本不需要理由,你也同样叫不醒装睡的人。遇到这种情况,早点闪人才是上策。不过大部分人的问题是没有闪人的心态,能力,和资源。

考985不牛逼,考上才牛逼。创业不牛逼,创业成功才牛逼。这个社会上很多人把目标当成牛逼的资本,牛逼哄哄的,死活不听劝,然后做的一塌糊涂,给别人添麻烦,让别人帮他料理后事,对此只能呵呵。

当你尝到用生气解决问题的甜头后,你就懒得再用其他方式了。你却忽略了,生气是鸩毒啊,剂量用够了,你的关系也玩完了。

年轻的时候你只搞事业不谈恋爱,等你事业有成了,钱相对自由了,你可能已经没有荷尔蒙了。

如果你经常雇佣比你矮小的人,将来我们就会变成矮人国,变成一家侏儒公司。相反,如果你每次都雇用比你高大的人,日后我们必能成为一家巨人公司。

如果一个人有充裕的时间去完成一项工作,那么他就会放慢节奏或者增加其他不必要的工作,直到花光所有的时间。

Copyright © 2016 - 2020 Cion.
All Rights Reserved.
备案:鲁ICP备19012333号-4.