golang 之快速排序

威尔we 等级 439 0 0

1、快速排序稳定性

快速排序是不稳定的算法,它不满足稳定算法的定义。

算法稳定性 -- 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!

2、快速排序时间复杂度

快速排序的时间复杂度在最坏情况下是O(N²),平均的时间复杂度是O(N*lgN)。

这句话很好理解:假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N),需要遍历多少次呢?至少lg(N+1)次,最多N次。

(01) 为什么最少是lg(N+1)次?快速排序是采用的分治法进行遍历的,我们将它看作一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(N+1)。因此,快速排序的遍历次数最少是lg(N+1)次。

(02) 为什么最多是N次?这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是N。因此,快读排序的遍历次数最多是N次。

3、示例

// golang
func quickSort(arr []int, start, end int) {
    if start < end {
        i, j := start, end
        key := arr[(start+end)/2]
        for i <= j {
            for arr[i] < key {
                i++
            }
            for arr[j] > key {
                j--
            }
            if i <= j {
                arr[i], arr[j] = arr[j], arr[i]
                i++
                j--
            }
        }

        if start < j {
            quickSort(arr, start, j)
        }
        if end > i {
            quickSort(arr, i, end)
        }
    }
}

4、算法流程分析

快速排序(Quick Sort)使用分治法策略。

它的基本思想是:选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分;其中一部分的所有数据都比另外一部分的所有数据都要小。然后,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序流程:

  1. 从数列中挑出一个基准值。
  2. 将所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边);在这个分区退出之后,该基准就处于数列的中间位置。
  3. 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

下面以数列a={30,40,60,10,20,50}为例,演示它的快速排序过程(如下图)。

golang 之快速排序

上图只是给出了第1趟快速排序的流程。在第1趟中,设置x=a[i],即x=30。

(01) 从"右 --> 左"查找小于x的数:找到满足条件的数a[j]=20,此时j=4;然后将a[j]赋值a[i],此时i=0;接着从左往右遍历。

(02) 从"左 --> 右"查找大于x的数:找到满足条件的数a[i]=40,此时i=1;然后将a[i]赋值a[j],此时j=4;接着从右往左遍历。

(03) 从"右 --> 左"查找小于x的数:找到满足条件的数a[j]=10,此时j=3;然后将a[j]赋值a[i],此时i=1;接着从左往右遍历。

(04) 从"左 --> 右"查找大于x的数:找到满足条件的数a[i]=60,此时i=2;然后将a[i]赋值a[j],此时j=3;接着从右往左遍历。

(05) 从"右 --> 左"查找小于x的数:没有找到满足条件的数。当i>=j时,停止查找;然后将x赋值给a[i]。此趟遍历结束!

按照同样的方法,对子数列进行递归遍历。最后得到有序数组!

收藏
评论区

相关推荐

关于Golang的那些事(一) -- Node.js和Golang对比
之前一直用Node.js作为开发语言,用了差不多4年的Node.js,涉及前端和后端,最近看到Golang这个新兴之秀挺火的,于是想探究探究一下这门语言,对比了一下他们的Github repo,截止现在Node.js的repo有72.5K星, issue数量是859个,Golang的repo有75.7K星,issue数量是5K个。从趋势来看,Golang来势
golang 中神奇的 slice
声明:本文仅限于简书发布,其他第三方网站均为盗版,原文地址: golang 中神奇的 slice(https://links.jianshu.com/go?tohttps%3A%2F%2Fliqiang.io%2Fpost%2Fimagesliceingolang) 在 golang 中,似乎人们都不太喜欢使用 Linked List,甚至于原
godoc 命令和 golang 代码文档管理
介绍 godoc 是 golang 自带的文档查看器,更多的提供部署服务 go doc 和 godoc 在 golang 1.13 被移除了,可以自行安装 golang.org go1.13 godoc(https://links.jianshu.com/go?tohttps%3A%2F%2Fgolang.org%2Fdoc%2Fg
Mac安装Golang和vscode
Mac第一次安装golang和vscode一起使用,遇到了不少的坑,下面介绍一下正确的安装方式。 1、使用brew安装Golang 如果不知道brew是什么,或怎么安装请看这里 brew官网(https://brew.sh/index_zhcn) brew install golang 安装完成后可以使用
【Golang】GoWeb框架之Gin-简明教程
Gin 简介 Gin is a HTTP web framework written in Go (Golang). It features a
Golang中常用的字符串操作
Golang中常用的字符串操作 一、标准库相关的Package go import( "strings" ) 二、常用字符串操作 1. 判断是否为空字符串 1.1 使用“”进行判断 思路:直接判断是否等于""空字符串,由于Golang中字符串不能为 nil,且为值类型,所以直接与空字符串比较即可。 举例: go
Golang精编100题-搞定golang面试
Golang精编100题 能力模型 | 级别 | 模型 | | | | | 初级 primary | 熟悉基本语法,能够看懂代码的意图; 在他人指导下能够完成用户故事的开发,编写的代码符合CleanCode规范; | | 中级 intermediate | 能够独立完成用户故事的开发和
golang 分析调试高阶技巧
layout: post title: “golang 调试高阶技巧” date: 2020603 1:44:09 0800 categories: golang GC 垃圾回收 golang 高阶调试 Golang tools nm compile
深入理解 Go Slice
(https://imghelloworld.osscnbeijing.aliyuncs.com/0ce8a8773a658d4b843e5796a0dbf001.png) image 原文地址:深入理解 Go Slice(https://github.com/EDDYCJY/blog/blob/master/golang/pkg/20
golang包循环引用的几种解决方案
golang包循环引用的几种解决方案 发表于2020年11月2日2020年11月3日(https://libuba.com/2020/11/02/golang%e5%8c%85%e5%be%aa%e7%8e%af%e5%bc%95%e7%94%a8%e7%9a%84%e5%87%a0%e7%a7%8d%e8%a7%
Golang如何解析post请求中的json字符串
目录问题解决 问题使用Golang开发服务器,最常用的使用场景之一就是处理各种http请求。那么我们如何使用Golang解析Post请求中的Json字符串呢?今天我们就来通过一个实例了解一下。 解决首先,我们需要定义好对应的消息结构,也就是前端请求服务器的API接口。定义接口的话推荐使用工具YAPI编写,支持预
GO开发[一]:golang语言初探
一.Golang的安装 1.https://dl.gocn.io/ (国内下载地址) (https://imghelloworld.osscnbeijing.aliyuncs.com/658c5d13c377
golang 之快速排序
1、快速排序稳定性 快速排序是不稳定的算法,它不满足稳定算法的定义。 算法稳定性 假设在数列中存在aiaj,若在排序之前,ai在aj前面;并且排序之后,ai仍然在aj前面。则这个排序算法是稳定的! 2、快速排序
golang - DES加密ECB(模式)
Java默认DES算法使用DES/ECB/PKCS5Padding,而golang认为这种方式是不安全的,所以故意没有提供这种加密方式,那如果我们还是要用到怎么办?下面贴上golang版的DES ECB加密解密代码(默认对密文做了base64处理)。
聊聊golang的DDD项目结构
序本文主要研究一下golang的DDD项目结构interfacesfoodappserver/interfacesinterfaces git:(master) tree.|____fileupload| |____fileformat.go| |____fileupload.go|____food_handler.go|__