数据结构-插入排序

插入排序

插入排序的三种常见方法：

直接插入排序、折半插入排序、希尔排序。

数据存储结构

因为我们是用的是C语言来实现算法，因此我们需要创建一个结构体，用来存放初始数据。

结构体定义如下：

#define MAX 100
typedef int KeyType;
typedef struct{
	KeyType key;
}RecordType;
typedef struct{
	RecordType R[MAX+1];
	int length;
}OrderList;

示例数据

 

其中data[0]置为0，用来表示哨兵单元。

直接插入排序

基本思想

当插入第i个记录时，前面的R[1]....R[i-1]已经排好序，这时用R[i]依次与前面的关键字比较，直到找

到合适的位置，随后插入。

代码实现

OrderList InsertSort(OrderList L)	//直接插入排序 
{
	int i,j;
	for(i=2;i<=10;i++){
		L.R[0] = L.R[i];	//L[0]做哨兵单元,同时也用来存放当前i位置记录大小. 
		j = i - 1;		//从i单元的前一个单元开始比较. 
		while(L.R[0].key//升序 
			L.R[j+1] = L.R[j];		//记录依次后移,其中最前面的记录永远会存在连续的两个. 
			j = j - 1;			//j需要前移继续比较. 
		}
		L.R[j+1] = L.R[0];		//j+1为合适的位置. 
	}
	return L;
}

验证

复杂度

时间复杂度为：O()

空间复杂度一直为：O(1)

折半插入排序

基本思想

折半插入排序跟前面的折半查找有同曲异工之妙，其中在查找的时候不再是顺序查找，而是折半查

找，但是在数据移动的过程中，仍然是顺序移动下来。

代码实现

OrderList BinsertSort(OrderList L)		//折半插入排序 
{
	int i,j,low,high,mid;
	for(i=2;i<=L.length;i++){
		L.R[0] = L.R[i];
		low = 1;
		high = i - 1;		//上界应该为i单元的前一个单元位置 
		while(low <= high){		
			mid = (low+high) / 2;
			if(L.R[0].key < L.R[mid].key)
				high = mid - 1;
			else
				low = mid + 1;
		}	//待插入的位置一定是low的位置, 
		for(j=i-1;j>=low;j--)		//i单元前面的所有单元依次后移. 
			L.R[j+1] = L.R[j];
		L.R[low] = L.R[0];		//插入单元 
	}
	return L;
}

验证

复杂度

若待排序列为正序，则时间复杂度为：O(N)

若待排序列为逆序，则时间复杂度为：O()

空间复杂度一直为：O(1)

希尔排序

希尔排序又叫做“缩小增量排序”。

基本思想

先将整个记录序列分割成若干个子序列，分别进行直接插入排序，在整个序列中的记录“基本有序”

时，再对全体记录进行一次直接插入排序。

其中，子序列并不是进行简单的分割，而是将某个增量d的记录组成一个子序列，让增量d逐步缩

短，直到d=1为止。

d的选取有很多种方法，这里只简单说明最基本的一种（足以应对绝大多数情景）：

d = [n/2]--------->d = [d/2]

下面我们给出一个例子：

假定有一个数据序列为：{5,9,12,2,8,15}

我们来看看希尔排序的一个完整过程：

1.d = [6/2] = 3

将整个序列分为三个子序列：{5,2}、{9,8}、{12,15}。

对三个子序列分别进行直接插入排序，得到新的三个子序列：

{2,5}、{8,9}、{12,15}

由这三个子序列拼凑成一个新的序列为：

{2,8,12,5,9,15}

2.d = [3/2] = 1

此时d = 1，所以直接对整个序列{2,8,12,5,9,15}进行一次直接插入排序，即可获得最终结果。

代码实现

OrderList ShellSort(OrderList L)
{
	int i,j,d;
	RecordType tmp;
	for(d=L.length/2;d>0;d/=2){		//d为本趟希尔排序的增量 
		for(i=d+1;i<=L.length;i++){
			tmp = L.R[i];		//保存待插入单元 
			j = i - d;		//j是与i间隔为d的前一个单元 
			while(j>=1&&tmp.key
				L.R[j+d] = L.R[j];		//R[j]必须后移d个位置,因为比较单元间相隔d 
				j = j - d;
			}
			L.R[j+d] = tmp; 
		}
	}
	return L;
}

验证

复杂度

时间复杂度为：O()

空间复杂度一直为：O(1)

所有代码

#include
#define MAX 100
typedef int KeyType;
typedef struct{
	KeyType key;
}RecordType;
typedef struct{
	RecordType R[MAX+1];
	int length;
}OrderList;
 
OrderList InsertSort(OrderList L)	//直接插入排序 
{
	int i,j;
	for(i=2;i<=10;i++){
		L.R[0] = L.R[i];	//L[0]做哨兵单元,同时也用来存放当前i位置记录大小. 
		j = i - 1;		//从i单元的前一个单元开始比较. 
		while(L.R[0].key//升序 
			L.R[j+1] = L.R[j];		//记录依次后移,其中最前面的记录永远会存在连续的两个. 
			j = j - 1;			//j需要前移继续比较. 
		}
		L.R[j+1] = L.R[0];		//j+1为合适的位置. 
	}
	return L;
}
 
OrderList BinsertSort(OrderList L)		//折半插入排序 
{
	int i,j,low,high,mid;
	for(i=2;i<=L.length;i++){
		L.R[0] = L.R[i];
		low = 1;
		high = i - 1;		//上界应该为i单元的前一个单元位置 
		while(low <= high){		
			mid = (low+high) / 2;
			if(L.R[0].key < L.R[mid].key)
				high = mid - 1;
			else
				low = mid + 1;
		}	//待插入的位置一定是low的位置, 
		for(j=i-1;j>=low;j--)		//i单元前面的所有单元依次后移. 
			L.R[j+1] = L.R[j];
		L.R[low] = L.R[0];		//插入单元 
	}
	return L;
}
 
OrderList ShellSort(OrderList L)
{
	int i,j,d;
	RecordType tmp;
	for(d=L.length/2;d>0;d/=2){		//d为本趟希尔排序的增量 
		for(i=d+1;i<=L.length;i++){
			tmp = L.R[i];		//保存待插入单元 
			j = i - d;		//j是与i间隔为d的前一个单元 
			while(j>=1&&tmp.key
				L.R[j+d] = L.R[j];		//R[j]必须后移d个位置,因为比较单元间相隔d 
				j = j - d;
			}
			L.R[j+d] = tmp; 
		}
	}
	return L;
}
 
int main()
{
	OrderList sample;
	sample.length = 10;
	int i,data[11]={0,5,8,4,12,35,6,8,67,64,100};
	for(i=1;i<11;i++)
		sample.R[i].key = data[i];
	sample = ShellSort(sample);
	for(i=1;i<11;i++)
		printf("%d ",sample.R[i].key);
	return 0;
}