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

算法之排序(上)

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

按照时间复杂度来进行划分可以将其划分为三类

•O(n2) :冒泡、插入、选择;基于比较•O(nlogn):快排、归并;基于比较•O(n):桶、计数、基数;不基于比较

这次我们来说时间复杂度为O(n2)的

在说具体的排序方法之前,先明确排序算法的评价标准

首先是排序算法的执行效率,执行效率一般从最好、最坏、平均时间复杂度上分析,其分析时间复杂度时需要考虑系数、常数和低阶,因为时间复杂度是在数据规模特别大的时候的增长趋势,在平时的代码中,数量级都是比较小的,所以还需要考虑这些问题。在基于比较的排序算法中,数值比较的次数和数据的移动次数也都是需要考虑进去的。

其次是内存的消耗,算法的内存消耗可以用空间复杂度来表示,当空间复杂度为O(1)的算法也可以称之为原地排序算法。

最后是算法的稳定性,当一组数据中有两个相同的值时,排序之后两个值的顺序是如果没有交换那它就是具有稳定性的算法。

然后我们再引入两个概念,有序度逆序度

有序度是数组中具有有序关系的元素对的个数。

比如说2、4、3、1、5、6这组数组的有序度是11,因为它有11个有序元素对,分别是(2,4)、(2,3)、(2,5) (2,6)、(4,5)、(4,6)、(3,5)、(3,6)、(1,5)、(1,6)、(5,6)。

对于6、5、4、3、2、1这组数据,它的有序度是0;对于1、2、3、4、5、6这组数据来说,它的有序度是n*(n-1)/2,这种完全有序的数组的有序度叫做满有序度。

所以逆序度也就等于满有序度-有序度,排序的过程就是增加有序度,减少逆序度的过程,最后到达满有序度,排序就结束了。


冒泡排序是依次对两个相邻的值进行比较,如果满足要求的大小关系,就继续往后看,如果不满足就将它们两个互换位置。每一次冒泡都最起码会交换一个值 ,所以最多执行n次就可以完成排序操作。

如果一组数据为4、5、6、3、2、1,要求其从小到大排序,那它进行第一次冒泡排序的过程就是这样的

这个时候,最大的数字6,就已经排在了正确的位置上,后续的冒泡操作依次是这样的

这种情况是刚好用了n次,如果代码直接写成循环n次的话,就可能会有多余的判断流程,如果排列顺序刚好为1、2、3、4、6、5的话,就只需要一次就可以完成排序操作,所以我们可以将每次有无数据交换的操作来作为有无完成排序的条件。

首先冒泡排序只交换相邻两个数据,所以空间复杂度为O(1),是原地排序算法。

在冒泡排序中,我们可以规定它在两个数值相等的时候不进行交换,就可以保证排序前后相同的数值先后顺序不变,所以它是一个稳定的排序算法。


在数组中,我们在中间插入一个数据的时候,是把相应位置的数据都往后挪一位,同时还可以保证顺序不变,同样的方法放到算法中,就有了插入排序

首先是将数据分为两个区间,已排序区间未排序区间,开始的时候,已排序区间只有一个元素,然后在未排序区间中取一个元素,在已排序区间中寻找对应的位置将其插入,不断重复直到未排序区间的数据为空。

比如要将4、5、6、1、3、2这组数据进行排序,那过程就是这样的

插入排序与冒泡排序一样,有比较和移动两个操作,循环比较得到要插入的位置,然后将后面的元素往后挪一位。

对于不同的查找插入点方法,不管是从头到尾,还是从尾到头,元素的比较次数是有区别的。但对于一个给定的初始序列,移动操作的次数总是固定的,就等于逆序度。

还是拿刚刚的例子说,满有序度是n*(n-1)/2=15,初始序列的有序度是5,所以逆序度是10。

在插入排序的时候,我们并不需要额外的空间,所以空间复杂度是O(1),所以它是一个原地排序算法。

因为在插入的时候,我们可以让未排序区间的元素排在已排序区间中相同元素的后面,所以它也是一个稳定的排序算法。


选择排序和插入排序比较类似,也有已排序区间和未排序区间,但是初始的时候是不对其进行区分的,选择排序每次都会在未排序区间中选择最小的一个数,将它放到已排序区间的末尾,如果没有已排序区间就将其放到未排序区间的前面。

首先选择排序也不需要申请多余的内存空间,空间复杂度为O(1),是原地排序算法。

由于它将数值与前面的数值进行交换,这样将会破坏它的稳定性,所以它是一个不稳定的排序算法。


相比之下,选择排序比冒泡排序和插入排序稍微逊色一点,拿冒泡排序和插入排序相比呢,从代码上看的话,冒泡排序进行数据交换是需要有第三个变量来做交换的,有三个赋值语句,而插入排序只需要一个赋值语句即可完成赋值操作,所以插入排序比冒泡排序性能更好一点。

参考文档

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

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法之排序(下)

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

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

    上一篇文章说了时间复杂度为O(n2)的冒泡、插入和选择三个排序方式,它们只适合在数据规模比较小的时候,接下来要说的是两个时间复杂度为O(nlogn)的算法,归并...

    信安本原
  • 算法之二分查找(上)

    二分查找在平时的生活中也挺常用的,比如说以前玩的猜数游戏,每次都取中间数,然后得知是大了,还是小了,这个例子也就是二分查找。

    信安本原
  • 数据结构与算法学习笔记之如何分析一个排序算法?

    现在IT这块找工作,不会几个算法都不好意思出门,排序算法恰巧是其中最简单的,我接触的第一个算法就是它,但是你知道怎么分析一个排序算法么?有很多时间复杂度相同的排...

    Dawnzhang
  • 如何优雅地给扑克牌排序?(一)——排序算法的数学本质

    不知平常各位打牌时候是否遇到过这样的场景:四人打完升级后,面对两幅混乱的扑克牌,走了一人后想打斗地主,现在要把他们分出一副来,于是打算先排序后分离,然后各种花色...

    magic2728
  • 10.1 内部排序

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

    闫小林
  • 两分钟真能搞懂桶排序

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

    bigsai
  • 桶排序/基数排序(Radix Sort)

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要...

    瑾诺学长
  • 排序概述

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

    瑾诺学长

扫码关注云+社区

领取腾讯云代金券