简单入门排序算法（直接插入排序，折半插入排序，希尔排序，冒泡排序，堆排序，归并排序）

预备知识（排序数组的创建20，100 ，500 个随机数进行排序）

“Struct.h”

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#pragma once
#include<iostream>
#include<string>
using namespace std;
#include<cstdlib>  //C语言标准库函数，包含随机函数rand（）srand(number);
#include<ctime>  //time函数头文件
#define MinSize 20
#define MinddleSize 100
#define MaxSize 500

typedef struct {
	int key;
	//string name; 先做保留
}Redtype;

typedef struct {
	Redtype r[MinSize + 1];
	int length;
	int countMove = 0;
	int countCompare= 0 ;
}Sqlist1;

typedef struct {
	Redtype r[MinddleSize + 1];
	int length;
	int countMove = 0;
	int countCompare = 0;
}Sqlist2;

typedef struct {
	Redtype r[MaxSize + 1];
	int length;
	int countMove = 0;
	int countCompare = 0;
}Sqlist3;

void CreateList(Sqlist1 &L) {
	L.length = 0;
	srand(int(time(0)));
	for (int i = 1; i <= MinSize; i++) {
		L.r[i].key = rand() % 100;
		L.length++;
	}
}
void CreateList(Sqlist2 &L) {
	L.length = 0;
	srand(int(time(0)));
	for (int i = 1; i <= MinddleSize; i++) {
		L.r[i].key = rand() % 100;
		L.length++;
	}
}
void CreateList(Sqlist3 &L) {
	L.length = 0;
	srand(int(time(0)));
	for (int i = 1; i <= MaxSize; i++) {
		L.r[i].key = rand() % 100;
		L.length++;
	}
}
void ShowList(Sqlist1 L) {
	for (int i = 1; i <= L.length; i++) {
		cout << L.r[i].key << " ";
		if (i % 20 == 0)  //每行20个
			cout << endl;
	}
	cout << "n比较次数为：" << L.countCompare << endl;
	cout << "移动次数为： " << L.countMove << endl;
}
void ShowList(Sqlist2 L) {
	for (int i = 1; i <= L.length; i++) {
		cout << L.r[i].key << " ";
		if (i % 20 == 0)  //每行20个
			cout << endl;
	}
	cout << "n比较次数为：" << L.countCompare << endl;
	cout << "移动次数为： " << L.countMove << endl;
}
void ShowList(Sqlist3 L) {
	for (int i = 1; i <= L.length; i++) {
		cout << L.r[i].key << " ";
		if (i % 20 == 0)  //每行20个
			cout << endl;
	}
	cout << "n比较次数为：" << L.countCompare << endl;
	cout << "移动次数为： " << L.countMove << endl;
}

插入排序：

（一）：简单插入排序（Straight Insertion sort）

• 将要排序的n个数据放在一个数组中
• 从头开始进行n-1次插入排序，将第i个数据插入到r[i-1]的有序序列中，成为i个元素的有序序列
• 数组的第一个位置作为缓冲单元，也作为标志单元，防止索引越界，
• 每一趟循环中，第i个元素先放备份于缓存单元，从r[i-1]后往前比较，如果i元素值较小，就将较大的元素往后移动，直到遇到合适的位置（找到大于等于第i个元素的值，还是到达第一个数组首个元素位置），将待插入元素插入到合适的位置。

StraightInsertionSort.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#pragma once
#include"Struct.h"

void StraightInsertSort(Sqlist1 &L) {
	for (int i = 2; i <= L.length; i++) {  //进行 n-1次顺序查找
		L.countCompare++;
		if (L.r[i].key < L.r[i - 1].key) { //若要插入的元素小于有序表最后一个元素，
			L.r[0] = L.r[i];
			L.countMove++;
			L.r[i] = L.r[i - 1];  //将有序表最后一个结构体元素后移
			L.countMove++;
			int j;
			for (j = i - 2; L.r[0].key < L.r[j].key; j--) {// 从后往前匹配找位置，若当前位置不符合则进入循环，找到位置或者到达了监视哨则退出循环
				L.r[j + 1] = L.r[j];
				L.countMove++;
				L.countCompare++;
			}
			L.countCompare++;
			L.r[j + 1] = L.r[0]; //将待插入的结构体元素插入到正确的位置
			L.countMove++;
		}
	}
}
void StraightInsertSort(Sqlist2 &L) {
	for (int i = 2; i <= L.length; i++) {  //进行 n-1次顺序查找
		L.countCompare++;
		if (L.r[i].key < L.r[i - 1].key) { //若要插入的元素小于有序表最后一个元素，
			L.r[0] = L.r[i];
			L.countMove++;
			L.r[i] = L.r[i - 1];  //将有序表最后一个结构体元素后移
			L.countMove++;
			int j;
			for (j = i - 2; L.r[0].key < L.r[j].key; j--) {// 从后往前匹配找位置，若当前位置不符合则进入循环，找到位置或者到达了监视哨则退出循环
				L.r[j + 1] = L.r[j];
				L.countMove++;
				L.countCompare++;
			}
			L.countCompare++;
			L.r[j + 1] = L.r[0]; //将待插入的结构体元素插入到正确的位置
			L.countMove++;
		}
	}
}
void StraightInsertSort(Sqlist3 &L) {
	for (int i = 2; i <= L.length; i++) {  //进行 n-1次顺序查找
		L.countCompare++;
		if (L.r[i].key < L.r[i - 1].key) { //若要插入的元素小于有序表最后一个元素，
			L.r[0] = L.r[i];
			L.countMove++;
			L.r[i] = L.r[i - 1];  //将有序表最后一个结构体元素后移
			L.countMove++;
			int j;
			for (j = i - 2; L.r[0].key < L.r[j].key; j--) {// 从后往前匹配找位置，若当前位置不符合则进入循环，找到位置或者到达了监视哨则退出循环
				L.r[j + 1] = L.r[j];
				L.countMove++;
				L.countCompare++;
			}
			L.countCompare++;
			L.r[j + 1] = L.r[0]; //将待插入的结构体元素插入到正确的位置
			L.countMove++;
		}
	}
}
void OperationStraightInsertSort() {
	cout << "n********** 20个随机数**********n";
	Sqlist1 L1;
	CreateList(L1);
	cout << "n排序前： n" << endl;
	ShowList(L1);
	cout << endl;
	cout << "n排序后： n" << endl;
	StraightInsertSort(L1);
	ShowList(L1);

	cout << "nn********** 100个随机数**********n";
	Sqlist2 L2;
	CreateList(L2);
	cout << "n排序前： n" << endl;
	ShowList(L2);
	cout << endl;
	cout << "n排序后： n" << endl;
	StraightInsertSort(L2);
	ShowList(L2);

	cout << "nn********** 500个随机数**********n";
	Sqlist3 L3;
	CreateList(L3);
	cout << "n排序前： n" << endl;
	ShowList(L3);
	cout << endl;
	cout << "n排序后： n" << endl;
	StraightInsertSort(L3);
	ShowList(L3);
}

• 分析

• 是稳定的排序
• 对于n个元素的平均移动和比较次数都是n^2/4
• 适用于链式存储和顺序存储，基本有序而且数据量较小的情况

结果：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

********** 20个随机数**********

排序前：

98 25 40 27 93 3 1 29 97 25 29 51 62 9 21 78 14 3 3 29

比较次数为：0
移动次数为： 0


排序后：

1 3 3 3 9 14 21 25 25 27 29 29 29 40 51 62 78 93 97 98

比较次数为：130
移动次数为： 149


********** 100个随机数**********

排序前：

98 25 40 27 93 3 1 29 97 25 29 51 62 9 21 78 14 3 3 29
13 29 77 90 97 30 94 97 91 99 80 12 3 3 20 68 88 42 30 47
75 33 24 94 56 79 9 44 73 27 47 48 91 88 74 60 46 9 17 91
61 74 10 32 82 94 17 95 75 24 41 99 41 95 62 12 79 65 50 67
30 59 27 60 88 73 44 52 63 34 56 8 56 65 99 80 91 59 70 83

比较次数为：0
移动次数为： 0


排序后：

1 3 3 3 3 3 8 9 9 9 10 12 12 13 14 17 17 20 21 24
24 25 25 27 27 27 29 29 29 29 30 30 30 32 33 34 40 41 41 42
44 44 46 47 47 48 50 51 52 56 56 56 59 59 60 60 61 62 62 63
65 65 67 68 70 73 73 74 74 75 75 77 78 79 79 80 80 82 83 88
88 88 90 91 91 91 91 93 94 94 94 95 95 97 97 97 98 99 99 99

比较次数为：2189
移动次数为： 2282


********** 500个随机数**********

排序前：

98 25 40 27 93 3 1 29 97 25 29 51 62 9 21 78 14 3 3 29
13 29 77 90 97 30 94 97 91 99 80 12 3 3 20 68 88 42 30 47
75 33 24 94 56 79 9 44 73 27 47 48 91 88 74 60 46 9 17 91
61 74 10 32 82 94 17 95 75 24 41 99 41 95 62 12 79 65 50 67
30 59 27 60 88 73 44 52 63 34 56 8 56 65 99 80 91 59 70 83
81 63 45 42 23 21 43 26 28 71 14 91 10 81 99 55 93 41 77 95
96 82 9 32 88 5 12 53 95 92 20 37 90 56 44 35 25 18 7 16
22 90 26 99 52 36 57 10 56 98 47 85 42 90 53 73 26 4 1 23
5 55 79 48 54 84 52 51 68 58 93 17 14 56 62 84 4 32 64 31
91 98 15 29 40 64 28 25 37 27 70 1 9 6 27 65 14 41 10 29
79 45 46 53 50 58 22 45 62 13 83 14 38 43 97 8 42 10 82 12
46 18 11 7 8 71 80 27 9 41 10 90 31 51 47 77 72 64 21 23
31 20 19 10 99 55 61 9 77 63 94 11 7 6 31 34 13 4 25 36
71 74 95 22 10 45 77 97 48 27 65 30 62 23 76 28 72 32 94 25
20 90 17 93 38 97 63 18 12 99 56 41 28 86 99 92 15 93 59 76
40 13 76 53 16 31 93 36 13 60 6 59 55 29 40 51 19 84 91 67
42 7 27 24 69 32 36 5 51 32 48 3 42 40 31 88 67 48 20 89
76 70 55 88 15 11 21 37 84 76 83 59 13 52 39 53 78 88 11 72
4 27 71 26 42 70 94 73 1 43 35 3 43 78 58 28 7 36 20 58
71 60 31 21 20 18 55 23 33 73 16 50 41 76 57 80 50 53 80 45
82 86 23 83 57 80 79 2 51 36 3 79 8 75 74 47 60 57 13 15
40 29 27 30 2 77 38 93 80 52 59 27 80 11 4 93 87 56 5 43
11 7 68 23 17 11 46 73 83 53 51 41 2 75 7 17 76 60 50 82
68 42 53 72 85 52 70 84 32 34 46 86 0 77 89 3 84 35 93 80
12 58 78 28 16 15 74 83 62 87 33 23 80 21 39 47 93 43 81 1

比较次数为：0
移动次数为： 0


排序后：

0 1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 4 4
4 4 4 5 5 5 5 6 6 6 7 7 7 7 7 7 7 8 8 8
8 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 11 11 11 11
11 11 11 12 12 12 12 12 12 13 13 13 13 13 13 13 14 14 14 14
14 15 15 15 15 15 16 16 16 16 17 17 17 17 17 17 18 18 18 18
19 19 20 20 20 20 20 20 20 21 21 21 21 21 21 22 22 22 23 23
23 23 23 23 23 23 24 24 24 25 25 25 25 25 25 26 26 26 26 27
27 27 27 27 27 27 27 27 27 27 28 28 28 28 28 28 29 29 29 29
29 29 29 29 30 30 30 30 30 31 31 31 31 31 31 31 32 32 32 32
32 32 32 33 33 33 34 34 34 35 35 35 36 36 36 36 36 36 37 37
37 38 38 38 39 39 40 40 40 40 40 40 41 41 41 41 41 41 41 41
42 42 42 42 42 42 42 42 43 43 43 43 43 43 44 44 44 45 45 45
45 45 46 46 46 46 46 47 47 47 47 47 47 48 48 48 48 48 50 50
50 50 50 51 51 51 51 51 51 51 52 52 52 52 52 52 53 53 53 53
53 53 53 53 54 55 55 55 55 55 55 56 56 56 56 56 56 56 56 57
57 57 57 58 58 58 58 58 59 59 59 59 59 59 60 60 60 60 60 60
61 61 62 62 62 62 62 62 63 63 63 63 64 64 64 65 65 65 65 67
67 67 68 68 68 68 69 70 70 70 70 70 71 71 71 71 71 72 72 72
72 73 73 73 73 73 73 74 74 74 74 74 75 75 75 75 76 76 76 76
76 76 76 77 77 77 77 77 77 77 78 78 78 78 79 79 79 79 79 79
80 80 80 80 80 80 80 80 80 80 81 81 81 82 82 82 82 82 83 83
83 83 83 83 84 84 84 84 84 84 85 85 86 86 86 87 87 88 88 88
88 88 88 88 89 89 90 90 90 90 90 90 91 91 91 91 91 91 91 92
92 93 93 93 93 93 93 93 93 93 93 94 94 94 94 94 94 95 95 95
95 95 96 97 97 97 97 97 97 98 98 98 99 99 99 99 99 99 99 99

比较次数为：63261
移动次数为： 63744

D:visual studio 2017数据结构Sort_experiment4DebugSort_experiment4.exe (进程 8384)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口...

折半插入排序（Binary Insertion Sort)

• 将待排序数据插入到数组r[n]中
• 进行n-1次循环和折半插入排序，每次将第i个元素插入到r[i-1]，成有序序列r[i]
• 每一次排序中，将待插入元素备份到缓存单元，将第i个元素与有序序列r[i-1]的中间元素（下标为m)比较，low(1)记录有序表的第一个元素的下标，high(i-1)记录有序表的最后一个元素的下标，如果i元素较大就对后子表进行二分查找(low = m +1），较小则对前子表进行二分查找（high = m -1),直到找到合适的位置，
• 找到待插入位置后，将合适的位置以及有序表后面的元素都后移一位，再将待插入元素插入

OperationBianryInsertSort();

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#pragma once
#include"Struct.h"

void BinaryInsertSort(Sqlist1 &L) {
	for (int i = 2; i <= L.length; i++) {
		L.countCompare++;
		L.r[0] = L.r[i];  //监视哨位置记录待插入元素
		L.countMove++;
		int low = 1; int high = i - 1; //置查找区间的初始值
		int m; //折半查找的位置
		while (low <= high) {
			L.countCompare++;
			m = (low + high) / 2; //根据高低位置的折中位置给m赋值
			if (L.r[0].key < L.r[m].key)
				high = m - 1;
			else
				low = m + 1;
			L.countCompare++;
		}
		L.countCompare++;
		for (int j = i - 1; j >= high + 1; j--) {   //将i=1 到 high +1 之间的元素都后移一位
			L.r[j + 1] = L.r[j];
			L.countCompare++;
			L.countMove++;
		}
		L.countCompare++;
		L.r[high + 1] = L.r[0];    //将待插入元素插入到找到的位置中
		L.countMove++;
		cout << "第 "<<i-1<<" 趟排序：" << endl;
		ShowList(L);
	}
	L.countCompare++;
}


void BinaryInsertSort(Sqlist2 &L) {
	for (int i = 2; i <= L.length; i++) {
		L.countCompare++;
		L.r[0] = L.r[i];  //监视哨位置记录待插入元素
		L.countMove++;
		int low = 1; int high = i - 1; //置查找区间的初始值
		int m; //折半查找的位置
		while (low <= high) {
			L.countCompare++;
			m = (low + high) / 2; //根据高低位置的折中位置给m赋值
			if (L.r[0].key < L.r[m].key)
				high = m - 1;
			else
				low = m + 1;
			L.countCompare++;
		}
		L.countCompare++;
		for (int j = i - 1; j >= high + 1; j--) {   //将i=1 到 high +1 之间的元素都后移一位
			L.r[j + 1] = L.r[j];
			L.countCompare++;
			L.countMove++;
		}
		L.countCompare++;
		L.r[high + 1] = L.r[0];    //将待插入元素插入到找到的位置中
		L.countMove++;
	}
	L.countCompare++;
}

void BinaryInsertSort(Sqlist3 &L) {
	for (int i = 2; i <= L.length; i++) {
		L.countCompare++;
		L.r[0] = L.r[i];  //监视哨位置记录待插入元素
		L.countMove++;
		int low = 1; int high = i - 1; //置查找区间的初始值
		int m; //折半查找的位置
		while (low <= high) {
			L.countCompare++;
			m = (low + high) / 2; //根据高低位置的折中位置给m赋值
			if (L.r[0].key < L.r[m].key)
				high = m - 1;
			else
				low = m + 1;
			L.countCompare++;
		}
		L.countCompare++;
		for (int j = i - 1; j >= high + 1; j--) {   //将i=1 到 high +1 之间的元素都后移一位
			L.r[j + 1] = L.r[j];
			L.countCompare++;
			L.countMove++;
		}
		L.countCompare++;
		L.r[high + 1] = L.r[0];    //将待插入元素插入到找到的位置中
		L.countMove++;
	}
	L.countCompare++;
}
void OperationBianryInsertSort() {
	cout << "n********** 20个随机数**********n";
	Sqlist1 L1;
	CreateList(L1);
	cout << "n排序前： n" << endl;
	ShowList(L1);
	cout << endl;
	cout << "n排序后： n" << endl;
	BinaryInsertSort(L1);
	//ShowList(L1);

	cout << "nn********** 100个随机数**********n";
	Sqlist2 L2;
	CreateList(L2);
	cout << "n排序前： n" << endl;
	ShowList(L2);
	cout << endl;
	cout << "n排序后： n" << endl;
	BinaryInsertSort(L2);
	ShowList(L2);

	cout << "nn********** 500个随机数**********n";
	Sqlist3 L3;
	CreateList(L3);
	cout << "n排序前： n" << endl;
	ShowList(L3);
	cout << endl;
	cout << "n排序后： n" << endl;
	BinaryInsertSort(L3);
	ShowList(L3);
}

result

********** 20个随机数**********

排序前：

94 90 85 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：0
移动次数为： 0

排序后：

第 1 趟排序：
90 94 85 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：6
移动次数为： 3
第 2 趟排序：
85 90 94 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：13
移动次数为： 7
第 3 趟排序：
85 90 94 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：20
移动次数为： 9
第 4 趟排序：
82 85 90 94 98 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：31
移动次数为： 15
第 5 趟排序：
18 82 85 90 94 98 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：43
移动次数为： 22
第 6 趟排序：
13 18 82 85 90 94 98 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：56
移动次数为： 30
第 7 趟排序：
13 18 82 85 89 90 94 98 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：68
移动次数为： 35
第 8 趟排序：
13 18 65 82 85 89 90 94 98 89 27 78 82 24 3 73 15 51 67 30

比较次数为：83
移动次数为： 43
第 9 趟排序：
13 18 65 82 85 89 89 90 94 98 27 78 82 24 3 73 15 51 67 30

比较次数为：95
移动次数为： 48
第 10 趟排序：
13 18 27 65 82 85 89 89 90 94 98 78 82 24 3 73 15 51 67 30

比较次数为：112
移动次数为： 58
第 11 趟排序：
13 18 27 65 78 82 85 89 89 90 94 98 82 24 3 73 15 51 67 30

比较次数为：130
移动次数为： 67
第 12 趟排序：
13 18 27 65 78 82 82 85 89 89 90 94 98 24 3 73 15 51 67 30

比较次数为：145
移动次数为： 75
第 13 趟排序：
13 18 24 27 65 78 82 82 85 89 89 90 94 98 3 73 15 51 67 30

比较次数为：167
移动次数为： 88
第 14 趟排序：
3 13 18 24 27 65 78 82 82 85 89 89 90 94 98 73 15 51 67 30

比较次数为：190
移动次数为： 104
第 15 趟排序：
3 13 18 24 27 65 73 78 82 82 85 89 89 90 94 98 15 51 67 30

比较次数为：210
移动次数为： 115
第 16 趟排序：
3 13 15 18 24 27 65 73 78 82 82 85 89 89 90 94 98 51 67 30

比较次数为：235
移动次数为： 131
第 17 趟排序：
3 13 15 18 24 27 51 65 73 78 82 82 85 89 89 90 94 98 67 30

比较次数为：257
移动次数为： 144
第 18 趟排序：
3 13 15 18 24 27 51 65 67 73 78 82 82 85 89 89 90 94 98 30

比较次数为：280
移动次数为： 156
第 19 趟排序：
3 13 15 18 24 27 30 51 65 67 73 78 82 82 85 89 89 90 94 98

比较次数为：304
移动次数为： 171

********** 100个随机数**********

排序前：

94 90 85 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30
53 95 1 82 93 82 0 81 20 32 39 89 19 72 43 53 54 58 44 78
83 97 1 74 17 23 75 29 5 32 91 13 55 17 91 48 34 78 7 25
70 90 52 84 90 29 96 13 13 19 35 31 91 95 22 20 68 98 70 61
29 25 24 60 76 51 78 4 45 52 76 0 81 59 91 34 29 19 42 46

比较次数为：0
移动次数为： 0

排序后：

0 0 1 1 3 4 5 7 13 13 13 13 15 17 17 18 19 19 19 20
20 22 23 24 24 25 25 27 29 29 29 29 30 31 32 32 34 34 35 39
42 43 44 45 46 48 51 51 52 52 53 53 54 55 58 59 60 61 65 67
68 70 70 72 73 74 75 76 76 78 78 78 78 81 81 82 82 82 82 83
84 85 89 89 89 90 90 90 91 91 91 91 93 94 95 95 96 97 98 98

比较次数为：4007
移动次数为： 2845

********** 500个随机数**********

排序前：

94 90 85 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30
53 95 1 82 93 82 0 81 20 32 39 89 19 72 43 53 54 58 44 78
83 97 1 74 17 23 75 29 5 32 91 13 55 17 91 48 34 78 7 25
70 90 52 84 90 29 96 13 13 19 35 31 91 95 22 20 68 98 70 61
29 25 24 60 76 51 78 4 45 52 76 0 81 59 91 34 29 19 42 46
38 89 92 95 92 71 85 85 24 11 24 20 59 37 88 60 3 3 18 33
28 32 14 9 91 35 62 24 22 41 95 31 53 48 57 96 47 25 41 76
16 28 9 50 89 34 56 44 68 68 38 16 6 26 82 65 94 82 39 21
84 83 56 53 62 80 43 95 82 45 91 79 88 72 32 17 85 23 60 53
44 13 36 84 4 98 24 55 86 93 31 22 88 45 16 3 14 97 30 67
16 63 95 47 29 6 6 74 66 64 47 31 54 68 78 30 4 21 8 72
10 58 85 11 37 11 49 82 0 15 37 84 61 64 25 14 38 88 48 40
85 65 87 65 62 96 33 70 84 17 86 15 58 38 19 63 95 45 17 97
25 47 86 76 30 78 44 16 59 9 71 49 16 14 98 15 77 93 9 11
84 63 29 30 94 58 83 78 22 63 70 61 71 67 67 24 22 54 70 64
48 25 34 29 70 51 57 19 21 51 13 13 38 12 31 62 31 72 2 82
71 61 38 97 32 89 9 7 6 89 69 47 74 28 92 69 12 33 60 14
29 98 27 2 9 70 2 69 60 70 0 21 57 19 45 67 48 87 76 55
4 93 98 89 16 70 40 77 72 94 51 19 42 26 65 19 86 55 75 47
81 6 41 99 25 65 65 72 33 3 0 60 42 96 97 57 63 39 75 52
9 87 65 88 18 59 12 35 22 37 33 67 7 66 56 13 77 76 56 90
85 44 20 35 0 72 93 91 18 55 97 87 39 48 92 53 56 53 24 7
98 2 50 74 29 69 46 82 15 10 36 73 7 81 41 20 56 51 4 77
93 3 10 29 11 94 2 19 36 65 93 54 22 49 48 88 15 66 52 83
35 77 3 76 20 56 7 42 48 72 28 0 80 65 53 83 0 23 56 62

比较次数为：0
移动次数为： 0

排序后：

0 0 0 0 0 0 0 0 1 1 2 2 2 2 2 3 3 3 3 3
3 3 4 4 4 4 4 5 6 6 6 6 6 7 7 7 7 7 7 8
9 9 9 9 9 9 9 10 10 10 11 11 11 11 11 12 12 12 13 13
13 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 15 16 16 16
16 16 16 16 17 17 17 17 17 18 18 18 18 19 19 19 19 19 19 19
19 19 20 20 20 20 20 20 21 21 21 21 22 22 22 22 22 22 22 23
23 23 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 26 26 27
27 28 28 28 28 29 29 29 29 29 29 29 29 29 29 30 30 30 30 30
31 31 31 31 31 31 32 32 32 32 32 33 33 33 33 33 34 34 34 34
35 35 35 35 35 36 36 36 37 37 37 37 38 38 38 38 38 38 39 39
39 39 40 40 41 41 41 41 42 42 42 42 43 43 44 44 44 44 44 45
45 45 45 45 46 46 47 47 47 47 47 47 48 48 48 48 48 48 48 48
49 49 49 50 50 51 51 51 51 51 51 52 52 52 52 53 53 53 53 53
53 53 53 54 54 54 54 55 55 55 55 55 56 56 56 56 56 56 56 56
57 57 57 57 58 58 58 58 59 59 59 59 60 60 60 60 60 60 61 61
61 61 62 62 62 62 62 63 63 63 63 63 64 64 64 65 65 65 65 65
65 65 65 65 65 66 66 66 67 67 67 67 67 67 68 68 68 68 69 69
69 69 70 70 70 70 70 70 70 70 70 71 71 71 71 72 72 72 72 72
72 72 72 73 73 74 74 74 74 75 75 75 76 76 76 76 76 76 76 77
77 77 77 77 78 78 78 78 78 78 78 79 80 80 81 81 81 81 82 82
82 82 82 82 82 82 82 82 83 83 83 83 83 84 84 84 84 84 84 85
85 85 85 85 85 85 86 86 86 86 87 87 87 87 88 88 88 88 88 88
89 89 89 89 89 89 89 89 90 90 90 90 91 91 91 91 91 91 91 92
92 92 92 93 93 93 93 93 93 93 94 94 94 94 94 95 95 95 95 95
95 95 96 96 96 96 97 97 97 97 97 97 98 98 98 98 98 98 98 99

比较次数为：72891
移动次数为： 64773

D:visual studio 2017数据结构Sort_experiment4DebugSort_experiment4.exe (进程 7796)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口…

分析

• 稳定排序
• 由于要进行折半查找，用于顺序结构，不能用于链式结构
• 适用于无序，n较大时的情况
• 移动次数不变，平均比较次数减少

希尔排序（Shell Sort）

• 将n个数据存在数组中，按照一定的增量进行分组，对分组的元素进行直接选择排序，一步步达到基本有序，最后做一次直接简单排序实现全部排序成功。
• 每一趟根据不同的增量值dk从增量下标+1的位置开始向后遍历数组，每个元素向前与间隔为dk的元素组成的分组进行直接排序
• 每一趟排序会更加有序，最后对基本有序的整个表实现一次增量为1的直接插入排序

ShellSort.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#pragma once
#include"Struct.h"
void ShellInsert(Sqlist1 &L, int k) {
	for (int i = k + 1; i <= L.length; i++) {
		if (L.r[i].key < L.r[i - k].key) {  //将i处元素插入到有序子列
			L.r[0] = L.r[i];  //将待存储元素存储在辅助单元中
			L.countMove++;
			int j = 0;
			for (int j = i - k; j > 0 && L.r[0].key < L.r[j].key; j -= k) {
				L.r[j + k] = L.r[j];
				L.countMove++;
				L.countCompare++;
			}
			L.countCompare++;
			L.r[j + k] = L.r[0];
			L.countMove++;
		}
		L.countCompare++;
	}
	L.countCompare++;
}
void Shellsort(Sqlist1 &L, int dt[], int t) {
	for (int k = 0; k < t; k++) {
		ShellInsert(L, dt[k]);  //进行t次希尔插入排序
		L.countCompare++;
	}
	L.countCompare++;
}

void ShellInsert(Sqlist2 &L, int k) {
	for (int i = k + 1; i <= L.length; i++) {
		if (L.r[i].key < L.r[i - k].key) {  //将i处元素插入到有序子列
			L.r[0] = L.r[i];  //将待存储元素存储在辅助单元中
			L.countMove++;
			int j = 0;
			for (int j = i - k; j > 0 && L.r[0].key < L.r[j].key; j -= k) {
				L.r[j + k] = L.r[j];
				L.countMove++;
				L.countCompare++;
			}
			L.countCompare++;
			L.r[j + k] = L.r[0];
			L.countMove++;
		}
		L.countCompare++;
	}
	L.countCompare++;
}
void Shellsort(Sqlist2 &L, int dt[], int t) {
	for (int k = 0; k < t; k++) {
		ShellInsert(L, dt[k]);  //进行t次希尔插入排序
		L.countCompare++;
	}
	L.countCompare++;
}
void ShellInsert(Sqlist3 &L, int k) {
	for (int i = k + 1; i <= L.length; i++) {
		if (L.r[i].key < L.r[i - k].key) {  //将i处元素插入到有序子列
			L.r[0] = L.r[i];  //将待存储元素存储在辅助单元中
			L.countMove++;
			int j = 0;
			for (int j = i - k; j > 0 && L.r[0].key < L.r[j].key; j -= k) {
				L.r[j + k] = L.r[j];
				L.countMove++;
				L.countCompare++;
			}
			L.countCompare++;
			L.r[j + k] = L.r[0];
			L.countMove++;
		}
		L.countCompare++;
	}
	L.countCompare++;
}
void Shellsort(Sqlist3 &L, int dt[], int t) {
	for (int k = 0; k < t; k++) {
		ShellInsert(L, dt[k]);  //进行t次希尔插入排序
		L.countCompare++;
	}
	L.countCompare++;
}
void OperationShellSort() {
	
	int dt[] = { 1,3,5 };
	int t = 3;
	cout << "n********** 20个随机数**********n";
	Sqlist1 L1;
	CreateList(L1);
	cout << "n排序前： n" << endl;
	ShowList(L1);
	cout << endl;
	cout << "n排序后： n" << endl;
	Shellsort(L1,dt,t);
	ShowList(L1);

	cout << "nn********** 100个随机数**********n";
	Sqlist2 L2;
	CreateList(L2);
	cout << "n排序前： n" << endl;
	ShowList(L2);
	cout << endl;
	cout << "n排序后： n" << endl;
	Shellsort(L2, dt, t);
	ShowList(L2);

	cout << "nn********** 500个随机数**********n";
	Sqlist3 L3;
	CreateList(L3);
	cout << "n排序前： n" << endl;
	ShowList(L3);
	cout << endl;
	cout << "n排序后： n" << endl;
	Shellsort(L3, dt, t);
	ShowList(L3);
}

result:

********** 20个随机数**********

排序前：

63 92 11 36 46 77 54 74 91 34 50 32 2 65 90 5 84 54 88 33

比较次数为：0
移动次数为： 0

排序后：

33 90 63 50 90 91 91 90 91 91 91 91 92 92 92 92 92 92 92 92

比较次数为：215
移动次数为： 180

********** 100个随机数**********

排序前：

63 92 11 36 46 77 54 74 91 34 50 32 2 65 90 5 84 54 88 33
34 96 24 59 13 83 20 79 69 80 31 19 31 22 68 35 8 78 6 57
50 74 42 85 29 61 92 75 30 74 78 47 35 49 65 65 84 58 53 92
76 98 83 42 83 43 21 10 18 51 62 66 27 82 14 64 99 31 20 98
50 21 39 77 17 79 46 46 29 63 39 6 43 70 93 80 95 82 76 28

比较次数为：0
移动次数为： 0

排序后：

28 39 63 28 80 59 39 63 59 43 82 59 63 82 59 82 82 63 82 82
82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82
82 82 90 85 83 91 91 91 91 91 91 91 91 91 91 91 91 92 92 92
92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92
92 92 92 92 92 92 92 92 92 92 92 92 96 96 96 96 96 98 99 99

比较次数为：3678
移动次数为： 3528

********** 500个随机数**********

排序前：

63 92 11 36 46 77 54 74 91 34 50 32 2 65 90 5 84 54 88 33
34 96 24 59 13 83 20 79 69 80 31 19 31 22 68 35 8 78 6 57
50 74 42 85 29 61 92 75 30 74 78 47 35 49 65 65 84 58 53 92
76 98 83 42 83 43 21 10 18 51 62 66 27 82 14 64 99 31 20 98
50 21 39 77 17 79 46 46 29 63 39 6 43 70 93 80 95 82 76 28
42 40 50 71 99 28 60 36 37 99 22 61 73 87 79 50 89 85 23 96
33 76 90 34 57 96 21 25 24 33 83 78 99 37 85 84 17 7 82 58
25 41 62 90 77 65 13 82 22 51 3 47 51 78 93 16 99 28 7 40
69 55 52 7 42 82 5 94 81 15 49 81 74 14 28 53 85 81 91 18
44 9 52 75 24 49 70 75 43 30 15 98 42 40 36 20 46 67 28 61
68 80 1 10 25 92 91 91 29 92 31 58 83 7 80 91 66 2 43 0
27 83 92 74 63 76 22 45 51 96 31 84 65 29 14 9 44 96 77 56
90 87 22 25 92 10 24 51 3 43 41 30 15 17 7 57 37 55 36 1
61 57 74 40 40 92 31 65 94 99 64 67 55 56 92 0 86 60 4 84
11 18 28 66 1 78 16 6 39 29 4 64 37 22 37 12 1 25 5 23
31 19 17 89 28 85 69 55 10 54 27 94 68 66 4 32 39 60 27 54
30 54 91 36 2 76 55 21 73 18 20 18 44 26 20 25 54 29 84 84
66 68 23 56 40 62 40 75 81 73 68 77 9 14 29 38 44 53 82 67
23 96 64 11 76 71 12 88 24 71 7 42 24 31 2 87 30 80 9 0
33 44 86 54 56 29 22 89 76 71 92 85 95 47 97 17 3 53 50 29
74 97 8 71 76 49 33 46 59 23 88 34 5 44 50 10 63 16 77 90
5 96 10 87 14 60 78 45 61 90 47 9 16 58 96 72 44 12 68 66
54 95 22 98 28 35 12 72 67 89 4 8 35 10 16 27 47 21 73 91
51 13 97 92 79 2 14 4 14 94 14 50 23 0 30 67 99 20 48 13
15 33 13 61 99 75 77 62 75 47 16 46 28 34 84 53 30 77 80 16

比较次数为：0
移动次数为： 0

排序后：

16 23 96 16 96 52 23 96 52 79 89 80 96 89 79 89 80 96 89 79
89 80 96 89 79 89 80 96 89 79 89 80 96 89 79 89 80 96 89 79
89 80 96 89 79 89 80 96 89 79 89 80 96 89 79 89 80 96 89 79
89 80 96 89 79 89 80 96 89 79 89 80 96 89 89 89 80 96 89 89
89 80 96 89 89 89 80 96 89 89 89 80 96 89 89 89 80 96 89 89
89 80 96 89 89 89 80 96 89 89 89 80 96 89 89 89 80 96 89 89
89 80 96 89 89 89 80 96 89 89 89 80 96 89 89 89 89 96 89 89
89 89 96 89 89 89 89 96 89 89 89 89 96 89 89 89 89 96 89 89
89 89 96 89 89 89 89 96 89 89 89 89 96 89 89 89 89 96 89 89
89 89 96 89 89 89 89 96 89 89 89 89 96 89 89 89 89 96 89 89
89 89 96 89 89 89 89 96 89 89 89 89 96 90 89 89 90 96 90 90
89 90 96 90 90 90 90 96 90 90 90 90 96 90 90 90 90 96 90 97
90 90 96 90 97 97 90 96 97 97 97 97 96 97 97 97 97 96 97 97
97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97
97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97
97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97
97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97
97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97
97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97
97 97 96 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97
97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97
97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97
97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97
97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 98 98
98 98 98 98 98 98 98 98 98 99 99 99 99 99 99 99 99 99 99 99

比较次数为：102499
移动次数为： 102209

D:visual studio 2017数据结构Sort_experiment4DebugSort_experiment4.exe (进程 21188)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口…

分析：

• 排序不稳定
• 只能用于顺序结构
• 比较次数和移动次数比直接排序少，更适合n大且无序的顺序表

交换排序

冒泡排序

• 待排序的记录存储在n个大小的存储单元中
• 从头开始进行n次冒泡排序
• 每一趟排序从第i 个记录开始排序，对i和i+1位置的元素比较，如果为逆序（前 > 后)则交换两个位置的记录，将i位置以及后续的最小值放到第i个位置
• 排序结束，记录呈现升序

BubbleSort.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#pragma once
#include"Struct.h"

void Bubble_Sort(Sqlist1 &L) {
	int m = L.length - 1; 
	int flag = 1;
	while (m > 0 && flag == 1) {
		flag = 0;
		for (int i = 1; i <= m; i++) {
			L.countCompare++;
			if (L.r[i].key > L.r[i + 1].key) {
				L.countCompare++;
				flag = 1;
				Redtype t1 = L.r[i];
				L.countMove++;
				L.r[i] = L.r[i+1];
				L.countMove++;
				L.r[i+1] = t1;
				L.countMove++;
			}
			L.countCompare++;
		}
		cout << endl;
			ShowList(L);
		m--;
		L.countCompare++;
		
	}
	L.countCompare++;
}

void Bubble_Sort2(Sqlist2 &L) {
	int size = L.length;
	int flag ;
	for (int pass = 1; pass < size; pass++) {
		L.countCompare++;
		flag = 1;
		int i ;
		for (int i = 1; i <= size - pass; i++) {
			L.countCompare++;
			if (L.r[i].key > L.r[i + 1].key) {
				L.countCompare++;
				Redtype t = L.r[i];
				L.countMove++;
				L.r[i] = L.r[i+1];
				L.countMove++;
				L.r[i + 1] = t;
				L.countMove++;
				flag = 0;
			}
			L.countCompare++;
		}
		L.countCompare++;
		L.countCompare++;
		if (flag)
			break;
	}
	L.countCompare++;
}

void Bubble_Sort(Sqlist3 &L) {
	int m = L.length - 1;
	int flag = 1;
	while (m > 0 && flag == 1) {
		flag = 0;
		for (int i = 1; i <= m; i++) {
			L.countCompare++;
			if (L.r[i].key > L.r[i + 1].key) {
				L.countCompare++;
				flag = 1;
				Redtype t1 = L.r[i];
				L.countMove++;
				L.r[i] = L.r[i + 1];
				L.countMove++;
				L.r[i + 1] = t1;
				L.countMove++;
			}
			L.countCompare++;
		}
		m--;
		L.countCompare++;
	}
	L.countCompare++;
}

void OperationBubbleSort() {
	Sqlist1 L1;
	CreateList(L1);
	cout << "n排序前： n" << endl;
	ShowList(L1);
	cout << endl;
	cout << "n排序后： n" << endl;
	Bubble_Sort(L1);
	//ShowList(L1);
	Sqlist2 L2;
	CreateList(L2);
	cout << "n排序前： n" << endl;
	ShowList(L2);
	cout << endl;
	cout << "n排序后： n" << endl;
	Bubble_Sort2(L2);
	ShowList(L2);
	Sqlist3 L3;
	CreateList(L3);
	cout << "n排序前： n" << endl;
	ShowList(L3);
	cout << endl;
	cout << "n排序后： n" << endl;
	Bubble_Sort(L3);
	ShowList(L3);
}

result

排序前：

65 26 8 66 27 59 19 46 80 60 51 10 3 56 38 88 87 23 85 59

比较次数为：0
移动次数为： 0

排序后：

26 8 65 27 59 19 46 66 60 51 10 3 56 38 80 87 23 85 59 88

比较次数为：54
移动次数为： 48

8 26 27 59 19 46 65 60 51 10 3 56 38 66 80 23 85 59 87 88

比较次数为：105
移动次数为： 90

8 26 27 19 46 59 60 51 10 3 56 38 65 66 23 80 59 85 87 88

比较次数为：150
移动次数为： 120

8 26 19 27 46 59 51 10 3 56 38 60 65 23 66 59 80 85 87 88

比较次数为：191
移动次数为： 144

8 19 26 27 46 51 10 3 56 38 59 60 23 65 59 66 80 85 87 88

比较次数为：230
移动次数为： 168

8 19 26 27 46 10 3 51 38 56 59 23 60 59 65 66 80 85 87 88

比较次数为：264
移动次数为： 183

8 19 26 27 10 3 46 38 51 56 23 59 59 60 65 66 80 85 87 88

比较次数为：296
移动次数为： 198

8 19 26 10 3 27 38 46 51 23 56 59 59 60 65 66 80 85 87 88

比较次数为：325
移动次数为： 210

8 19 10 3 26 27 38 46 23 51 56 59 59 60 65 66 80 85 87 88

比较次数为：351
移动次数为： 219

8 10 3 19 26 27 38 23 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：375
移动次数为： 228

8 3 10 19 26 27 23 38 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：396
移动次数为： 234

3 8 10 19 26 23 27 38 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：415
移动次数为： 240

3 8 10 19 23 26 27 38 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：431
移动次数为： 243

3 8 10 19 23 26 27 38 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：444
移动次数为： 243

排序前：

65 26 8 66 27 59 19 46 80 60 51 10 3 56 38 88 87 23 85 59
11 71 63 42 85 37 82 9 62 19 33 48 28 93 2 75 26 36 28 48
10 76 7 99 64 81 19 10 87 1 47 1 62 37 71 78 17 99 19 72
20 37 21 77 99 29 81 24 74 28 40 60 51 37 79 34 58 16 32 77
68 58 41 92 99 26 92 36 56 60 36 34 10 37 61 35 87 76 89 14

比较次数为：0
移动次数为： 0

排序后：

1 1 2 3 7 8 9 10 10 10 10 11 14 16 17 19 19 19 19 20
21 23 24 26 26 26 27 28 28 28 29 32 33 34 34 35 36 36 36 37
37 37 37 37 38 40 41 42 46 47 48 48 51 51 56 56 58 58 59 59
60 60 60 61 62 62 63 64 65 66 68 71 71 72 74 75 76 76 77 77
78 79 80 81 81 82 85 85 87 87 87 88 89 92 92 93 99 99 99 99

比较次数为：12323
移动次数为： 6870

排序前：

65 26 8 66 27 59 19 46 80 60 51 10 3 56 38 88 87 23 85 59
11 71 63 42 85 37 82 9 62 19 33 48 28 93 2 75 26 36 28 48
10 76 7 99 64 81 19 10 87 1 47 1 62 37 71 78 17 99 19 72
20 37 21 77 99 29 81 24 74 28 40 60 51 37 79 34 58 16 32 77
68 58 41 92 99 26 92 36 56 60 36 34 10 37 61 35 87 76 89 14
25 72 73 18 54 5 2 29 59 83 73 64 53 69 25 19 49 34 56 59
26 6 67 11 76 87 74 92 71 17 30 85 85 63 29 9 16 54 43 38
39 64 83 66 11 58 86 72 37 58 69 81 90 32 81 91 13 13 90 5
41 80 13 45 54 93 59 43 73 71 40 46 91 39 88 36 81 25 16 77
38 85 25 84 57 82 78 29 78 13 95 18 54 74 4 5 25 83 94 10
64 53 92 81 67 78 94 10 16 51 98 31 25 67 63 73 38 41 27 19
19 3 19 27 16 50 44 46 78 12 16 95 41 7 63 35 74 83 91 43
68 27 22 33 89 49 39 4 54 40 90 23 3 33 44 16 35 36 34 21
84 24 56 62 61 89 53 8 77 50 53 81 36 54 39 53 15 70 57 57
64 55 33 74 58 77 65 52 94 9 8 16 7 23 94 66 24 28 58 99
99 1 31 50 88 79 65 29 42 98 5 91 5 7 50 8 69 43 93 60
86 52 68 87 33 74 22 13 65 2 6 45 21 22 29 67 37 26 85 39
71 97 19 60 53 95 7 96 12 93 26 48 75 65 45 96 39 72 88 97
65 65 61 54 46 60 67 68 67 67 81 92 90 92 19 30 87 27 94 48
86 89 3 44 63 57 38 73 60 70 48 63 75 17 83 70 35 24 76 41
5 15 98 71 46 34 69 26 68 60 41 74 48 54 20 64 1 79 45 19
54 86 46 11 92 1 65 5 8 81 10 94 16 65 20 27 76 72 89 23
23 61 39 91 9 5 81 43 7 99 61 2 69 98 39 92 48 73 29 42
4 95 32 90 7 18 24 15 39 12 76 19 24 6 80 15 78 85 46 3
74 26 82 62 46 46 33 48 18 65 37 2 28 94 59 42 27 92 20 61

比较次数为：0
移动次数为： 0

排序后：

1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 5 5
5 5 5 5 5 5 6 6 6 7 7 7 7 7 7 7 8 8 8 8
8 9 9 9 9 10 10 10 10 10 10 10 11 11 11 11 12 12 12 13
13 13 13 13 14 15 15 15 15 16 16 16 16 16 16 16 16 16 17 17
17 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20
20 21 21 21 22 22 22 23 23 23 23 23 24 24 24 24 24 24 25 25
25 25 25 25 26 26 26 26 26 26 26 26 27 27 27 27 27 27 27 28
28 28 28 28 29 29 29 29 29 29 29 30 30 31 31 32 32 32 33 33
33 33 33 33 34 34 34 34 34 35 35 35 35 36 36 36 36 36 36 37
37 37 37 37 37 37 37 38 38 38 38 38 39 39 39 39 39 39 39 39
39 40 40 40 41 41 41 41 41 41 42 42 42 42 43 43 43 43 43 44
44 44 45 45 45 45 46 46 46 46 46 46 46 46 46 47 48 48 48 48
48 48 48 48 49 49 50 50 50 50 51 51 51 52 52 53 53 53 53 53
53 54 54 54 54 54 54 54 54 54 55 56 56 56 56 57 57 57 57 58
58 58 58 58 58 59 59 59 59 59 59 60 60 60 60 60 60 60 60 61
61 61 61 61 61 62 62 62 62 63 63 63 63 63 63 64 64 64 64 64
64 65 65 65 65 65 65 65 65 65 65 66 66 66 67 67 67 67 67 67
67 68 68 68 68 68 69 69 69 69 69 70 70 70 71 71 71 71 71 71
72 72 72 72 72 73 73 73 73 73 73 74 74 74 74 74 74 74 74 75
75 75 76 76 76 76 76 76 77 77 77 77 77 78 78 78 78 78 78 79
79 79 80 80 80 81 81 81 81 81 81 81 81 81 81 82 82 82 83 83
83 83 83 84 84 85 85 85 85 85 85 85 86 86 86 86 87 87 87 87
87 87 88 88 88 88 89 89 89 89 89 90 90 90 90 90 91 91 91 91
91 92 92 92 92 92 92 92 92 92 93 93 93 93 94 94 94 94 94 94
94 95 95 95 95 96 96 97 97 98 98 98 98 99 99 99 99 99 99 99

比较次数为：311232
移动次数为： 184560

D:visual studio 2017数据结构Sort_experiment4DebugSort_experiment4.exe (进程 16184)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口…

分析：

• 稳定排序
• 用于顺序结构和链式结构
• 移动次数多，n较大时不适合

快速排序

• 将待排序记录存储在n个大小的存储单元中
• 从n个记录中取一个记录作为枢轴记录（一般取第一个记录），然后以记录为轴，比它大的记录移动到右边，比它小的记录移动到左边，再将从左边开始找比枢轴大的记录移动到右边（交替执行两个操作，直到遍历整个表，最后将枢轴记录放到枢轴位置，形成两个子表，再对字表进行重复操作，直到字表只剩下一个记录，此时排序完成
• 第一趟排序中，将枢轴记录(r[1]放在缓存单元r[0]中，获取顺序存储结构的上界high和下界low，选定枢轴后，从该表的表右侧向左开始搜索，先找到第一比枢轴记录小的记录放到low（r[1])（若high位置的记录>=枢轴记录则没有找到，将high 左移（-1),否则将high位置记录移动到low位置）在从左边向右寻找第一个比枢轴记录大的记录，移动到high位置（若low位置的记录<=枢轴记录则找不到，将low右移动，否则将low位置的记录移动到high位置）,重复两个操作，直到遍历了整个表，再将枢轴记录放到枢轴位置
• 接下来每一趟对两个字进行重复操作

QuickSort.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#pragma once
#include"Struct.h"

int Partition(Sqlist1 &L, int low, int high) {
	L.r[0] = L.r[low]; //将第一个记录暂存在缓存单元
	int protkey = L.r[low].key; //枢轴记录的key值
	while (low < high) {
		L.countCompare++;
		while (low < high && L.r[high].key >= protkey) {   //找出右边第一个比key的的记录的记录
			L.countCompare++;
			high--;
		}
		L.countCompare++;
		L.r[low] = L.r[high];  //将右边第一个小于prokey的记录移动到low位置
		L.countMove++;
		while (low < high && L.r[low].key <= protkey) {
			L.countCompare++;
			low++; 
		}
		L.countCompare++;
		L.r[high] = L.r[low];  //将左边第一个大于prokey的记录移动到高端high位置
		L.countMove++;
	}
	L.countCompare++;
	L.r[low] = L.r[0]; //当low == high 时， 将枢轴记录放到中间位置
	L.countMove++;

	return low; //返回枢轴位置的下标
}

void QSort(Sqlist1 &L, int low, int high) {
	L.countCompare++;
	if (low < high) {
		int prvotLocal = Partition(L, low, high);  //取枢轴记录的下标
		cout << endl;
		ShowList(L);
		QSort(L, low, prvotLocal - 1); //对左子表递归排序
		QSort(L, prvotLocal + 1, high); //对右子表递归排序
	}
}

void QuickSort(Sqlist1 & L) {
	QSort(L, 1, L.length);  //对顺序表调用递归函数
}

int Partition(Sqlist2 &L, int low, int high) {
	L.r[0] = L.r[low]; //将第一个记录暂存在缓存单元
	int protkey = L.r[low].key; //枢轴记录的key值
	while (low < high) {
		L.countCompare++;
		while (low < high && L.r[high].key >= protkey) {   //找出右边第一个比key的的记录的记录
			L.countCompare++;
			high--;
		}
		L.countCompare++;
		L.r[low] = L.r[high];  //将右边第一个小于prokey的记录移动到low位置
		L.countMove++;
		while (low < high && L.r[low].key <= protkey) {
			L.countCompare++;
			low++;
		}
		L.countCompare++;
		L.r[high] = L.r[low];  //将左边第一个大于prokey的记录移动到高端high位置
		L.countMove++;
	}
	L.countCompare++;
	L.r[low] = L.r[0]; //当low == high 时， 将枢轴记录放到中间位置
	L.countMove++;
	return low; //返回枢轴位置的下标
}

void QSort(Sqlist2 &L, int low, int high) {
	L.countCompare++;
	if (low < high) {
		int prvotLocal = Partition(L, low, high);  //取枢轴记录的下标
		QSort(L, low, prvotLocal - 1); //对左子表递归排序
		QSort(L, prvotLocal + 1, high); //对右子表递归排序
	}
}

int Partition(Sqlist3 &L, int low, int high) {
	L.r[0] = L.r[low]; //将第一个记录暂存在缓存单元
	int protkey = L.r[low].key; //枢轴记录的key值
	while (low < high) {
		L.countCompare++;
		while (low < high && L.r[high].key >= protkey) {   //找出右边第一个比key的的记录的记录
			L.countCompare++;
			high--;
		}
		L.countCompare++;
		L.r[low] = L.r[high];  //将右边第一个小于prokey的记录移动到low位置
		L.countMove++;
		while (low < high && L.r[low].key <= protkey) {
			L.countCompare++;
			low++;
		}
		L.countCompare++;
		L.r[high] = L.r[low];  //将左边第一个大于prokey的记录移动到高端high位置
		L.countMove++;
	}
	L.countCompare++;
	L.r[low] = L.r[0]; //当low == high 时， 将枢轴记录放到中间位置
	L.countMove++;
	return low; //返回枢轴位置的下标
}

void QSort(Sqlist3 &L, int low, int high) {
	L.countCompare++;
	if (low < high) {
		int prvotLocal = Partition(L, low, high);  //取枢轴记录的下标
		QSort(L, low, prvotLocal - 1); //对左子表递归排序
		QSort(L, prvotLocal + 1, high); //对右子表递归排序
	}
}

void QuickSort(Sqlist3 & L) {
	QSort(L, 1, L.length);  //对顺序表调用递归函数
}

void QuickSort(Sqlist2 & L) {
	QSort(L, 1, L.length);  //对顺序表调用递归函数
}
void OperationQuickSort() {
	Sqlist1 L1;
	CreateList(L1);
	cout << "n排序前： n" << endl;
	ShowList(L1);
	cout << endl;
	cout << "n排序后： n" << endl;
	QuickSort(L1);
	ShowList(L1);
	Sqlist2 L2;
	CreateList(L2);
	cout << "n排序前： n" << endl;
	ShowList(L2);
	cout << endl;
	cout << "n排序后： n" << endl;
	QuickSort(L2);
	ShowList(L2);
	Sqlist3 L3;
	CreateList(L3);
	cout << "n排序前： n" << endl;
	ShowList(L3);
	cout << endl;
	cout << "n排序后： n" << endl;
	QuickSort(L3);
	ShowList(L3);
}

result

排序前：

40 32 60 65 57 83 18 2 10 2 10 83 40 15 25 65 0 77 19 14

比较次数为：0
移动次数为： 0

排序后：

14 32 19 0 25 15 18 2 10 2 10 40 40 83 83 65 57 77 65 60

比较次数为：39
移动次数为： 13

10 2 10 0 2 14 18 15 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：66
移动次数为： 24

2 2 10 0 10 14 18 15 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：75
移动次数为： 27

0 2 2 10 10 14 18 15 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：86
移动次数为： 32

0 2 2 10 10 14 18 15 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：92
移动次数为： 35

0 2 2 10 10 14 15 18 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：105
移动次数为： 38

0 2 2 10 10 14 15 18 19 25 32 40 40 83 83 65 57 77 65 60

比较次数为：113
移动次数为： 41

0 2 2 10 10 14 15 18 19 25 32 40 40 83 83 65 57 77 65 60

比较次数为：127
移动次数为： 44

0 2 2 10 10 14 15 18 19 25 32 40 40 60 83 65 57 77 65 83

比较次数为：139
移动次数为： 47

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 83 77 65 83

比较次数为：152
移动次数为： 52

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 83 77 65 83

比较次数为：161
移动次数为： 55

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 65 77 83 83

比较次数为：169
移动次数为： 58

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 65 77 83 83

比较次数为：175
移动次数为： 61
0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 65 77 83 83

比较次数为：179
移动次数为： 61

排序前：

73 44 62 54 99 83 75 29 86 57 31 23 52 38 71 38 36 89 58 85
33 19 88 2 9 9 19 19 92 42 94 14 16 4 92 7 3 69 23 38
74 33 2 5 11 54 63 98 26 8 73 9 0 90 49 92 50 73 67 56
32 51 0 72 27 43 62 84 59 31 39 83 85 42 41 83 42 39 33 69
88 62 3 52 9 37 93 71 68 97 76 75 63 27 75 89 14 65 50 0

比较次数为：0
移动次数为： 0

排序后：

0 0 0 2 2 3 3 4 5 7 8 9 9 9 9 11 14 14 16 19
19 19 23 23 26 27 27 29 31 31 32 33 33 33 36 37 38 38 38 39
39 41 42 42 42 43 44 49 50 50 51 52 52 54 54 56 57 58 59 62
62 62 63 63 65 67 68 69 69 71 71 72 73 73 73 74 75 75 75 76
83 83 83 84 85 85 86 88 88 89 89 90 92 92 92 93 94 97 98 99

比较次数为：1368
移动次数为： 396

排序前：

73 44 62 54 99 83 75 29 86 57 31 23 52 38 71 38 36 89 58 85
33 19 88 2 9 9 19 19 92 42 94 14 16 4 92 7 3 69 23 38
74 33 2 5 11 54 63 98 26 8 73 9 0 90 49 92 50 73 67 56
32 51 0 72 27 43 62 84 59 31 39 83 85 42 41 83 42 39 33 69
88 62 3 52 9 37 93 71 68 97 76 75 63 27 75 89 14 65 50 0
9 37 42 5 58 24 17 44 11 79 81 6 83 54 63 95 46 53 66 66
9 75 65 7 21 60 1 89 30 74 73 63 57 8 1 84 9 19 2 29
84 77 94 38 85 22 7 6 61 80 30 78 65 26 92 41 66 60 41 3
2 2 18 7 29 74 9 7 2 68 72 41 84 80 81 64 49 65 53 80
34 44 34 14 98 42 83 20 55 86 10 71 74 54 75 18 87 89 40 70
42 73 2 34 0 90 71 29 36 51 30 65 35 83 18 23 26 6 35 16
36 10 49 7 31 92 70 8 51 79 90 74 48 39 10 24 43 54 42 17
56 43 30 6 98 23 2 29 4 8 80 87 23 56 46 29 72 50 0 50
99 30 45 31 84 35 46 17 25 68 94 15 96 75 16 67 55 34 29 59
1 99 21 19 54 96 12 65 37 58 97 3 45 69 71 88 23 27 63 6
51 80 49 92 21 79 26 36 92 6 96 85 63 95 63 16 32 81 77 84
83 14 97 53 57 8 94 6 52 17 52 81 15 18 81 15 6 13 94 27
31 6 20 52 85 49 51 47 86 18 91 93 41 44 72 73 1 42 20 13
67 71 7 18 84 26 48 1 7 74 29 79 83 86 67 44 0 7 27 0
74 88 91 77 19 78 29 97 7 13 45 16 13 55 26 17 7 28 96 33
88 90 39 18 57 82 93 88 58 50 39 54 15 28 65 92 42 75 82 49
94 48 19 27 41 64 75 4 38 36 26 40 62 85 39 96 88 10 8 49
50 26 9 14 90 86 57 1 9 95 45 8 47 87 77 67 51 62 56 94
20 38 89 21 84 20 79 90 8 2 6 34 48 80 55 39 41 62 95 9
96 61 35 47 76 54 6 96 51 45 9 61 25 43 91 85 86 17 77 32

比较次数为：0
移动次数为： 0

排序后：

0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2
2 2 3 3 3 3 4 4 4 5 5 6 6 6 6 6 6 6 6 6
6 6 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8
8 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 11 11 12
13 13 13 13 14 14 14 14 14 15 15 15 15 16 16 16 16 16 17 17
17 17 17 17 18 18 18 18 18 18 18 19 19 19 19 19 19 19 20 20
20 20 20 21 21 21 21 22 23 23 23 23 23 23 24 24 25 25 26 26
26 26 26 26 26 26 27 27 27 27 27 27 28 28 29 29 29 29 29 29
29 29 29 30 30 30 30 30 31 31 31 31 31 32 32 32 33 33 33 33
34 34 34 34 34 35 35 35 35 36 36 36 36 36 37 37 37 38 38 38
38 38 38 39 39 39 39 39 39 39 40 40 41 41 41 41 41 41 41 42
42 42 42 42 42 42 42 42 43 43 43 43 44 44 44 44 44 45 45 45
45 45 46 46 46 47 47 47 48 48 48 48 49 49 49 49 49 49 49 50
50 50 50 50 50 51 51 51 51 51 51 51 52 52 52 52 52 53 53 53
54 54 54 54 54 54 54 54 55 55 55 55 56 56 56 56 57 57 57 57
57 58 58 58 58 59 59 60 60 61 61 61 62 62 62 62 62 62 63 63
63 63 63 63 63 64 64 65 65 65 65 65 65 65 66 66 66 67 67 67
67 67 68 68 68 69 69 69 70 70 71 71 71 71 71 71 72 72 72 72
73 73 73 73 73 73 74 74 74 74 74 74 74 75 75 75 75 75 75 75
75 76 76 77 77 77 77 77 78 78 79 79 79 79 79 80 80 80 80 80
80 81 81 81 81 81 82 82 83 83 83 83 83 83 83 83 84 84 84 84
84 84 84 84 85 85 85 85 85 85 85 86 86 86 86 86 86 87 87 87
88 88 88 88 88 88 88 89 89 89 89 89 90 90 90 90 90 90 91 91
91 92 92 92 92 92 92 92 92 93 93 93 94 94 94 94 94 94 94 95
95 95 95 96 96 96 96 96 96 96 97 97 97 97 98 98 98 99 99 99

比较次数为：9030
移动次数为： 2374

D:visual studio 2017数据结构Sort_experiment4DebugSort_experiment4.exe (进程 21528)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口…

分析

• 不稳定算法，一位无顺序交换
• 适合顺序结构，不适合链式结构
• 适合n大且无序

简单选择排序

• 将待排序的的记录中逐个选择关键字最小的记录，按升序排在顺序序列，最后，遍历完所有记录后得到一个升序表
• 数组实现：
• 将待排序的n个记录放在数组中，从第一个记录开始进行n-1趟排序
• 每一趟排序用局部变量k 获取 i位置的记录的下标，再用k与后续记录的记录逐个比较，如果 r[k]较大则更新k为较小记录的下标，遍历数组，最后找出该趟的最小记录下标放在k，如果k位置不是i位置则将两个位置的记录交换，实现i位置存储最小记录

SimpleInsertSort.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#pragma once
#include"Struct.h"

void SelectSort(Sqlist1 &L) {
	for (int i = 1; i < L.length; i++) {
		L.countCompare++;
		int k = i;
		for (int j = i + 1; j <= L.length; j++) {
			L.countCompare++;
			if (L.r[j].key < L.r[k].key)
				k = j;
			L.countCompare++;
		}
		L.countCompare++;
		if (k != i) {
			Redtype t = L.r[i];
			L.countMove++;
			L.r[i] = L.r[k];
			L.countMove++;
			L.r[k] = t;
			L.countMove++;
		}
		L.countCompare++;
		cout << endl << "第 " << i << " 趟排序 ：" << endl;
		ShowList(L);
	}
	L.countCompare++;
}

void SelectSort(Sqlist2 &L) {
	for (int i = 1; i < L.length; i++) {
		L.countCompare++;
		int k = i;
		for (int j = i + 1; j <= L.length; j++) {
			L.countCompare++;
			if (L.r[j].key < L.r[k].key)
				k = j;
			L.countCompare++;
		}
		L.countCompare++;
		if (k != i) {
			Redtype t = L.r[i];
			L.countMove++;
			L.r[i] = L.r[k];
			L.countMove++;
			L.r[k] = t;
			L.countMove++;
		}
		L.countCompare++;
	}
	L.countCompare++;
}
void SelectSort(Sqlist3 &L) {
	for (int i = 1; i < L.length; i++) {
		L.countCompare++;
		int k = i;
		for (int j = i + 1; j <= L.length; j++) {
			L.countCompare++;
			if (L.r[j].key < L.r[k].key)
				k = j;
			L.countCompare++;
		}
		L.countCompare++;
		if (k != i) {
			Redtype t = L.r[i];
			L.countMove++;
			L.r[i] = L.r[k];
			L.countMove++;
			L.r[k] = t;
			L.countMove++;
		}
		L.countCompare++;
	}
	L.countCompare++;
}
void OperationSelectSort() {
	cout << "n********** 20个随机数**********n";
	Sqlist1 L1;
	CreateList(L1);
	cout << "n排序前： n" << endl;
	ShowList(L1);
	cout << endl;
	cout << "n排序后： n" << endl;
	SelectSort(L1);
	ShowList(L1);

	cout << "nn********** 100个随机数**********n";
	Sqlist2 L2;
	CreateList(L2);
	cout << "n排序前： n" << endl;
	ShowList(L2);
	cout << endl;
	cout << "n排序后： n" << endl;
	SelectSort(L2);
	ShowList(L2);

	cout << "nn********** 500个随机数**********n";
	Sqlist3 L3;
	CreateList(L3);
	cout << "n排序前： n" << endl;
	ShowList(L3);
	cout << endl;
	cout << "n排序后： n" << endl;
	SelectSort(L3);
	ShowList(L3);
}

结果：

********** 20个随机数**********

排序前：

45 88 78 47 27 5 33 21 25 28 43 96 22 70 96 68 98 68 94 73

比较次数为：0
移动次数为： 0

排序后：

第 1 趟排序 ：
5 88 78 47 27 45 33 21 25 28 43 96 22 70 96 68 98 68 94 73

比较次数为：41
移动次数为： 3

第 2 趟排序 ：
5 21 78 47 27 45 33 88 25 28 43 96 22 70 96 68 98 68 94 73

比较次数为：80
移动次数为： 6

第 3 趟排序 ：
5 21 22 47 27 45 33 88 25 28 43 96 78 70 96 68 98 68 94 73

比较次数为：117
移动次数为： 9

第 4 趟排序 ：
5 21 22 25 27 45 33 88 47 28 43 96 78 70 96 68 98 68 94 73

比较次数为：152
移动次数为： 12

第 5 趟排序 ：
5 21 22 25 27 45 33 88 47 28 43 96 78 70 96 68 98 68 94 73

比较次数为：185
移动次数为： 12

第 6 趟排序 ：
5 21 22 25 27 28 33 88 47 45 43 96 78 70 96 68 98 68 94 73

比较次数为：216
移动次数为： 15

第 7 趟排序 ：
5 21 22 25 27 28 33 88 47 45 43 96 78 70 96 68 98 68 94 73

比较次数为：245
移动次数为： 15

第 8 趟排序 ：
5 21 22 25 27 28 33 43 47 45 88 96 78 70 96 68 98 68 94 73

比较次数为：272
移动次数为： 18

第 9 趟排序 ：
5 21 22 25 27 28 33 43 45 47 88 96 78 70 96 68 98 68 94 73

比较次数为：297
移动次数为： 21

第 10 趟排序 ：
5 21 22 25 27 28 33 43 45 47 88 96 78 70 96 68 98 68 94 73

比较次数为：320
移动次数为： 21

第 11 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 96 78 70 96 88 98 68 94 73

比较次数为：341
移动次数为： 24

第 12 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 68 78 70 96 88 98 96 94 73

比较次数为：360
移动次数为： 27

第 13 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 68 70 78 96 88 98 96 94 73

比较次数为：377
移动次数为： 30

第 14 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 68 70 73 96 88 98 96 94 78

比较次数为：392
移动次数为： 33

第 15 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 98 96 94 96

比较次数为：405
移动次数为： 36

第 16 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 98 96 94 96

比较次数为：416
移动次数为： 36

第 17 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 94 96 98 96

比较次数为：425
移动次数为： 39

第 18 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 94 96 98 96

比较次数为：432
移动次数为： 39

第 19 趟排序 ：
5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 94 96 96 98

比较次数为：437
移动次数为： 42
5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 94 96 96 98

比较次数为：438
移动次数为： 42

********** 100个随机数**********

排序前：

49 36 42 42 42 31 77 93 37 79 95 40 93 16 21 38 48 26 24 30
12 80 81 23 18 13 38 75 29 97 2 4 61 76 55 8 20 70 57 40
32 70 61 23 43 16 79 36 35 1 92 29 38 1 56 33 29 4 15 29
27 72 80 86 60 34 7 98 7 26 35 40 41 72 59 29 31 68 7 97
94 2 49 25 4 66 21 90 90 50 0 69 84 70 24 40 56 11 44 58

比较次数为：0
移动次数为： 0

排序后：

0 1 1 2 2 4 4 4 7 7 7 8 11 12 13 15 16 16 18 20
21 21 23 23 24 24 25 26 26 27 29 29 29 29 29 30 31 31 32 33
34 35 35 36 36 37 38 38 38 40 40 40 40 41 42 42 42 43 44 48
49 49 50 55 56 56 57 58 59 60 61 61 66 68 69 70 70 70 72 72
75 76 77 79 79 80 80 81 84 86 90 90 92 93 93 94 95 97 97 98

比较次数为：10198
移动次数为： 285

********** 500个随机数**********

排序前：

49 36 42 42 42 31 77 93 37 79 95 40 93 16 21 38 48 26 24 30
12 80 81 23 18 13 38 75 29 97 2 4 61 76 55 8 20 70 57 40
32 70 61 23 43 16 79 36 35 1 92 29 38 1 56 33 29 4 15 29
27 72 80 86 60 34 7 98 7 26 35 40 41 72 59 29 31 68 7 97
94 2 49 25 4 66 21 90 90 50 0 69 84 70 24 40 56 11 44 58
35 87 1 55 4 48 46 46 90 71 60 6 60 19 53 42 95 14 61 92
20 54 74 53 63 20 68 75 75 17 64 59 7 70 39 27 48 10 57 26
20 18 90 67 87 80 35 72 3 34 57 61 93 61 60 96 69 41 14 85
31 4 6 40 64 79 91 18 55 4 72 22 57 20 46 29 49 58 75 68
16 81 53 28 63 91 62 81 75 78 26 76 90 63 87 75 18 73 63 67
27 19 15 48 40 86 35 58 71 33 98 20 97 57 79 8 76 3 92 30
51 99 54 74 5 91 70 67 45 9 22 98 49 86 59 89 47 11 61 36
33 20 3 45 12 30 73 35 61 61 11 54 77 27 20 17 83 96 63 52
97 26 65 18 97 74 47 62 24 48 89 94 70 80 38 0 59 53 22 88
37 74 54 37 35 11 36 96 18 57 83 98 94 29 15 81 63 94 75 45
52 41 10 11 0 48 96 99 11 42 19 31 75 58 70 59 7 90 72 78
88 94 28 41 55 6 20 58 94 32 12 52 51 25 48 17 61 97 76 28
39 96 75 8 62 32 18 32 83 29 66 85 58 68 40 45 41 72 64 1
92 44 41 62 76 92 84 55 14 74 94 69 25 12 34 79 76 61 2 0
17 48 81 20 16 15 39 78 80 35 52 47 7 99 54 18 21 92 28 85
71 36 75 36 79 73 4 20 79 12 6 76 37 89 42 99 98 10 56 36
72 56 55 78 80 69 24 66 12 62 87 15 95 79 90 12 19 20 50 60
55 98 91 66 9 59 0 90 32 2 67 84 16 23 70 27 3 1 33 13
14 37 58 37 8 38 87 73 31 21 99 1 6 35 60 15 95 12 71 73
93 51 92 48 86 47 87 10 55 84 12 67 63 35 7 59 44 25 27 67

比较次数为：0
移动次数为： 0

排序后：

0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 3 3 3 3 4
4 4 4 4 4 4 5 6 6 6 6 6 7 7 7 7 7 7 7 8
8 8 8 9 9 10 10 10 10 11 11 11 11 11 11 12 12 12 12 12
12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16
16 17 17 17 17 18 18 18 18 18 18 18 18 19 19 19 19 20 20 20
20 20 20 20 20 20 20 20 20 21 21 21 21 22 22 22 23 23 23 24
24 24 24 25 25 25 25 26 26 26 26 26 27 27 27 27 27 27 28 28
28 28 29 29 29 29 29 29 29 29 30 30 30 31 31 31 31 31 32 32
32 32 32 33 33 33 33 34 34 34 35 35 35 35 35 35 35 35 35 35
36 36 36 36 36 36 36 37 37 37 37 37 37 38 38 38 38 38 39 39
39 40 40 40 40 40 40 40 41 41 41 41 41 41 42 42 42 42 42 42
43 44 44 44 45 45 45 45 46 46 46 47 47 47 47 48 48 48 48 48
48 48 48 48 49 49 49 49 50 50 51 51 51 52 52 52 52 53 53 53
53 54 54 54 54 54 55 55 55 55 55 55 55 55 56 56 56 56 57 57
57 57 57 57 58 58 58 58 58 58 58 59 59 59 59 59 59 59 60 60
60 60 60 60 61 61 61 61 61 61 61 61 61 61 62 62 62 62 62 63
63 63 63 63 63 63 64 64 64 65 66 66 66 66 67 67 67 67 67 67
68 68 68 68 69 69 69 69 70 70 70 70 70 70 70 70 71 71 71 71
72 72 72 72 72 72 72 73 73 73 73 73 74 74 74 74 74 75 75 75
75 75 75 75 75 75 75 76 76 76 76 76 76 76 77 77 78 78 78 78
79 79 79 79 79 79 79 79 80 80 80 80 80 80 81 81 81 81 81 83
83 83 84 84 84 84 85 85 85 86 86 86 86 87 87 87 87 87 87 88
88 89 89 89 90 90 90 90 90 90 90 90 91 91 91 91 92 92 92 92
92 92 92 93 93 93 93 94 94 94 94 94 94 94 95 95 95 95 96 96
96 96 96 97 97 97 97 97 97 98 98 98 98 98 98 99 99 99 99 99

比较次数为：250998
移动次数为： 1473

D:visual studio 2017数据结构Sort_experiment4DebugSort_experiment4.exe (进程 19964)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口…

分析：

• 该算法稳定
• 比较次数增多，移动次数减少，当单个记录占用空间大的时候适合使用
• 适用于链式结构

堆排序

• 堆的性质：n个元素序列{k1,k2,k3,kn} 中ki >=k2i and ki >=k2i+1（大根堆，双亲结点大于孩子结点）或者小根堆
• 大根堆定义：非终端叶字结点的值均不小于其孩子结点，上大下小
• 小根堆定义：非终端叶子结点的值均不大于其孩子结点，上小下大

堆排序思想：

• 将无序的n个记录排成无序的完全二叉树
• 初建堆：调整法构造成大根堆
• 对于n个结点的序列，将根结点与最后一个结点交换，把最大值的记录放在序列尾部，此时破环剩余的前n-1大根堆结构，再次调整堆成大根堆，再对n-1个结点的大根堆进行交换操作，直到最后的的子树剩下一个记录为止，此时无序序列成为升序序列
• 进行n-1次堆排序就排成升序序列

1筛选法调整堆

• 在交换首位记录后，除了根结点都满足大根堆的性质，从上往下对一条路的结点进行调整，将左右子树的较大值的结点与根结点进行交换，再对该子树进行相同的操作，直到叶子结点为止。像筛子一样把大的往上，小的往下，成为新的大根堆

2建初堆

• 再n个结点的完全二叉树中，大于n/2的结点都是叶子，因此以这些结点为根的子树都是堆，所以，从n/2-1的结点开始往前调整为堆，即调整n/2次可建立一个初堆
  *每一趟调整中，s记录根节点的地址，先将新的根结点的值暂存到缓存单元rc，从缓存单元的结点的值与孩子结点中的较大值比较，如果比孩子结点的值大即停止比较，已成大根堆，退出本次调整堆操作；如果比孩子结点的值小，则将孩子结点的较大值填到根节点位置，孩子结点的位置作为新的根结点进行堆该新子树进行调整，s更新为新的根节点的下标，直到新的子树满足大根堆为止
  *完成调整n/2次后无序序列成为大根堆

HeapSortion.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#pragma once
#include"Struct.h"

//调整堆
void HeapAdjust(Sqlist1 &L, int s, int m) {
	Redtype rigister = L.r[s];  //存储要调整的二叉树的起始根结点
	for (int i = 2 * s; i <= m; i *= 2) {
		L.countCompare++;
		if (i < m &&L.r[i].key < L.r[i + 1].key) //获取孩子结点中key值较大的结点
			i++;  
		L.countCompare++;
		L.countCompare++;
		if (rigister.key >= L.r[i].key) //当前子树根节点key值比孩子结点都大，已经为大根堆
			break;
		L.r[s] = L.r[i]; //将key值大的孩子结点移动到key值较小的根结点原来的位置
		L.countMove++;
		s = i;	//找不到合适的位置，则以当前孩子结点作为根结点在其子树根结点，继续查找位置，直到叶字找到或者到了叶子结点
	}
	L.countCompare++;
	L.r[s] = rigister;
	L.countMove++;
}

//建初堆
void Createheap(Sqlist1 &L) {
	int number = L.length;
	for (int i = number / 2; i > 0; --i) {
		L.countCompare++;
		HeapAdjust(L, i, number);
	}
	L.countCompare++;
}

//堆排序
void HeapSort(Sqlist1 &L) {
	Createheap(L);
	for (int i = L.length; i > 1; i--) {  
		L.countCompare++;
		Redtype rigister = L.r[1];  //根结点与子树的最后一个叶子结点交换记录
		L.countMove++;
		L.r[1] = L.r[i];	
		L.countMove++;
		L.r[i] = rigister;
		L.countMove++;
		HeapAdjust(L, 1, i - 1); //将剩下的无序序列重新调整为大根堆序列
	}
	L.countCompare++;
}

//调整堆
void HeapAdjust(Sqlist2 &L, int s, int m) {
	Redtype rigister = L.r[s];  //存储要调整的二叉树的起始根结点
	for (int i = 2 * s; i <= m; i *= 2) {
		L.countCompare++;
		if (i < m &&L.r[i].key < L.r[i + 1].key) //获取孩子结点中key值较大的结点
			i++;
		L.countCompare++;
		L.countCompare++;
		if (rigister.key >= L.r[i].key) //当前子树根节点key值比孩子结点都大，已经为大根堆
			break;
		L.r[s] = L.r[i]; //将key值大的孩子结点移动到key值较小的根结点原来的位置
		L.countMove++;
		s = i;	//找不到合适的位置，则以当前孩子结点作为根结点在其子树根结点，继续查找位置，直到叶字找到或者到了叶子结点
	}
	L.countCompare++;
	L.r[s] = rigister;
	L.countMove++;
}

//建初堆
void Createheap(Sqlist2 &L) {
	int number = L.length;
	for (int i = number / 2; i > 0; --i) {
		L.countCompare++;
		HeapAdjust(L, i, number);
	}
	L.countCompare++;
}

//堆排序
void HeapSort(Sqlist2 &L) {
	Createheap(L);
	for (int i = L.length; i > 1; i--) {
		L.countCompare++;
		Redtype rigister = L.r[1];  //根结点与子树的最后一个叶子结点交换记录
		L.countMove++;
		L.r[1] = L.r[i];
		L.countMove++;
		L.r[i] = rigister;
		L.countMove++;
		HeapAdjust(L, 1, i - 1); //将剩下的无序序列重新调整为大根堆序列
	}
	L.countCompare++;
}

//调整堆
void HeapAdjust(Sqlist3 &L, int s, int m) {
	Redtype rigister = L.r[s];  //存储要调整的二叉树的起始根结点
	for (int i = 2 * s; i <= m; i *= 2) {
		L.countCompare++;
		if (i < m &&L.r[i].key < L.r[i + 1].key) //获取孩子结点中key值较大的结点
			i++;
		L.countCompare++;
		L.countCompare++;
		if (rigister.key >= L.r[i].key) //当前子树根节点key值比孩子结点都大，已经为大根堆
			break;
		L.r[s] = L.r[i]; //将key值大的孩子结点移动到key值较小的根结点原来的位置
		L.countMove++;
		s = i;	//找不到合适的位置，则以当前孩子结点作为根结点在其子树根结点，继续查找位置，直到叶字找到或者到了叶子结点
	}
	L.countCompare++;
	L.r[s] = rigister;
	L.countMove++;
}

//建初堆
void Createheap(Sqlist3 &L) {
	int number = L.length;
	for (int i = number / 2; i > 0; --i) {
		L.countCompare++;
		HeapAdjust(L, i, number);
	}
	L.countCompare++;
}

//堆排序
void HeapSort(Sqlist3 &L) {
	Createheap(L);
	for (int i = L.length; i > 1; i--) {
		L.countCompare++;
		Redtype rigister = L.r[1];  //根结点与子树的最后一个叶子结点交换记录
		L.countMove++;
		L.r[1] = L.r[i];
		L.countMove++;
		L.r[i] = rigister;
		L.countMove++;
		HeapAdjust(L, 1, i - 1); //将剩下的无序序列重新调整为大根堆序列
	}
	L.countCompare++;
}
void OperationHeapSort() {
	cout << "n********** 20个随机数**********n";
	Sqlist1 L1;
	CreateList(L1);
	cout << "n排序前： n" << endl;
	ShowList(L1);
	cout << endl;
	cout << "n排序后： n" << endl;
	HeapSort(L1);
	ShowList(L1);
	cout << "nn********** 100个随机数**********n";
	Sqlist2 L2;
	CreateList(L2);
	cout << "n排序前： n" << endl;
	ShowList(L2);
	cout << endl;
	cout << "n排序后： n" << endl;
	HeapSort(L2);
	ShowList(L2);

	cout << "nn********** 500个随机数**********n";
	Sqlist3 L3;
	CreateList(L3);
	cout << "n排序前： n" << endl;
	ShowList(L3);
	HeapSort(L3);
	cout << endl;
	cout << "n排序后： n" << endl;
	ShowList(L3);
	
}

result

********** 20个随机数**********

排序前：

42 96 98 62 43 16 99 77 46 68 88 90 23 98 79 73 19 66 60 65

比较次数为：0
移动次数为： 0

排序后：

16 19 23 42 43 46 60 62 65 66 68 73 77 79 88 90 96 98 98 99

比较次数为：231
移动次数为： 134

********** 100个随机数**********

排序前：

42 96 98 62 43 16 99 77 46 68 88 90 23 98 79 73 19 66 60 65
87 31 41 51 41 19 13 95 54 86 67 97 98 79 4 40 73 10 12 81
83 1 61 88 86 26 58 19 35 41 47 43 98 98 36 46 26 5 95 93
73 52 34 19 63 68 69 63 13 76 76 47 68 14 28 36 91 55 31 39
33 18 65 29 25 36 8 43 64 2 39 9 25 18 22 77 59 51 13 62

比较次数为：0
移动次数为： 0

排序后：

1 2 4 5 8 9 10 12 13 13 13 14 16 18 18 19 19 19 19 22
23 25 25 26 26 28 29 31 31 33 34 35 36 36 36 39 39 40 41 41
41 42 43 43 43 46 46 47 47 51 51 52 54 55 58 59 60 61 62 62
63 63 64 65 65 66 67 68 68 68 69 73 73 73 76 76 77 77 79 79
81 83 86 86 87 88 88 90 91 93 95 95 96 97 98 98 98 98 98 99

比较次数为：1830
移动次数为： 909

********** 500个随机数**********

排序前：

42 96 98 62 43 16 99 77 46 68 88 90 23 98 79 73 19 66 60 65
87 31 41 51 41 19 13 95 54 86 67 97 98 79 4 40 73 10 12 81
83 1 61 88 86 26 58 19 35 41 47 43 98 98 36 46 26 5 95 93
73 52 34 19 63 68 69 63 13 76 76 47 68 14 28 36 91 55 31 39
33 18 65 29 25 36 8 43 64 2 39 9 25 18 22 77 59 51 13 62
60 40 96 53 12 59 26 30 40 37 1 80 40 96 69 43 31 12 18 38
58 88 43 12 30 54 16 9 93 40 96 45 83 71 31 9 13 71 78 47
67 56 65 7 6 97 23 85 44 24 25 85 63 25 7 81 40 66 24 86
17 98 53 33 41 69 99 54 50 39 37 70 6 72 74 90 58 60 69 64
64 78 74 6 49 62 81 76 3 95 9 33 35 74 92 93 29 73 9 21
50 39 38 63 91 45 9 20 72 44 16 67 16 47 72 44 35 35 78 65
35 53 27 12 63 5 30 33 45 61 59 37 23 67 83 71 85 38 1 22
77 62 19 27 62 7 77 44 21 32 93 97 16 24 59 74 5 80 23 10
80 7 9 22 28 71 52 13 51 16 43 42 79 82 4 55 27 6 41 5
23 28 91 99 63 24 9 67 10 42 2 55 25 64 2 61 5 18 34 53
23 19 50 94 3 87 39 7 3 59 42 27 9 85 15 7 18 40 4 32
40 54 72 80 74 12 79 32 46 65 21 36 92 51 63 50 21 51 65 15
83 19 45 34 91 85 43 38 26 33 61 72 80 95 44 9 82 43 0 10
56 21 48 48 54 88 46 44 58 0 66 92 53 10 40 15 1 61 31 19
0 95 91 56 91 38 71 75 73 44 84 92 21 75 56 92 1 9 50 6
16 11 61 61 71 56 43 85 83 69 40 54 46 58 59 38 19 3 13 57
67 44 7 12 14 14 28 9 25 32 56 60 49 16 51 22 24 21 58 21
2 48 42 28 74 54 89 76 94 30 69 80 52 75 39 57 19 69 89 89
18 7 99 56 59 67 71 92 31 37 12 25 64 60 12 68 91 22 28 53
23 83 15 78 81 69 33 15 73 59 67 67 36 54 4 76 32 67 66 89

比较次数为：0
移动次数为： 0

排序后：

0 0 0 1 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 7 7 7 8 9
9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 11 12 12 12
12 12 12 12 12 12 13 13 13 13 13 13 14 14 14 15 15 15 15 15
16 16 16 16 16 16 16 16 17 18 18 18 18 18 18 19 19 19 19 19
19 19 19 19 19 20 21 21 21 21 21 21 21 21 22 22 22 22 22 23
23 23 23 23 23 23 24 24 24 24 24 25 25 25 25 25 25 25 26 26
26 26 27 27 27 27 28 28 28 28 28 28 29 29 30 30 30 30 31 31
31 31 31 31 32 32 32 32 32 33 33 33 33 33 33 34 34 34 35 35
35 35 35 36 36 36 36 36 37 37 37 37 38 38 38 38 38 38 39 39
39 39 39 39 40 40 40 40 40 40 40 40 40 40 41 41 41 41 41 42
42 42 42 42 43 43 43 43 43 43 43 43 43 44 44 44 44 44 44 44
44 45 45 45 45 46 46 46 46 46 47 47 47 47 48 48 48 49 49 50
50 50 50 50 51 51 51 51 51 51 52 52 52 53 53 53 53 53 53 54
54 54 54 54 54 54 54 55 55 55 56 56 56 56 56 56 56 57 57 58
58 58 58 58 58 59 59 59 59 59 59 59 59 60 60 60 60 60 61 61
61 61 61 61 61 62 62 62 62 62 63 63 63 63 63 63 63 64 64 64
64 64 65 65 65 65 65 65 66 66 66 66 67 67 67 67 67 67 67 67
67 67 68 68 68 68 69 69 69 69 69 69 69 69 70 71 71 71 71 71
71 71 72 72 72 72 72 73 73 73 73 73 73 74 74 74 74 74 74 75
75 75 76 76 76 76 76 77 77 77 77 78 78 78 78 79 79 79 79 80
80 80 80 80 80 81 81 81 81 82 82 83 83 83 83 83 83 84 85 85
85 85 85 85 86 86 86 87 87 88 88 88 88 89 89 89 89 90 90 91
91 91 91 91 91 91 92 92 92 92 92 92 93 93 93 93 94 94 95 95
95 95 95 96 96 96 96 97 97 97 98 98 98 98 98 98 99 99 99 99

比较次数为：12585
移动次数为： 5746

D:visual studio 2017数据结构Sort_experiment4DebugSort_experiment4.exe (进程 4100)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口…

分析：

• 算法是不稳定的
• 不可以用于链式存储结构
• 建立堆的时候，进行比较堆的比较操作，当记录数n较小的时候不适用，使用于n较大的适用，性能比一般的插入选择排序快，但是性能比不上快排。

归并排序

• 归并是指将2或多个有序序列进行合并成一个有序表

思想

• 初始序列是由n个记录构造，可以看作n个长度为1的子序列，然后子序列两两合并成[n/2]个子序列，再重复两两合并，直到得到一个长度为n的有序序列。

1，相邻两个序列表的归并

• 将待归并的顺序表从中间划分两个有序的相邻的子表，将两个子表中从头开始取一记录进行比较，将较小者先存入目标表，更新位置计数单元，直到一个子表为空为止
• 将剩余的非空的有序的子表的元素都添加到目标表中
• 实现了两个子表归并

2,归并排序数组实现

• 2路归并将待排序序列表的记录归并并排序到目标序列表中，当待排序表长度为1时候停止排序，长度非1则
• 1，将序列表分为两个字表，先对子表进行递归归并函数，不断层层深入
• 2，将已经递归结束的两个子表的有序序列进行归并

MergingSort.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#pragma once
#include"Struct.h"

void Merge(Sqlist1 R, Sqlist1 &T, int low, int mid, int high) {
	int i = low; int j = mid + 1; int k = low;
	while (i <= mid && j <= high) {  //确定比较范围都在子序列表的范围之内
		T.countCompare++;
		if (R.r[i].key <= R.r[j].key) {
			T.r[k++] = R.r[i++];  //先取值再++,后序列值较大
			T.countMove++;
		}
		else {
			T.r[k++] = R.r[j++]; //先序列值较大
			T.countMove++;
		}
		T.countCompare++;
	}
	T.countCompare++;
	while (i <= mid) {			//将先序序列所有剩余记录刷出
		T.r[k++] = R.r[i++];
		T.countCompare++;
		T.countMove++;
	}
	T.countCompare++;
	while (j <= high) {			//将后续序列所有剩余记录刷出
		T.r[k++] = R.r[j++];
		T.countCompare++;
		T.countMove++;
	}
	T.countCompare++;
}

void MSort(Sqlist1 R, Sqlist1 &T, int low, int high) {
	if (low == high) {  //序列只剩一个元素，已经排序完成，将其存储到引用顺序表中
		T.r[low] = R.r[low];
		T.countMove++;
	}
	else {
		int mid = (low + high) / 2; //获取中间序列值
		Sqlist1 Temp;
		MSort(R, Temp, low, mid);
		MSort(R, Temp, mid + 1, high);
		Merge(Temp, T, low, mid, high);

	}
	T.countCompare++;

}

void MergeSort(Sqlist1 &L) {


	MSort(L, L, 1, L.length);
}

void Merge(Sqlist2 R, Sqlist2 &T, int low, int mid, int high) {
	T.countCompare = R.countCompare;
	T.countMove = R.countMove;
	int i = low; int j = mid + 1; int k = low;
	while (i <= mid && j <= high) {  //确定比较范围都在子序列表的范围之内
		T.countCompare++;
		if (R.r[i].key <= R.r[j].key) {
			T.r[k++] = R.r[i++];  //先取值再++,后序列值较大
			T.countMove++;
		}
		else {
			T.r[k++] = R.r[j++]; //先序列值较大
			T.countMove++;
		}
		T.countCompare++;
	}
	T.countCompare++;
	while (i <= mid) {			//将先序序列所有剩余记录刷出
		T.r[k++] = R.r[i++];
		T.countCompare++;
		T.countMove++;
	}
	T.countCompare++;
	while (j <= high) {			//将后续序列所有剩余记录刷出
		T.r[k++] = R.r[j++];
		T.countCompare++;
		T.countMove++;
	}
	T.countCompare++;
}

void MSort(Sqlist2 R, Sqlist2 &T, int low, int high) {
	if (low == high) {  //序列只剩一个元素，已经排序完成，将其存储到引用顺序表中
		T.r[low] = R.r[low];
		T.countMove++;
	}
	else {
		int mid = (low + high) / 2; //获取中间序列值
		Sqlist2 Temp;
		MSort(R, Temp, low, mid);
		MSort(R, Temp, mid + 1, high);
		Merge(Temp, T, low, mid, high);

	}
	T.countCompare++;

}

void MergeSort(Sqlist2 &L) {


	MSort(L, L, 1, L.length);
}

void Merge(Sqlist3 R, Sqlist3 &T, int low, int mid, int high) {
	int i = low; int j = mid + 1; int k = low;
	while (i <= mid && j <= high) {  //确定比较范围都在子序列表的范围之内
		T.countCompare++;
		if (R.r[i].key <= R.r[j].key) {
			T.r[k++] = R.r[i++];  //先取值再++,后序列值较大
			T.countMove++;
		}
		else {
			T.r[k++] = R.r[j++]; //先序列值较大
			T.countMove++;
		}
		T.countCompare++;
	}
	T.countCompare++;
	while (i <= mid) {			//将先序序列所有剩余记录刷出
		T.r[k++] = R.r[i++];
		T.countCompare++;
		T.countMove++;
	}
	T.countCompare++;
	while (j <= high) {			//将后续序列所有剩余记录刷出
		T.r[k++] = R.r[j++];
		T.countCompare++;
		T.countMove++;
	}
	T.countCompare++;
}

void MSort(Sqlist3 R, Sqlist3 &T, int low, int high) {
	if (low == high) {  //序列只剩一个元素，已经排序完成，将其存储到引用顺序表中
		T.r[low] = R.r[low];
		T.countMove++;
	}
	else {
		int mid = (low + high) / 2; //获取中间序列值
		Sqlist3 Temp;
		MSort(R, Temp, low, mid);
		MSort(R, Temp, mid + 1, high);
		Merge(Temp, T, low, mid, high);

	}
	T.countCompare++;

}

void MergeSort(Sqlist3 &L) {


	MSort(L, L, 1, L.length);
}

void OperationMergeSort() {
	Sqlist1 L1;
	CreateList(L1);
	cout << "n排序前： n" << endl;
	ShowList(L1);
	cout << endl;
	cout << "n排序后： n" << endl;
	MergeSort(L1);
	ShowList(L1);
	Sqlist2 L2;
	CreateList(L2);
	cout << "n排序前： n" << endl;
	ShowList(L2);
	cout << endl;
	cout << "n排序后： n" << endl;
	MergeSort(L2);
	ShowList(L2);
	Sqlist3 L3;
	CreateList(L3);
	cout << "n排序前： n" << endl;
	ShowList(L3);
	cout << endl;
	cout << "n排序后： n" << endl;
	MergeSort(L3);
	ShowList(L3);
}

result

排序前：

81 10 16 66 57 81 81 92 60 43 93 10 57 62 41 73 0 89 75 58

比较次数为：0
移动次数为： 0

排序后：

0 10 10 16 41 43 57 57 58 60 62 66 73 75 81 81 81 89 92 93

比较次数为：43
移动次数为： 20

排序前：

81 10 16 66 57 81 81 92 60 43 93 10 57 62 41 73 0 89 75 58
91 24 80 41 24 68 55 55 49 55 25 9 22 75 55 13 51 34 99 93
62 10 16 86 85 13 71 39 91 56 82 78 91 68 54 74 2 73 46 6
54 15 88 93 18 29 31 70 16 80 28 65 64 11 21 7 95 76 73 82
72 36 33 17 50 34 34 19 3 33 12 17 99 99 70 41 84 84 60 48

比较次数为：0
移动次数为： 0

排序后：

0 2 3 6 7 9 10 10 10 11 12 13 13 15 16 16 16 17 17 18
19 21 22 24 24 25 28 29 31 33 33 34 34 34 36 39 41 41 41 43
46 48 49 50 51 54 54 55 55 55 55 56 57 57 58 60 60 62 62 64
65 66 68 68 70 70 71 72 73 73 73 74 75 75 76 78 80 80 81 81
81 82 82 84 84 85 86 88 89 91 91 91 92 93 93 93 95 99 99 99

比较次数为：414
移动次数为： 201

排序前：

81 10 16 66 57 81 81 92 60 43 93 10 57 62 41 73 0 89 75 58
91 24 80 41 24 68 55 55 49 55 25 9 22 75 55 13 51 34 99 93
62 10 16 86 85 13 71 39 91 56 82 78 91 68 54 74 2 73 46 6
54 15 88 93 18 29 31 70 16 80 28 65 64 11 21 7 95 76 73 82
72 36 33 17 50 34 34 19 3 33 12 17 99 99 70 41 84 84 60 48
36 88 86 32 55 12 53 90 38 79 98 46 64 24 29 65 53 98 52 66
41 41 33 72 22 91 81 86 12 25 26 88 59 6 85 21 66 68 60 54
67 62 12 50 99 86 6 70 43 48 91 51 71 87 24 14 86 23 15 35
6 26 52 13 94 34 55 41 9 39 26 1 25 81 5 91 19 49 4 73
93 93 29 83 93 96 7 7 52 75 54 69 51 69 27 12 44 53 42 99
72 13 7 59 20 76 50 68 46 41 67 38 69 19 20 78 20 93 36 13
70 11 64 44 38 60 47 92 41 57 83 52 60 14 26 81 52 68 75 90
47 54 70 52 37 0 45 23 39 64 4 41 59 11 1 19 7 45 8 18
78 96 34 91 48 62 77 11 18 27 96 72 99 48 66 92 53 54 0 83
54 31 38 66 60 35 7 66 75 30 46 50 78 60 35 17 29 13 58 48
41 38 44 39 24 47 39 61 99 51 73 61 78 81 8 82 79 96 72 94
69 25 28 99 21 63 82 70 70 19 34 85 42 6 9 86 57 40 45 52
93 9 99 70 66 65 12 9 15 84 14 55 29 33 31 37 52 28 54 33
51 96 76 33 31 77 29 18 75 17 40 48 43 94 4 61 90 69 55 92
64 9 31 73 40 93 96 62 78 30 21 95 96 65 26 1 54 20 65 47
4 31 55 90 47 89 98 27 94 8 81 63 47 93 76 78 96 43 36 23
99 95 69 51 78 40 90 84 47 84 96 92 11 71 20 42 75 26 78 68
7 66 98 81 15 78 88 13 8 54 2 99 76 26 39 38 8 3 17 35
4 64 24 46 8 87 1 27 18 85 28 91 96 23 90 95 48 83 29 88
57 58 13 55 0 79 22 35 46 68 55 98 23 39 99 40 88 33 39 90

比较次数为：0
移动次数为： 0

排序后：

0 0 0 0 1 1 1 1 2 2 3 3 4 4 4 4 4 5 6 6
6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 9 9 9 9
9 9 10 10 10 11 11 11 11 11 12 12 12 12 12 12 13 13 13 13
13 13 13 13 14 14 14 15 15 15 15 16 16 16 17 17 17 17 17 18
18 18 18 18 19 19 19 19 19 20 20 20 20 20 21 21 21 21 22 22
22 23 23 23 23 23 24 24 24 24 24 24 25 25 25 25 26 26 26 26
26 26 26 27 27 27 27 28 28 28 28 29 29 29 29 29 29 29 30 30
31 31 31 31 31 31 32 33 33 33 33 33 33 33 34 34 34 34 34 34
35 35 35 35 35 36 36 36 36 37 37 38 38 38 38 38 38 39 39 39
39 39 39 39 39 40 40 40 40 40 41 41 41 41 41 41 41 41 41 41
42 42 42 43 43 43 43 44 44 44 45 45 45 46 46 46 46 46 46 47
47 47 47 47 47 47 48 48 48 48 48 48 48 49 49 50 50 50 50 51
51 51 51 51 51 52 52 52 52 52 52 52 52 53 53 53 53 54 54 54
54 54 54 54 54 54 54 55 55 55 55 55 55 55 55 55 55 55 56 57
57 57 57 57 58 58 58 59 59 59 60 60 60 60 60 60 60 61 61 61
62 62 62 62 62 63 63 64 64 64 64 64 64 65 65 65 65 65 66 66
66 66 66 66 66 66 67 67 68 68 68 68 68 68 68 69 69 69 69 69
69 70 70 70 70 70 70 70 70 71 71 71 72 72 72 72 72 73 73 73
73 73 73 74 75 75 75 75 75 75 75 76 76 76 76 76 77 77 78 78
78 78 78 78 78 78 78 78 79 79 79 80 80 81 81 81 81 81 81 81
81 81 82 82 82 82 83 83 83 83 84 84 84 84 84 85 85 85 85 86
86 86 86 86 86 87 87 88 88 88 88 88 88 89 89 90 90 90 90 90
90 90 91 91 91 91 91 91 91 91 92 92 92 92 92 93 93 93 93 93
93 93 93 93 93 94 94 94 94 95 95 95 95 96 96 96 96 96 96 96
96 96 96 98 98 98 98 98 99 99 99 99 99 99 99 99 99 99 99 99

比较次数为：997
移动次数为： 500

D:visual studio 2017数据结构Sort_experiment4DebugSort_experiment4.exe (进程 508)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口…

####分析：

• 算法稳定
• 移动次数等于待排序次数，比较高效的一个算法

最后

以上就是壮观爆米花最近收集整理的关于简单入门排序算法（直接插入排序，折半插入排序，希尔排序，冒泡排序，堆排序，归并排序）的全部内容，更多相关简单入门排序算法（直接插入排序内容请搜索靠谱客的其他文章。