NoKuu

插入算法，顾名思义，在这里我不介绍了，这种算法就像你打扑克牌前理牌一样。

插入算法是一个对少量元素排序比较有效的算法，意思是插入算法在对大量数据进行排序时，效率不是很高。

我们来看一下插入算法在 c++ 下的具体实现（升序）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
using namespace std;
 
void main()
{
	const int N = 10;
	int a[N] = {12, 9, 13, 78, 55, 34, 77, 55, 4, 52};
 
/*算法的主体开始*/
							//cost	times
	for(int i=1; i<n ; i++)			//c1		n
	{
		int key = a[i];			//c2		n-1
		int j = i - 1;			//c3		n-1
 
		while(j >= 0 && a[j] > key)	//c4
		{
			a[j+1] = a[j];		//c5
			j--;			//c6
		}
		a[j+1] = key;			//c7		n-1
	}
/*算法的主体结束*/
 
	for(int m=0; m</n><n ; m++)
		cout<<a[m]<<"\t";
}

我们假定算法主体中每条语句所执行的时间是一个常量 cost，而对数据进行排序时相对应的执行次数为 times。

那么最佳情况下，运行时间为（已经排好序为升序）：
T(n) = c1n +c2(n-1) +c3(n-1) +c4(n-1) +c7(n-1)
= (c1 +c2 +c3 +c4 +c7)n -(c2 +c3 +c4 +c7)

而在最坏情况下，运行时间为（此时数据为降序）：
T(n) = c1n +c2(n-1) +c3(n-1) +c4( n(n + 1)/2 – 1 ) +c5( n(n – 1)/2 ) +c6( n(n – 1)/2 ) +c7(n-1)
= (c4/2 + c5/2 + c6/2)n^2 +(c1 +c2 +c3 +c4/2 -c5/2 -c6/2 +c7)n -(c2 +c3 +c4 +c7)

我们进一步对运行时间抽象，可以看出：
最佳运行时间T(n) = a*n +b
最差运行时间T(n) = a*n^2 +b*n +c

可以看出在最佳情况下插入算法的运行时间与数据量是成线性增长的；而当数据量相当大时，则插入算法的效率是相当差的。

相关日志

• 三本书 (0)