插入排序(Insertion Sort)的基本思想是每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止,
程序算法艺术与实践:经典排序算法之插入排序
。基本思想与伪代码
经过j-1遍处理后,A[1..j-1]己排好序。第j遍处理仅将A[j]插入L[1..j-1]的适当位置,使得A[1..j]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较A[j]和A[j-1],如果A[j-1]≤ A[j],则A[1..j]已排好序,第i遍处理就结束了;否则交换A[j]与A[j-1]的位置,继续比较A[j-1]和A[j-2],直到找到某一个位置i(1≤i≤j-1),使得A[j] ≤A[j+1]时为止。用伪码描述如下:
算法: InsertSort(A,n)输入:n个数组A输出:按照递增顺序的数组A1. for j ← 2 to n do2. x←A[j]3. i ← j-1 //行3到行7把A[j]插入A[1.....j-1]之中4. while i >0 and x 如下图所示演示了对4个元素进行插入排序的过程,共需要(a),(b),(c)三次插入。对4个元素进行插入排序</p><p> <img alt="/" src="http://img2.shangxueba.com/img/uploadfile/20150924/15/4B074EF11CDA1D4E4FDFB22345370710.gif" /></p><p> 在插入排序算法中,为了写程序方便我们可以引入一个哨兵元素A[0],它小于A[1..n]中任一记录。所以,我们设元素的类型ElementType中有一个常量-∞,它比可能出现的任何记录都小。如果常量-∞不好事先确定,就必须在决定A[i]是否向前移动之前检查当前位置是否为1,若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时,就将A[i]放入A[0]中,这样也可以保证在适当的时候结束第i遍处理。</p><H4>效率分析</h4></p><p> 考虑算法Insertion_Sort的复杂性。对于确定的i,内while循环的次数为O(i),所以整个循环体内执行了∑O(i)=O(∑i),其中i从2到n。即比较次数为O(n2)。如果输入序列是从大到小排列的,那么内while循环次数为i-1次,所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知,最坏情况下,Insertion_Sort要比较Ω(n^2)次。如果元素类型是一个很大的纪录,则算法第5行要消耗大量的时间,因此有必要分析移动元素的次数。经过分析可知,平均情况下第5行要执行n(n-1)/4次,分析方法与冒泡排序的分析相同。如果移动元素要消耗大量的时间,则可以用链表来实现线性表。</p><H4>Insertion_Sort实现</h4></p><p> 根据插入排序伪码思想,实现算法代码如下所示:</p>电脑资料《程序算法艺术与实践:经典排序算法之插入排序》(http://meiwen.anslib.com)。那么如下代码呢>_<:</p>