插入排序Insertion-Sort

最近在学习算法导论这本书,对一些算法进行了进一步的学习,在这里记录一下。

排序算法可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。内部排序是排序的基础,在内部排序中,根据排序过程中所依据的原则可以将它们分为5类:插入排序(直接插入排序、二分法插入排序、希尔排序)、交换排序(冒泡排序、快速排序)、选择排序(直接选择排序、堆排序)、归并排序和基数排序;根据排序过程的时间复杂度来分,可以分为三类:简单排序、先进排序、基数排序。

首先,研究一下直接插入排序算法(Insertion Sort),对于少量元素的排序,这是一个有效的算法。算法导论中提出了一个扑克牌的例子来形容插入排序,我们对扑克牌进行排序。开始时,左手为空且桌子上牌面向下,然后我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右向左将它与手中已有的每张牌进行比较。

插入排序的伪代码表示如下,这里定义数组A[0,...,n-1]包含了一个长度为n的数组,在伪代码中数组长度n用A.length表示。

1Insertion-Sort(A) 2for j=1 to A.length-1 3 key=A[j] 4 //INSERT A[j] into the sorted sequence A[0...j-1] 5 i=j-1 6 while i>=0 and A[i]>key 7 A[i+1]=A[i] 8 i=i-1 9 A[i+1]=key 10 11

插入排序的具体工作流程如下:(以下图片来自算法导论) 

具体实现的代码稍后补上,现在分析一下该算法的时间复杂度:

当问题规模为n时,最好情况(序列本身有序):比较次数:n-1;移动次数:0
最差情况(逆序):比较次数:2+3+4+……+n=(n+2)n/2;
移动次数:Mmax=1+2+3+……+n-1=n*n/2
若待排序对象序列中出现各种可能排列的概率相同,则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和对象移动次数约为 n^2/4。因此,直接插入排序的时间复杂度为 O(n^2) ,是一种 稳定的排序方法。(若在待排序的记录中,存在两个或两个以上的关键码值相等的记录,经排序后这些记录的相对次序仍然保持不变,则称相应的排序方法是稳定的方法,否则是不稳定的方法。)

空间复杂度为O(1),不需要额外存储空间。

 

代码交流 2021