专栏首页刘望舒算法(二)初等排序前篇[插入和冒泡排序]

算法(二)初等排序前篇[插入和冒泡排序]

前言

排序是算法的基础,排序有很多种方法,有些方法实现起来很简单,但是效率较差,我们可以将这些排序的方法称之为初等排序。这篇文章我们就来学习初等排序中的插入排序和冒泡排序。

1.插入排序

插入排序比较容易想到,思路与打扑克时排列牌的顺序是类似的。比如我们左手拿牌,然后用右手将牌从左到右,从小到大来排序,这就需要我们把需要进行排列的牌抽出来放到合适的位置,并且不断的重复,直到牌的顺序排好,这个过程就可以理解为插入排序。

图解插入排序

插入排序过程中会将需要排序的数组,分为两个部分:已排序部分和未排序部分,如下图所示。

从图中可以看出这个数组分为两个部分,其中下标为0、1、2的元素为已排列部分,其余的则为未排列部分。

插入的排序规则: 将开头元素视为以排序部分。接着执行如下的处理,直到没有未排序部分。 - 取出未排序部分的开头元素赋值给临时保存数据的变量v。 - 在已排列的部分将所有比v大的元素向后移动一个位置。 - 将取出的元素v插入空位。

按照这个规则,我们来举一个简单的例子。我们对数组 a={8,3,1,5,2,1} 进行从小到大排序,数组a如下图所示。

我们对数组a进行排序,共需要5个步骤: 1.接着我们将a[0]=8视为已排序,我们从a[1]开始操作,将a[1]的值3取出,3要小于a[0]的值8,因此将a[0]的值8移动到a[1],再把3插入到a[0],如下图所示。

2.a[2]的值1要比a[0]和a[1]的值要小,则将a[0]和a[1]顺次向后移一个位置,然后将1插入a[0],如下图所示。

3.将a[3]中的5拿出来,比它大的是a[2]的8,因此8向后移,将5插入a[3]。如下图所示。

4.将a[4]中2拿出来,发现a[1]、a[2]、a[3]中的值都比2大,因此将它们依次向后移,将2插入到a[1]中,如下图所示。

5.最后将a[5]中的1移到合适的位置,过程和上面一样,最后的排序结果如下图所示。

实现插入排序

接下来要实现插入排序,针对下图来定义变量。

如上图所示,i代表未排序部分的开头元素,v是临时保存a[i]值的变量, j代表已排序部分v要插入的位置。 根据定义的这三个变量,插入排序的实现思路就是:外层循环i从1开始自增,并在每次循环开始时将a[i]的值保存在v中;内层循环则是j从i-1开始向前自减,并将比v大的元素从a[j]移动到a[j+1],并将v插入到当前j+1的位置(内层循环后j会先自减1,因此插入的地方则是j+1的位置),当j等于-1或者a[j]小于等于v则内层循环结束。 接下来我们用代码来实现插入排序,如下所示。

其中负责打印数组的ArrayUtils类如下所示。

输出结果为: {8, 3, 1, 5, 2, 1} {1, 1, 2, 3, 5, 8}

插入排序的复杂度

根据算法(一)时间复杂度所讲的,我们来算一下插入排序的时间复杂度。在最坏的情况下,每个i循环都需要执行i次移动,总共需要1+2+......+n-1=n²/2+n/2,根据此前讲过的推导大O阶的规则的我们得出插入排序的时间复杂度为O(n²)。

2.冒泡排序

冒泡排序应该是开发者最容易理解的排序算法,它的基本思想就是每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。需要进行排序的元素则向水中的气泡一样慢慢的移向水面。

图解冒泡排序

与插入排序一样,需要进行冒泡排序的数组也分为已排序部分和未排序部分。 冒泡排序的规则为:从数组末尾开始依次比较相邻的两个元素,如果大小关系相反则交换位置,直到数组中不再有顺序相反的相邻元素。

我们对数组 a={5,3,2,4,1} 进行从小到大排序,排序过程如下所示。 第一轮排序:

我们将数组末尾的a[4]的值和a[3]的值进行对比,发现a[4]的值比a[3]的值小,则将它们交换,再接着对剩下的相邻的两个元素进行对比和交换,最终得到的结果为a={1,5,3,2,4},已排序的部分的元素为1。

第二轮排序:

首先对比a[3]和a[4]的值,发现a[3]的值比a[4]的值小,则不需要进行排序。最终得到的结果为a={1,2,5,3,4},已排序部分的元素为1、2。

第三轮排序:

经过第三轮排序,已排序部分的元素为1、2、3。

第四轮排序:

经过四轮排序我们最终得到的结果为a={1,2,3,4,5}

实现冒泡排序

实现插入排序时,我们要先定义两个变量,i为循环变量,表示未排序部分的开头元素,从数组开头向末尾移动。j也为循环变量,用于对未排序部分中相邻元素两两比较,从数组的末尾n-1开始减小到 i 结束(i=1)。

代码实现如下所示。

其中ArrayUtils的printArray方法此前讲过,这里就不再给出,打印结果为: {5, 3, 2, 4, 1} {1, 2, 3, 4, 5}

冒泡排序的复杂度

最坏的情况下,冒泡排序对未排序部分的相邻元素进行了(n-1)+(n-2)+(n-3)+……+1次比较,也就是n²/2+n/2次比较,根据推导大O阶的规则我们得出冒泡排序的时间复杂度为O(n²)。

本文分享自微信公众号 - 刘望舒(liuwangshuAndroid),作者:刘望舒

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

原始发表时间:2017-02-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法(三)初等排序后篇[选择和希尔排序]

    1.选择排序 根据上一篇文章讲到的插入排序和冒泡排序,我们把选择排序的数组也分为已排序部分和未排序部分。 图解选择排序 在用图来讲解选择排序之前,我们要先了...

    用户1269200
  • Java并发编程(四)Java内存模型

    相关文章 Java并发编程(一)线程定义、状态和属性 Java并发编程(二)同步 Java并发编程(三)volatile域 前言 此前我们讲到了线程、同步...

    用户1269200
  • Android网络编程(一)HTTP协议原理

    前言 这篇文章是这个系列的开篇,作为移动开发者,开发的应用不免会对网络进行访问,虽然现在已经有很多的开源库帮助我们可以轻而易举的访问网络,但是我们仍要去了解网络...

    用户1269200
  • 10.4 选择排序

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

    C语言入门到精通
  • 10.4 选择排序

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

    C语言入门到精通
  • 排序算法(九):桶排序

    桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中...

    zhipingChen
  • 经典排序算法详细介绍

    渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:

    IT茂茂
  • 不稳定的原地排序算法:选择排序

    在之前的文章中,我们说了两个原地排序算法:插入排序和冒泡排序。分析两个算法的原理,也用代码实现了两个算法。最后,我们也从两个算法入手,引出了评价算法性能的两个重...

    飞翔的竹蜻蜓
  • 十大经典排序算法动画,看我就够了!

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

    五分钟学算法
  • 八大排序算法

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

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券