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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define MAX_SIZE 20 //定义顺序表的最大长度
typedef int KeyType; //定义关键字类型为整数类型
typedef int InfoType;
typedef struct {
	KeyType key; //关键字类型
	InfoType info; //其他数据项类型
} RedType; //记录类型

typedef struct {
	RedType r[MAX_SIZE+1]; //r[0]闲置或用作哨兵单元
	int length; //顺序表长度
} SqList; //顺序表类型

void StraightInsertionSort1(SqList &L){
	//对顺序表L做直接插入排序
	for(int i=2; i<=L.length; ++i){
		if(L.r[i].key < L.r[i-1].key){
			L.r[0] = L.r[i];//复制为监视哨
			int j;
			for(j=i-1; L.r[0].key < L.r[j].key; --j){//此处重复比较了一次
				L.r[j+1] = L.r[j];//记录后移
			}
			L.r[j+1] = L.r[0];//插入到正确位置
		}
	}
}

void StraightInsertionSort2(SqList &L){
	//对顺序表L做直接插入排序
	for(int i=2; i<=L.length; ++i){
		if(L.r[i].key < L.r[i-1].key){
			L.r[0] = L.r[i];//复制为监视哨
			L.r[i] = L.r[i-1];
			int j;
			for(j=i-2; L.r[0].key < L.r[j].key; --j){
				L.r[j+1] = L.r[j];//记录后移
			}
			L.r[j+1] = L.r[0];//插入到正确位置
		}
	}
}

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
28
29
30
31
32
33
34
35
#define MAX_SIZE 20 //定义顺序表的最大长度
typedef int KeyType; //定义关键字类型为整数类型
typedef int InfoType;
typedef struct {
	KeyType key; //关键字类型
	InfoType info; //其他数据项类型
} RedType; //记录类型

typedef struct {
	RedType R[MAX_SIZE+1]; //R[0]闲置或用作哨兵单元
	int length; //顺序表长度
} SqList; //顺序表类型

//R[0]不存放数据元素
void BiInsertionSort(SqList &L){
	for(int i=2; i<=L.length; ++i){
		L.R[0] = L.R[i];//将L.R[i]暂存到L.R[0]
		//在 L.R[1 .. i-1] 中折半查找插入位置；
		int low=1, high=i-1;
		while(low <= high){
			int m = (low+high)/2; // 折半
			if(L.R[0].key < L.R[m].key){
				high = m - 1;//插入点在低半区
			} else {
				low = m + 1;//插入点在高半区
			}//if
		}//while
		int j;
		for(j=i-1; j>=high+1;--j){
			L.R[j+1] = L.R[j];//记录后移
		}//for
		L.R[j+1] = L.R[0];//插入
	}//for
}

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
28
29
30
31
32
33
34
35
36
37
				
				
void LInsertionSort(Elem SL[], int n){
	//对记录序列SL[1..n]做表插入排序
	SL[0].key = MAX_INT;
	SL[0].next=1;
	SL[1].next=0;
	for(i=2; i<=n; ++i){
		for(j=0,k=SL[0].next; SL[k].key<=SL[i].key;j=k,k=SL[k].next){
			SL[j].next = i;
			SL[i].next = k;
		}//结点i 插入在 结点j 和 结点k 之间
	}//for
}//LInsertionSort

// 如何在排序之后调整记录序列？
// 算法中使用了三个指针：
//		p 指示第i个记录的当前位置；
//		i 指示第i个记录应在的位置；
//		q 指示第i+1个记录的当前位置；		
void Arrange(Elem SL[], int n){
	p = SL[0].next; //p指示第一个记录的当前位置
	for(i=1; i<n; ++i){
		while(p<i){
			p = SL[p].next; //
		}
		q = SL[p].next; //q指示尚未调整的表尾
		if(p != i){
			SL[p] <-->SL[i]; //交换记录，使第i个记录到位
			SL[i].next = p; //指向被移走的记录
		}
		p = q; //p指示尚未调整的表尾，为找第i+1个记录做准备
	}//for
}//Arrange

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
//对顺序表L做一趟希尔插入排序。
//本算法是和一趟直接插入排序相比，做了如下修改：
//1、前后记录位置的增量是dk，而不是1；
//2、r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。
void ShellInsert(SqList &L, int dk) {
	for(int i=dk+1; i<=L.length; ++i) {
		if(L.r[i].key < L.r[i-dk].key) {//需将 L.r[i] 插入有序增量子表
			L.r[0] = L.r[i];//暂存在 L.r[0]
			int j;
			for(j=i-dk; j>0 && (L.r[0].key < L.r[j].key); j-=dk) {
				L.r[j+dk] = L.r[j];//记录后移，查找插入位置
			}
			L.r[j+dk] = L.r[0];//插入
		}
	}
}
//按增量序列 dlta[0 .. t-1]对顺序表L做希尔排序
//SqList &L  
//int dlta[]  增量序列
//int t		  排序趟数
void ShellSort(SqList &L, int dlta[], int t) {
	for(int k=0; k<t; ++t){
		ShellInsert(L, dlta[k]);//一趟增量为dlta[k]的插入排序
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void ShellInsert(Elem R[], int dk){
	for(int i=dk+1; i<=n; ++i){
		if(R[i].key < R[i-dk].key){
			R[0] = R[i];
			int j;
			for(j=i-dk; j>0 && (R[0].key < R[j].key); j-=dk){
				R[j+dk] = R[j];
			}
			R[j+dk] = R[0];
		}
	}
}

void ShellSort(Elem R[], int dlta[], int t){
	for(int k=0; k<t; ++t){
		ShellInsert(R, dlta[k]);
	}
}