《算法基础:打开算法之门》一3.3 插入排序

3.3 插入排序

尽管插入排序和选择排序有些相似,但它们还是有点不同。在选择排序中,当我们决定要把哪本书放在第i个位置上时,35当下前i个位置的书是书架中所有书按照作者姓名排序的前i本书。插入排序中,前i个位置的书仍然是初始时刻在前i个位置的书,但现在是按照作者名字顺序对这i本书进行了重排操作。

例如,假设放在前4个位置的书已经按照作者名字排好序了,并且按照顺序,它们分别是Charles Dickens、Herman Melville、Jonathan Swift和Leo Tolstoy所写的书。现在第5个位置处的书是Sir Walter Scott写的。通过插入排序,我们将Swift和Tolstoy所写的书分别向右移动一个位置,将它们分别从第3个位置和第4个位置移动到第4个位置和第5个位置,然后我们把由Scott所写的书放置到空出的第3个位置。此时当我们操作由Scott所写的书时,我们并不关心位于它右侧的是哪本书籍(下图中显示的是由Jack London和Gustave Flaubert所写的书),我们随后再处理它们。

为了移动Swift和Tolstoy所写的书,首先比较Tolstoy和Scott这两个作者名字。我们发现Tolstoy排在Scott之后,因此将Tolstoy所写的书向右移动一个位置,从第4个位置移动到第5个位置。然后比较Swift和Scott这两个作者名字。我们发现Swift排在Scott之后,因此将Swift所写的书向右移动一个位置,从第3个位置移动到第4个位置,其中第4个位置就是当我们移动Tolstoy时所空出的位置。下一步比较Herman Melville和Scott这两个作者名字。这时,我们发现Melville并没有排在Scott之后。因而不再比较作者名字,因为我们已经发现由Scott所写的书应该排在Melville所写的书的右侧和Swift所写的书的左侧。我们把Scott所写的书放在第3个位置处,也就是当我们移动Swift所写的书时所空出的位置。

为了将这一观点转化为插入排序中对一个数组的排序,子数组A[1i-1]是初始时位于数组的前i-1个位置的元素,但是此时它们被重新排序了。为了判定原来在A[i]中存放的元素现在的位置,36插入排序依次与A[1i-1]中的所有元素进行比较,首先与A[i-1]比较,之后依次向左移动,使每个比当前A[i]元素大的元素向右移动一个位置。一旦找到了一个不大于A[i]的元素或者已经到达了数组的最左端,那么我们将初始时在A[i]中的元素调换到数组当前的新位置上。

第1B步中的判定条件依赖于短路的(short circuiting)“与”运算符:如果表达式左侧部分(即j>0)为假,那么它就不会再判定表达式右侧部分的真假。如果j≤0,程序又试图获取A[j]的值时,就会发生数组索引指向错误。下面我们使用在3.2节的选择排序例子里的数组来描述插入排序的执行过程:

同样地,最初的数组出现在左上侧,图中每一步显示了经过程序第1步中外部循环的一次迭代后得到的新数组。深灰色阴影标识的元素是已经排好序的子数组。针对外部循环的循环不变式(我们也不再证明)如下:在第1步循环的每次迭代开始时,子数组A[1i-1]包含初始元素A[1i-1],但此时是已经排好序的。下图表明当i等于4时,上述例子第1B步中的内部循环是如何工作的。我们假定子数组A[13]中包含初始在前3个位置的数组元素,37但现在它们是排好序的。为了确定原来在A[4]中的元素现在应该放置的位置,我们将它保存在一个名为key的变量中,然后将A[13]中比key值大的元素依次向右移动一个位置:

深灰色阴影位置表明元素应该移动到的位置。从最后一步可以看出,A[1]的值3并不比key的值7大,因此内部循环终止。正如最后一步得出的,key的值移动到了A[1]的右侧。当然,由于内部循环的第一次迭代会覆盖A[i],所以我们必须在第1A步中将初始时在A[i]中的值保存至key中。也有可能内部循环的终止是因为j>0不成立。这种情况会在key小于A[1i-1]的所有元素时发生。当j变成0时,A[1i-1]的每个元素均会右移1次,因此第1C步中key值放入A[1]中,这正好是我们想要放置的地方。分析插入排序(INSERTIONSORT)的运行时间,我们发现它比选择排序(SELECTIONSORT)更复杂。SELECTIONSORT程序的内层循环迭代次数仅仅取决于外层循环的索引i而并非元素自身的值。然而,对于INSERTIONSORT程序,内层循环的迭代次数取决于外层循环的索引i和数组元素值。当内层循环每次都执行0次迭代时,INSERTIONSORT会出现最好情况。对于每个i值,当第一次验证A[j]>key时就已经是错误的,此时便为最好情况。换句话说,每次执行第1B步时,一定有A[i-1]≤A[i]成立。这种情况在什么时候才会发生呢?当且仅当在程序开始时,数组A已经是有序的。在这种情况下,外层循环迭代n-1次,而外层循环的每次迭代均会花费常量时间,因此INSERTIONSORT会花费Θ(n)时间。当内层循环每次都执行最大次数时,会发生最坏情况。现在判定条件A[j]>key每次都为真,且循环一定终止于条件j>0被判定为假时。每个元素A[i]必须扫描比较到数组的最左侧。这种情况在什么时候才会发生呢?当数组A整体为逆序时,即非递增顺序。在这种情况下,外层循环每迭代一次,内层循环会迭代i-1次。由于外层循环随着i值变化会从2增长到n,因此内层循环的迭代次数组成了一个等差数列:

这正如我们在选择排序中看到的那样,也是Θ(n2)。由于每个内层循环迭代会花费常量时间,因此最坏情况下插入排序的运行时间是Θ(n2)。因此,最坏情况下,选择排序和插入排序有近似相等的运行时间。有必要完全弄清楚插入排序的平均运行时间吗?这取决于一个“平均的”输入看起来是怎样的。如果输入数组中的元素的顺序是随机的,那么对于每个元素,它比约有一半在它之前的元素要大,比约有一半在它之前的元素要小,因此每次执行内层循环时,它会近似执行(i-1)/2次迭代。相对于最坏运行时间而言,这会使运行时间减半。但1/2仅仅是一个常数因子,因此,近似情况下,它和最坏情况下的运行时间没有区别,依然是Θ(n2)。当数组开始是“基本有序”时,插入排序是一个绝佳的选择。假定每个数组元素开始时所处的位置均处于最终排好序的终止位置的k步之内。那么一个给定元素移动的次数,经过内层循环的迭代,至多移动k步。因此,包括所有内层循环迭代,所有元素移动次数至多为kn次,这反过来告诉我们内层循环迭代的总次数最多是kn次(由于每个内层循环中每个元素恰好移动一个位置)。如果k是一个常数,那么插入排序总共的运行时间将是Θ(n),因为Θ符号能把常量因子k考虑在内。事实上,我们甚至能够容忍一些元素在数组中移动很长的距离,只要这样的元素不太多。尤其是,如果l个元素能在数组中任意移动(因此每个这样的元素移动次数能达到n-1次),而剩下的n-l个元素最多移动k个位置,那么总共的移动次数至多是l(n-1)+(n-l)k=(k+l)n-(k+1)l,如果k和l都是常量,它也是Θ(n)。比较插入排序和选择排序的近似运行时间,我们会看到在最坏情况下,它们是一样的。当数组是基本有序时,插入排序更好些。39然而,选择排序较插入排序有以下优点:在任何条件下选择排序都只会移动元素Θ(n)次,而插入排序的元素移动次数可能会达到Θ(n2)次,这是因为INSERTIONSORT每执行一次第1Bi步就会移动一次元素。正如我们在选择排序中所指出的那样,如果移动一个元素相当耗时并且你无法确知插入排序的输入是否接近最好情况,那么最好运行选择排序而不是插入排序。

时间: 2024-10-25 08:25:31

《算法基础:打开算法之门》一3.3 插入排序的相关文章

《算法基础:打开算法之门》一导读

前言 Algorithms Unlocked 计算机是如何解决问题的呢?小小的GPS是如何只在几秒钟内就从无数条可能路径中找出到达目的地的最快捷路径的呢?在网上购物时,又如何防止他人窃取你的信用卡账号呢?解决这些问题,以及大量其他问题的答案均是算法.我写本书的目的就是为你打开算法之门,解开算法之谜. 我是<算法导论>的合著者之一.<算法导论>是一本特别好的书(当然,这是我个人的主观评价),但是它确实相当专业. 本书并不是<算法导论>,甚至不能被称为一本教材.它既没有对计

《算法基础:打开算法之门》一1.2 资源利用

1.2 资源利用 什么样的算法才能称为高效使用计算资源的算法呢?我们在讨论近似算法时提及了一个衡量效率的标准:时间.一个能给出正确输出但是会花费很长时间才能得出结果的算法可能是没有价值的.如果你的GPS需要一个小时才能计算出推荐的驾驶路线,你还会愿意打开GPS吗?诚然,一旦我们知道某算法能给出一个正确输出,时间便是我们用来衡量算法效率的主要方式.但是时间不是唯一的衡量标准.由于一个计算机算法必须能够在可用的内存空间上运行,因此我们可能还需要考虑该算法需要占用多大的计算机内存空间(它的"内存占用量

《算法基础:打开算法之门》一第3章 排序算法和查找算法

第3章 Algorithms Unlocked 排序算法和查找算法 在第2章中,我们看到了在数组上进行线性查找的三个算法.我们能做得更好吗?答案是:看情况.如果不清楚数组中的元素是否有序,我们是不可能做得更好的.在最坏情况下,我们必须查找数组的所有n个元素,因为如果在前n-1个元素中不能找到要找的值,那么要查找的元素可能在第n个位置上.因此,当我们不清楚数组中的元素是否有序时,我们不可能实现比Θ(n)更好的最坏情况运行时间. 然而,假定数组是以非递减顺序排序的,那么根据"非递减"的含义

《算法基础:打开算法之门》一2.1 如何描述计算机算法

2.1 如何描述计算机算法 将计算机算法描述成一个可执行程序可以有多种选择,例如使用通用的编程语言表示,像Java.C.C++.Python或Fortran.诚然,许多教科书上的算法都是这么表示的.但是使用实际的编程语言来表示算法所带来的问题是你可能会在语言细节上越陷越深,而对算法本身的认识反而模糊不清.另一种表示算法的方式是"伪代码",就像我们在<算法导论>中使用的一样,它听起来像是多种编程语言和英语的混合表示.如果你曾用一种实际的编程语言编写过程序,那么你就能很容易地搞

数据结构与算法系列(2)基础排序算法

前言 在计算机中实现存储数据最普遍的两种操作就是排序和查找.这是从计算机产业初始就已经确认的 了.这意味着排序和查找也是计算机科学领域最值得研究的两种操作.本书提到的许 多数据结构的主要设计目的就是为了使排序和/或查找更加简单,同时也是为了数据在结构内的存 储更加有效. 本章会介绍有关数据排序和查找的基础算法.这些算法仅依赖数组作为数据结构,而且所采用的 "高级"编程技术只是递归.本章还介绍了用来非正式分析不同算法之间速度与效率的方 法,此方法贯穿全书. 1.排序算法 人们在日常生活中

程序员必须知道的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要Ο(n log n)次比较.在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见.事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来. 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists). 算法步骤: 1 从数列中挑出一个元素,称为 "

java-一道基础的算法,答案是什么?

问题描述 一道基础的算法,答案是什么? 看开始看算法(第四版) 第一张的一道练习 给出以下表达式的类型和值 d. 1+2+'3'**** 这个我觉得java是会自动转化为字符型吗? 我就自己println试验了一下. System.out.println(1+2+'3'); 结果为54,不懂了,求教. 但是我看了网上的答案是33?一样不懂 我已经知道了,题目中是我错误 原题是双引号,字符型 1+2+"3" 我看成1+2+'3'了.不过倒是加深了理解,谢谢各位 解决方案 带单引号的3是字

程序员必须知道的10大基础实用算法及其讲解(转)

  算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序n个项目要Ο(nlogn)次比较.在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见.事实上,快速排序通常明显比其他Ο(nlogn)算法更快,因为它的内部循环(innerloop)可以在大部分的架构上很有效率地被实现出来. 快速排序使用分治法(Divideandconquer)策略来把一个串行(list)分为两个子串行(sub-lists). 算法步骤: 1从数列中挑出一个元素,称为"基准"(p

一道算法基础题 uva1586

问题描述 一道算法基础题 uva1586 题目链接在这儿 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=830&page=show_problem&problem=4461 我自己做的代码如下 但是通不过 测了好多数据都没问题 #include<cstdio> #include<cstring> using namespace std; in

java 算法基础之二快速排序算法

http://www.cnblogs.com/hexiaochun/archive/2012/09/03/2668324.html java 算法基础之二快速排序算法 所谓的快速排序的思想就是,首先把数组的第一个数拿出来做为一个key,在前后分别设置一个i,j做为标识,然后拿这个key对这个数组从后面往前遍历,及j--,直到找到第一个小于这个key的那个数,然后交换这两个值,交换完成后,我们拿着这个key要从i往后遍历了,及i++;一直循环到i=j结束,当这里结束后,我们会发现大于这个key的值