专栏首页信安本原算法之排序(中)

算法之排序(中)

上一篇文章说了时间复杂度为O(n2)的冒泡、插入和选择三个排序方式,它们只适合在数据规模比较小的时候,接下来要说的是两个时间复杂度为O(nlogn)的算法,归并排序快速排序,它们比较适合在大规模数据的时候使用,相比于前面的三个算法就更加常用。


首先来看归并排序(Merge Sort)

归并排序的操作还是比较简单的,它是将数组从中间分割为前后两部分,然后再将每一部分分割,直到分割到不能分为止,然后将数值两两排序合并,不断合并到最初的数组,就完成了排序的操作,它的示例图是这样的

归并排序使用的是分治思想,分而治之,也就是将大问题不断的分解,分解成一个个小问题,小问题都解决了,那大问题也就都解决了,这个跟前面说的递归是特别像的,分治是一种处理问题的思想,递归是具体的技巧,分治算法一般都是用递归来实现的。

既然是使用递归来实现的,那我们就要找到它的通用递归公式和递归终止条件,首先我们假设第一个数值用p表示,最后一个数值用r表示,既然要将数组从中间分割,那每次分割的下标就为q=(p+r)/2,即数组就分为了两段(p,q)和(q+1,r)。

那递归终止条件又该怎么定义?我们来看什么时候是我们需要截至的,当数组分解成单个字符的时候就停止了,那这个时候开始结束符号将一致,所以只需要在p>=r时结束就可以了。

分解结束之后就需要返回进行合并了,这个时候我们可以使用两个变量来帮助我们进行识别,这里用i和j两个变量来进行说明,将i和j分别指向(p,q)和(q+1,r)的第一个元素,同时比较这两个元素的大小,如果ai<aj,就将ai放到一个临时数组中,并将i后移一位;否则就将aj放到临时数组中,并将j后移一位,最后将临时数组拷贝回我们的数组就完成了排序操作。

说了这么多理解起来也比较困难,有一句话就很符合现在的情况,Talk is cheap. Show me the code( 不要多BB,放码过来吧 ),代码在后一片文章在给出来。

那归并排序是不是原地排序算法呢,由于归并排序在每次合并数据的时候都需要额外申请一个空间来存放,在合并完成之后将会被释放掉,并且在任意时刻,CPU只会有一个函数在执行,也就只有一个临时的内存空间在使用,临时空间最大也超不过数据总和n,所以空间复杂度为O(n),不是一个原地排序算法

在合并过程中,如果(p,q)、(q+1,r)中存在相同的元素,那我们就可以先把(p,q)中的元素先放入到临时空间中,所以归并排序是一个稳定的排序算法


接下来,我们来看快速排序(Quicksort),简称“快排”,它也是利用分治思想,虽然看起来跟归并排序有点像,但是它们的思路是完全不一样的。

快速排序是在p到r中任意选择一个pivot(分区点),然后遍历p到r的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,这样就将数组分成了三个区域,p到q-1是小于 pivot 的,q+1到r是大于 pivot 的,中间q是 pivot 。

然后不断的分治,直到区间缩小为1,所以它的递归终止条件也是p>=r。

在选取 pivot 的时候,一般选择最后一个数值,选择中间的数值作为 pivot 后,还需要将它移动到头或尾的位置,如果我们在进行分区的时候,不考虑空间大小的因素的话,分区操作其实是非常好写的,每一次分区都新申请两个空间,将小于 pivot 的放到一个空间,将大于 pivot 的放到另一个空间,然后再将两个空间合起来拷贝回前面的数组空间,这样的话快排就不是原地排序算法了,所以我们采取另外一种比较巧妙的办法。

这个操作有点类似上一篇文章中的选择排序,我们通过一个变量i,把数组分为前后两个区域,用选择排序中的叫法,前面是已排序区间,后面是未排序区间,我们每次都将未排序区间中的一个数值与 pivot 进行比较,如果小于 pivot 就将它放到已排序区间的末尾,也就是变量i所指向的位置,这个时候我们采取数组中用到的数据交换的方式,将需要调动的数据与i所指位置交换,这样涉及到的操作也就仅仅是数值交换的问题了,空间复杂度也就变成了O(1),快速排序也就是一个原地排序算法了。

同时也因为其中直接使用了数据交换的方式,他也就改变了数据原来的顺序,也就不是一个稳定的排序算法了。


那快速排序和归并排序的区别到底在哪里,它们在于归并排序是自下而上的,先处理子问题,然后再合并;快速排序是自上而下的,先分区,然后再处理子问题。


参考文档

极客时间-数据结构与算法之美

本文分享自微信公众号 - 无心的梦呓(wuxinmengyi),作者:Vesel无心

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

原始发表时间:2020-02-05

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法之排序(下)

    前面两篇文章说了时间复杂度为O(n2)的冒泡排序、插入排序和选择排序;也说了时间复杂度为O(nlogn)的归并排序和快速排序;这次来说一下时间复杂度为O(n)的...

    信安本原
  • 算法之排序(上)

    排序算法有很多种,甚至有很多都完全没有听过,我们最常见,也最经典的就是:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

    信安本原
  • 算法之排序(中)-c语言实现

    上一篇文章里说了归并排序和快速排序,它们的代码实现是非常相似的,只要理解了其中的具体实现,还是比较容易写出代码的。

    信安本原
  • 【技术分享】一:搜索排序—概述

    搜索排序:在一次会话中,用户在交互界面输入需要查询的query,系统给返回其排好序的doc例表的过程。

    腾讯智能钛AI开发者
  • 什么是基数排序?

    老读者可能比较熟悉,刚开始的时候写了一个排序算法系列,把常见的排序算法都写了,有兴趣的可以在公众号内的目录菜单栏中选择数据结构与算法查看。

    用户1260737
  • 10.4 选择排序

    1、一趟简单选择排序的操作为:通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录交换之。

    闫小林
  • 《十大经典排序算法》简介

    十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的...

    搜云库
  • 排序在数据分析中有多重要?

    说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有...

    CDA数据分析师
  • 排序算法系列

    概述 概念 排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 排序分为内部排序和外部排序。 若整个排序过程不需要访问...

    静默虚空
  • 十大经典排序算法的 JavaScript 实现

    https://segmentfault.com/a/1190000009332932

    前端博客 : alili.tech

扫码关注云+社区

领取腾讯云代金券