专栏首页GoLang那点事排序-真的了解快速排序了吗,请解答下题

排序-真的了解快速排序了吗,请解答下题

题目

给出一个区间的集合,请合并所有重叠的区间。 示例:[[1,5],[2,7],[,10,18],[,17,19]] 结果:[[1,7],[10,19]] 为什么呢?[1,5] [2,7]有重叠3,4;[10,18],[17,19]有重叠17,18

我们分析上面的示例,其实比较的就是下一个区间起始值是否在上一个区间的范围内,依次比较,直到匹配失败,就把这个已经匹配过的最小值和最大值放入一个新的区间。

基于上面的思路,我们首先得保证区间是有序的(基于起始值的有序),所以先排序,这里我们学习一下快速排序算法。

快速排序

快速排序核心原理是经过一趟排序之后,使得这一组数据在某个值左边全是小于这个值的,在这个值的右边全是大于这个值的,然后递归排序左边的数组和右边数组,直到最后数组的大小是1,排序终止,如下图,

  • 第一次我们选取值为8的元素为中间值,经过一趟排序后,4的左边是7,2,右边是15
  • 第二次我们对左边元素7,2,右边元素15进行排序,选取的中间值分别是7,15
  • 第三次排序完成后,2,7有序,15只有一个元素,右边的数组终止排序
  • 第四次对2,7进行排序,2,7各只有一个元素,终止排序

结合上面的题目我们用代码实现快速排序

总结一下快速排序

快速排序是最常用的一种排序算法,在实际场景中也广泛用到,比如类库中(jdk类库,golang类库)其排序算法都有用到快速排序。

  • 快速排序使用了递归算法,每次分区之后,数组都会被切分成两个大小差不多相等的小区间,直到区间大小为1,这个过程需要log(n)次,每个区间进行排序需要遍历n(数组的结尾-开始)次,所以时间复杂度是nlog(n),极端情况下会退化成n2,例如[1,2,3,4,5],这种情况下,数组是有序的,假设我们选的分区值是1,每次分区后两个数组的大小差距太大(数组长度-2),,所以需要执行n次分区操作,那么时间复杂度会退化成n2。
  • 他是一种原地排序算法,不会占用多余的空间,排序过程中除了申请一些临时变量存储,并无其它任何内存开销,所以空间复杂度是O(1),
  • 他是一种不稳定的排序算法 ,因为在分区函数中会对数据元素做交换
  • 快速排序的核心思想是分区和分治,分区时分区的值选取也很关键,一般采用中位数

快速排序的平均时间复杂度是nlog(n),其退化到n2的概率是非常小的,我们也可以选取合适的中间值进行避免,但他的原地排序,分治思想是非常优秀的,所以他在实际场景中应用广泛。

再回到一开始的问题

我们对intervals二位数组按下标为0的元素进行了升序排序,我们按照上面的解题思路开始实现代码

本文分享自微信公众号 - GoLang那点事(aweiaichitudou),作者:那小子阿伟

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序-线性排序,如何做到百万级数据秒级排序,时间复杂度O(n)?

    我们经常接触的冒泡排序,快速排序,归并排序等,这些排序时间复杂度大多是n^2或者N(logN),他们都是基于比较的排序(就是排序过程中数据两两做比较),那你有知...

    阿伟
  • 排序-归并排序,一种外排序,递归,非递归,磁盘?

    归并排序是一种分治思想的应用,所以也适合处理大数量的排序,因此也是一种外排序算法,磁盘排序算法,应用场景也较多,比如mysql的排序,sharding-jdbc...

    阿伟
  • 微服务-高并发下接口如何做到优雅的限流

    通俗的来讲,一根管子往池塘注水,池塘底部有一个口子往外出水,当注水的速度过快时,池塘的水会溢出,此时,我们的做法换根小管子注水或者把注水管子的口堵住一半,这就是...

    阿伟
  • 排序概述

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    瑾诺学长
  • 10.1 内部排序

    1、排序(Sorting)时计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。

    C语言入门到精通
  • 写代码?程序猿?你不能不懂的八大排序算法的Python实现

    信息获取后通常需要进行处理,处理后的信息其目的是便于人们的应用。信息处理方法有多种,通常由数据的排序,查找,插入,删除等操作。本章介绍几种简单的数据排序算法和高...

    风骨散人Chiam
  • 两分钟真能搞懂桶排序

    在数据结构与算法的排序中,我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏,其实这个也没啥复杂的,算法的排序中,我...

    bigsai
  • 漫画:“排序算法” 大总结

    如果原始数组本来已经接近有序,只需要较少的比较交换次数即可完成排序。比如下面这个数组,只有7和8是逆序的:

    小灰
  • 排序算法总括-java版

    内部排序就是仅仅依赖于内存就可以进行的排序,比如有交换排序、插入排序、选择排序、归并排序、基数排序

    shengjk1
  • 算法之旅 | 冒泡排序法

    HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

    HTML5学堂

扫码关注云+社区

领取腾讯云代金券