专栏首页网管叨bi叨图解算法基础--快速排序,附 Go 代码实现

图解算法基础--快速排序,附 Go 代码实现

很多面试题的解答都是以排序为基础的,如果我们写出一个 O(n^2 ) 的算法,大概率要被挂,今天写个快排的基础文章,后面看情况再把归并和堆排序写一写,至于选择排序、冒泡排序这种时间复杂度高的就不写了,有兴趣的可以找书自己看一下。

文中算法的实现是用 Go 写了一个比较简单的快速排序,方便大家理解(旁边画外音:其实是他好几年没面试了,太厉害的他也写不出来)。

关于更优秀的代码实现,可以在评论区里发出来一起学习,相信咱们读者里一定是卧虎藏龙,有不少算法大拿。

快速排序的思想

快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值之外的数分为 "比基准值小的数" 和 "比基准值大的数" 这两个类别,再将其排列成以下形式。

【比基准值小的数】 基准值 【比基准值大的数】

接着,继续对两个序列 "【】"中的数据进行排序之后,整体的排序便完成了。对基准值左右两侧的序列排序时,同样也会使用快速排序。

快速排序是一种"分治法",将原本的问题分解成两个子问题—— 比基准值小的数和比基准值大的数,然后再分别解决这两个子问题。解决子问题的时候会再次使用快速排序,只有在子问题里只剩下一个数字的时候,排序才算完成。

快排的过程

下面我们用示意图更好地理解一下快速排序对一个序列进行排序的过程。

图例出自—《我的第一本算法书》

假定有如下待排序序列

待排序序列

首先在序列中随机选择一个基准值,这里选择了 4。

选择基准值 pivot

将其他数字和基准值进行比较,小于基准值的往左移,大于基准值的往右移。

首先比较第一个元素 3 和基准值4,因为 3 < 4, 所以将 3放在基准值的左边。

首先比较 3 和基准值4,因为 3 < 4, 所以将 3放在基准值的左边

接下来,比较 5 和基准值,因为 5 > 4,所以将 5 放在基准值的右边。

5 > 4, 将5放在基准值右边

对整个序列进行同样操作后,所有小于基准值的数字全都放到了基准值的左边,大于的则全都放在了右边。

一轮排序完成后的结果

把基准值放入序列

现在排序就分成了两个子问题,分别再对基准值左边和右边的数据进行排序。

分解成了两个子问题

两边的排序操作也和前面的一样,也是使用快排算法,选取基准值,把小于的数字放左边大于的放右边。

对子序列使用快速排序

子问题有可能会再分解成子问题,直到子问题里只剩下一个数字,再也无法分解出子问题的时候,整个序列的排序才算完成。

排序完成

因为快速排序算法在对序列进行排序的过程中会再次使用该算法,所以快速排序算法在实现时需要使用"递归”来实现。

快速排序的Go代码实现

下面上一个用 Go 版本的快速排序算法的简单实现


func quickSort(sequence []int, low int, high int) {
 if high <= low {
  return
 }
 j := partition(sequence, low, high)
 quickSort(sequence, low, j-1)
 quickSort(sequence, j+1, high)
}

// 进行快速排序中的一轮排序
func partition(sequence []int, low int, high int) int {
 i, j := low+1, high
 for {
  // 把头元素作为基准值 pivot
  for sequence[i] < sequence[low] {
   // i 坐标从前往后访问序列,如果位置上的值大于基准值,停下来。
   // 准备和 j 坐标访问到的小于基准值的值交换位置
   i++
   if i >= high {
    break
   }
  }
  for sequence[j] > sequence[low] {
   // j 坐标从后往前访问序列,如果位置上的值小于基准值,停下来。
   // 和 i 坐标指向的大于基准值的值交换位置
   j--
   if j <= low {
    break
   }
  }
  if i >= j {
   break
  }
  sequence[i], sequence[j] = sequence[j], sequence[i]
 }
 sequence[low], sequence[j] = sequence[j], sequence[low]

 return j
}

每一轮快速排序都会经历下面这几个步骤:

  1. 设置两个变量i、j,排序开始的时候:i=0,j=待排序序列长度 - 1。
  2. 以第一个数组元素作为基准值 pivot(也可以是最后一个元素,或者是随机的一个元素)。
  3. i 坐标从开始向后访问序列里的元素,即 i++,找到第一个大于 pivot 的位置 ,和 j 坐标访问到的小于基准值的值交换位置。
  4. j 坐标从末尾向前搜索,即j--,找到第一个小于 pivot 的位置,将i,j坐标上的值进行互换。
  5. 重复第3、4步,直到i=j,然后将 pivot 和 j 坐标上的值互换,完成一轮排序,小于 pivot 的值都放在了它的左边,大于的则放到了右边。

重复进行上面的过程,直到排序完成。最后我们可以生成一个随机数序列对上面的快速排序函数进行测试:

func main() {
 rand.Seed(time.Now().Unix())
 sequence := rand.Perm(34)
 fmt.Printf("sequence before sort: %v", sequence)
 quickSort(sequence, 0, len(sequence) - 1)
 fmt.Printf("sequence after sort: %v", sequence)
}

快速排序的时间复杂度

分割子序列时需要选择基准值,如果每次选择的基准值都能使得两个子序列的长度为原本的一半,那么快速排序的运行时间和归并排序的一样,都为 O(nlogn)。将序列对半分割 log2n 次之后,子序列里便只剩下一个数据,这时子序列的排序也就完成了。

因此,如果像下图这样一行行地展现根据基准值分割序列的过程,那么总共会有 log2n 行。

快排分解序列的次数

每行中每个数字都需要和基准值比较大小,因此每行所需的运行时间为 O(n)。由此可知,整体的时间复杂度为 O(nlogn)。

如果运气不好,每次都选择最小值作为基准值,那么每次都需要把其他数据移到基准值的右边,递归执行 n 行,运行时间也就成了 O(n^2 )。

所以真正应用的时候基准值的选取也比较讲究,比如以中位数做基准值:本轮排序序列的第一个、最后一个、中间位置三个数的中位数作为基准值进行排序。

今天的内容分享到这里就结束了,喜欢的话还请点赞、在看多多支持,关注不迷路。

- END -

文章分享自微信公众号:
网管叨bi叨

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:进击的网管
原始发表时间:2022-03-07
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • go排序算法快速实现

    Johns
  • 快速排序算法详细图解JAVA_实现快速排序

    有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。

    全栈程序员站长
  • go实现堆排序、快速排序、桶排序算法

    堆排序是利用堆这种数据结构而设计的一种排序算法。以大堆为例利用堆顶记录的是最大关键字这一特性,每一轮取堆顶元素放入有序区,就类似选择排序每一轮选择一个最大值放入...

    冬夜先生
  • 排序算法Java代码实现(五)—— 快速排序

    CherishTheYouth
  • 【Go数据结构与算法基础】快速排序

    另一种是取i,需要保证pivot不取arr[l],防止死循环,同时不可以使用 arr[(l+r)>>1]这种,得向上取整,例如:arr[(l+r+1)>>1]。

    公众号guangcity
  • 十张动图带你搞懂排序算法(附go实现代码)

    时间复杂度是指执行这个算法所需要的计算工作量,其复杂度反映了程序执行时间**「随输入规模增长而增长的量级」,在很大程度上能很好地反映出算法的优劣与否。一个算法花...

    Golang梦工厂
  • 排序算法 | 快速排序(含C++/Python代码实现)

    排序算法,就是使得序列按照一定要求排列的方法。排序算法有很多,本文将介绍面试中常常被问到的经典排序算法:快速排序,并分别利用C++和Python进行实现。

    Amusi
  • 算法 | 快速搞定八种排序算法与代码实现

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    田维常
  • PHP快速排序算法实现的原理及代码详解

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

    砸漏
  • php计数排序算法的实现代码(附四个实例代码)

    计数排序只适合使用在键的变化不大于元素总数的情况下。它通常用作另一种排序算法(基数排序)的子程序,这样可以有效地处理更大的键。

    砸漏
  • 深入解析快速排序算法的原理及其Go语言版实现

    快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

    李海彬
  • php 二维数组快速排序算法的实现代码

    php 二维数组快速排序算法的实现代码 二维数组排序算法与一维数组排序算法基本理论都是一样,都是通过比较把小的值放在左变的数组里,大的值放在右边的数组里在分别递...

    用户2323866
  • <算法入门>快速理解7种排序算法 | python3实现(附源码)学习难度:桶排序(简化版)冒泡排序选择排序插入排序快速排序(面试常用算法)归并排序(先分后和, 分而治之)希尔排序

    算法是程序的灵魂,而排序算法 是算法的入门经典,作者在此用python亲自实现了7种主流的排序算法,并做简短的说明. ? 排序算法 学习难度: 桶排序 < 冒泡...

    zhaoolee
  • 《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

    billyang916
  • 这里有 300 篇 Python 与机器学习类原创笔记

    主要包括计算机科学中基本的算法与数据结构,结合算法思想和Leetcode实战,总结介绍。

    好好学java
  • 【机器学习入门】机器学习基础核心算法:贝叶斯分类!(附西瓜书案例及代码实现)

    寄语:首先,简单介绍了生成模型和判别模型,对条件概率、先验概率和后验概率进行了总结;其次,对朴素贝叶斯的原理及公式推导做了详细解读;再次,对三种可能遇到的问题进...

    黄博的机器学习圈子
  • 太赞了!机器学习基础核心算法:贝叶斯分类!(附西瓜书案例及代码实现)

    寄语:首先,简单介绍了生成模型和判别模型,对条件概率、先验概率和后验概率进行了总结;其次,对朴素贝叶斯的原理及公式推导做了详细解读;再次,对三种可能遇到的问题进...

    Datawhale
  • 很多小伙伴问我推荐什么书籍和网课,这次把私藏很久的资料都贡献了(上)

    平时有不少读者朋友问,有没有学习书籍网上课程推荐?今天结合自己学习经历与身边几个朋友的经历总结了一份程序员相关的书籍和网课。

    C语言与CPP编程
  • 用 Go 学算法--归并排序

    今天继续基础排序算法的图解和Go 代码实现,上次我们分享了《用Go学算法--快速排序》,这次分享一个时间复杂度为*** 诶,时间复杂度多少先保密,文末会有分析。...

    KevinYan

扫码关注腾讯云开发者

领取腾讯云代金券