插入排序(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
输出:按照递增顺序的数组A
1. for j ← 2 to n do
2. x←A[j]
3. i ← j-1 //行3到行7把A[j]插入A[1.....j-1]之中
4. while i >0 and x <A[i] do
5. A[i+1] ← A[i]
6. i← i-1
7. A[i+1] ← x
~~~
如下图所示演示了对4个元素进行插入排序的过程,共需要(a),(b),(c)三次插入。对4个元素进行插入排序
![](https://box.kancloud.cn/dd369031fdd39522dfdcc41a561ae8f0_491x360.jpg)
在插入排序算法中,为了写程序方便我们可以引入一个哨兵元素A[0],它小于A[1..n]中任一记录。所以,我们设元素的类型ElementType中有一个常量-∞,它比可能出现的任何记录都小。如果常量-∞不好事先确定,就必须在决定A[i]是否向前移动之前检查当前位置是否为1,若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时,就将A[i]放入A[0]中,这样也可以保证在适当的时候结束第i遍处理。
#### 效率分析
考虑算法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次,分析方法与冒泡排序的分析相同。如果移动元素要消耗大量的时间,则可以用链表来实现线性表。
#### Insertion_Sort实现
根据插入排序伪码思想,实现算法代码如下所示:
~~~
void InsertSort(int *a,int n) {
int i,j,t,m;
for (i=1;i<n;i++) {
t=a[i];
j=i-1;
while(j>=0 && t<a[j]) {
a[j+1]=a[j];
j--;
}
a[j+1]=t;
}
}
~~~
我们对上述实现codes,感觉并不是喜欢编程风格(^_^)。那么如下代码呢>_<:
~~~
void InsertionSort(int *ptritems, int count) {
int i, j, k;
for (i=1; i< count; ++i) {
k = ptritems[i];
for ( j=i-1; (j>=0) && (k<ptritems[j]); j--)
ptritems[j+1] = ptritems[j];
ptritems[j+1] = k;
}
}
~~~
测试之前,在此给出部分Main函数的部分code.其中约定N为20(输入数组大小),同时,为了让输入数组的值是随机产生,使用rand()函数。代码如下所示:
~~~
int array[N],i; //声明数组
srand(time(NULL));
for(i=0;i<N;i++){ //初始化数组
array[i]=rand()/1000+10;
}
printf("Sort Before:\n");
for(i=0;i<N;i++) {
printf("%d ",array[i]); //输出
}
printf("\n");
InsertSort(array,N);//排序
printf("Sort After:\n");
for(i=0;i<N;i++) {
printf("%d ",array[i]); //输出
}
~~~
在这段程序中,主函数首先初始化一个数组,并输出排序前的数组内容。然后,调用插入排序法子函数,接着输出排序后的数组内容。
在插入排序法子程序中,首先将需要插入的元素保存到变量t中。变量j表示插入的位置(插入数组元素的序号),设置其值为i-1,表示准备将当前位置(序号为i)的数插入到序号为i-1(即前一个元素)的位置。
接着,通过while循环判断,如果序号为j元素的数据大于变量t(需要插入的数据),则将序号为j的元素向后移,同时j-1,以判断前一个数据是否还需要向后移。通过该循环,找到一个元素的值比t小,该元素的序号为j。然后,将在序号为j的下一个元素插入数据。
编译执行这段程序,得到如下结果,如下图所示。
![](https://box.kancloud.cn/21841928702c045c03dc843df1edd9c6_644x105.jpg)
插入排序法在数据已有一定顺序的情况下,效率较好。但如果数据无规则,则需要移动大量的数据,其效率就与冒泡排序法和选择排序法一样差了。插入排序法是一个原地置换排序法,也是一个稳定排序法。插入法虽然在最坏情况下复杂性为θ(n^2),但是对于小规模输入来说,插入排序法是一个快速的原地置换排序法。许多复杂的排序法,在规模较小的情况下,都使用插入排序法来进行排序,比如快速排序和桶排序。
关于[程序算法艺术与实践](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多讨论与交流,敬请关注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).
- 前言
- 螺旋矩阵、螺旋队列算法
- 程序算法艺术与实践:稀尔排序、冒泡排序和快速排序
- Josephu 问题:数组实现和链表实现
- 杨辉三角形算法
- 位图排序
- 堆排序的实现
- Juggling算法
- 【编程珠玑】排序与位向量
- 取样问题
- 变位词实现
- 随机顺序的随机整数
- 插入排序
- 二分搜索
- 产生不重复的随机数
- 约瑟夫环解法
- 快速排序
- 旋转交换或向量旋转
- 块变换(字符反转)
- 如何优化程序打印出小于100000的素数
- 基本的排序算法原理与实现
- 利用马尔可夫链生成随机文本
- 字典树,后缀树
- B-和B+树
- 程序算法艺术与实践引导
- 程序算法艺术与实践:基础知识之有关算法的基本概念
- 程序算法艺术与实践:经典排序算法之桶排序
- 程序算法艺术与实践:基础知识之函数的渐近的界
- 程序算法艺术与实践:递归策略之矩阵乘法问题
- 程序算法艺术与实践:递归策略之Fibonacci数列
- 程序算法艺术与实践:递归策略基本的思想
- 程序算法艺术与实践:经典排序算法之插入排序
- 程序算法艺术与实践:递归策略之递归,循环与迭代