选择排序、冒泡排序、归并排序、快速排序、插入排序的实现以及算法时间效率的计算分析-c语言_c语言中算法时间效率分析

题目：利用switch结构来选择所要用的排序算法，每一种排序都用相同的计算运行时间的代码，不断的改变数据规模，每一个规模在实验时，用循环进行多次实验并作为样本记录消耗的时间。最后输出在不同排序算法下，不同的数据规模的20次实验样本和平均用时。

1.整体思路：
（1）首先要实现选择排序、冒泡排序、归并排序、快速排序、插入排序这五种排序的功能。
//arr是传入的数组，len是数组长度
//由于归并排序、快速排序使用递归算法，因此不能再排序函数中计算时间。
void select_sort(int arr[], int len);
void maopao_sort(int arr[], int len);
void merge_sort(int arr[], unsigned int first, unsigned int last);
void quick_sort(long int arr[], int begin, int end);
void charu_sort(long int arr[], int len);
（2）其次实现五种排序方法计算时间的函数。
在计算时间的函数中，用while循环20个样本，每个数组内容随机生成，每生成一次，记录当前时间（begintime）并调用相应排序函数，再次记录时间（endtime），算出排序所用的时间（endtime - begintime）。
void select_time(int len);
void maopao_time(int len);
void merge_time(int len);
void quick_time(int len);
void charu_time(int len);
（3）main函数中switch结构来选择所要用的排序算法，len长度的初始值为10，用while循环来增加len长度，将len值传入所需的函数中调用来计算输出不同数组长度的时间。
2.算法分析
（1）选择排序;
核心思想：选出一个最值将其与第一个数进行交换，len个数是len-1趟;
（2）冒泡排序;
核心思想：每趟比价中进行len-1次的两两比较，第j次比较中进行len-j次的比较，每趟结束后，将最值沉底;
（3）合并排序;
核心思想：将待排序序列分为两部分，依次对分得的两个部分再次使用归并排序，之后再对其进行合并;
（4）快速排序;
核心思想：数组中取出第一个数（默认）作为基准数。将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 再对左右区间重复上述步骤，直到各区间只有一个数。
（5）插入排序;
核心思想：将数组的第一个数记为有序序列，其后len-1个数组成无序列，将无序序列中的数依次插入有序序列。
3.算法实现

/*
date：2018/11/30
author:Better_Me1
program:关于选择排序、冒泡排序、归并排序、快速排序、插入排序算法时间效率的研究;
compiler:Visual Studio 2013
*/

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>//用到clock()函数
#include<Windows.h>

int begintime = 0;
int endtime = 0;
int arr1[100000] = { 0 };

//交换数组函数;
void swap(int* a, int* b){
	int c = 0;
	c = *a;
	*a = *b;
	*b = c;
}

//选择排序;
//分析：选出一个最值将其与第一个数进行交换，len个数是len-1趟;
void select_sort(int arr[], int len){
	int min = 0;
	for (int i = 0; i < len - 1; i++){//外层循环控制趟数;
		min = i;//假设第一个数为最小值;
		for (int j = i + 1; j < len; j++){//从下一个数至以后一个数中寻找最值;
			if (arr[min] > arr[j]){ //后面有比最值更小的;
				min = j;     //下标记到min中;
			}
		}
		if (min != i){
			swap(&arr[min], &arr[i]);//交换两数的值，此时将最小的数交换到了第一位;
		}
	}
}

//冒泡排序;
//分析：每趟比价中进行len-1次的两两比较，第j次比较中进行len-j次的比较，每趟结束后，将最值沉底;
void maopao_sort(int arr[], int len){
	for (int i = 0; i < len - 1; i++){//外层循环控制趟数;
		for (int j = 0; j < len - i; j++){//第j趟比较len-j次;
			if (arr[j] > arr[j + 1]){  //若下一个小;
				swap(&arr[j], &arr[j + 1]);//交换;
			}
		}
	}
}
void merge(int arr[], int low, int mid, int high){
	int i, k;
	int *tmp = (int *)malloc((high - low + 1)*sizeof(int));
	//申请空间，使其大小为两个;
	int left_low = low;
	int left_high = mid;
	int right_low = mid + 1;
	int right_high = high;
	for (k = 0; left_low <= left_high && right_low <= right_high; k++){ // 比较两个指针所指向的元素;
		if (arr[left_low] <= arr[right_low]){
			tmp[k] = arr[left_low++];
		}
		else{
			tmp[k] = arr[right_low++];
		}
	}
	if (left_low <= left_high){ //若第一个序列有剩余，直接复制出来粘到合并序列尾;
		for (i = left_low; i <= left_high; i++){
			tmp[k++] = arr[i];
		}
	}
	if (right_low <= right_high){
		//若第二个序列有剩余，直接复制出来粘到合并序列尾;
		for (i = right_low; i <= right_high; i++){
			tmp[k++] = arr[i];
		}
	}
	for (i = 0; i < high - low + 1; i++){
		arr[low + i] = tmp[i];
	}
	free(tmp);
}
//合并排序;
//分析：将待排序序列分为两部分，依次对分得的两个部分再次使用归并排序，之后再对其进行合并;
void merge_sort(int arr[], unsigned int first, unsigned int last){
	int mid = 0;
	if (first < last){
		mid = first/2 + last/2;// 防止溢出 ;
		merge_sort(arr, first, mid);
		merge_sort(arr, mid + 1, last);
		merge(arr, first, mid, last);
	}
}

//快速排序的作用;
//分析：数组中取出第一个数（默认）作为基准数。将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
//再对左右区间重复上述步骤，直到各区间只有一个数;
//交换的次数较少，提高了程序的运行速度;
//在最差的情况下，时间复杂度仍和冒泡排序一样是O(N ^ 2)，但是平均复杂度是O(NlonN);
void quick_sort(int arr[], int begin, int end){
	int i = begin;
	int j = end;
	int x = arr[begin];
	if (begin < end){
		while (begin < end){
			while (begin<end && arr[end]>x){
				end--;
			}
			if (begin < end){
				arr[begin++] = arr[end];
			}
			while (begin < end && arr[begin] < x){
				begin++;
			}
			if (begin < end){
				arr[end--] = arr[begin];
			}
		}
		arr[begin] = x;
		quick_sort(arr, i, end - 1);//用递归将选取的标准数左右两边都进行排序;
		quick_sort(arr, begin + 1, j);
	}
}



//插入排序;
//分析：将数组的第一个数记为有序序列，其后len-1个数组成无序列，将无序序列中的数依次插入有序序列;
void charu_sort(int arr[], int len){
	int t = 0;
	int j = 0;
	for (int i = 1; i < len; i++){//从第二个数开始，直至最后一个数;
		t = arr[i];//待插入的数;
		for (j = i - 1; j >= 0 && t < arr[j]; j--){//在有序序列中寻找插入位置;
			arr[j + 1] = arr[j];//还未找到插入位置,当前元素后移，为插入的数准备空间;
		}
		arr[j + 1] = t;//找到插入位置，将元素插入;
	}
}

//计算20组样本选择排序所用的时间
void select_time(int len){
	int sum = 0;
	int n = 0;//样本;
	printf("20组样本(ms):>");
	while (n < 20){
		for (int i = 0; i < len; i++){
			arr1[i] = rand();
		}
		/*for (int i = 0; i < len; i++){
			printf("%d\n", arr1[i]);
			count++;
		}*/
		/*printf("\n");
		printf("%d\n", count);*/
		begintime = clock();	//计时开始;
		select_sort(arr1,len);//选择排序;
		endtime = clock();	//计时结束;
		sum = sum + endtime - begintime;//总时间;
		printf(" %d ", endtime - begintime);
		if (n == 19){
			printf("\n");
		}
		n++;
	}
	printf("排序所花平均时间:> %d \n", (sum / 20));
}
//计算20组样本冒泡排序所用的时间
void maopao_time(int len){
	int sum = 0;
	int n = 0;//样本;
	printf("20组样本(ms):>");
	while (n < 20){
		for (int i = 0; i < len; i++){
			arr1[i] = rand();
		}
		begintime = clock();	//计时开始;
		maopao_sort(arr1, len);//冒泡排序;
		endtime = clock();	//计时结束;
		sum = sum + endtime - begintime;//总时间;
		printf(" %d ", endtime - begintime);
		if (n == 19){
			printf("\n");
		}
		n++;
	}
	printf("排序所花平均时间:> %d \n", (sum / 20));
}
//计算20组样本合并排序所用的时间
void merge_time(int len){
	int sum = 0;
	int n = 0;//样本;
	printf("20组样本(ms):>");
	while (n < 20){
		for (int i = 0; i < len; i++){
			arr1[i] = rand();
		}
		begintime = clock();	//计时开始;
		merge_sort(arr1, 0, len - 1);//合并排序;
		endtime = clock();	//计时结束;
		sum = sum + endtime - begintime;//总时间;
		printf(" %d ", endtime - begintime);
		if (n == 19){
			printf("\n");
		}
		n++;
	}
	printf("排序所花平均时间:> %d \n", (sum / 20));
}
//计算20组样本快速排序所用的时间
void quick_time(int len){
	int sum = 0;
	int n = 0;//样本;
	printf("20组样本(ms):>");
	while (n < 20){
		for (int i = 0; i < len; i++){
			arr1[i] = rand();
		}
		begintime = clock();	//计时开始;
		quick_sort(arr1, 0, len - 1);//快速排序;
		endtime = clock();	//计时结束;
		sum = sum + endtime - begintime;//总时间;
		printf(" %d ", endtime - begintime);
		if (n == 19){
			printf("\n");
		}
		n++;
	}
	printf("排序所花平均时间:> %d \n", (sum / 20));
}
//计算20组样本插入排序所用的时间
void charu_time(int len){
	int sum = 0;
	int n = 0;//样本;
	printf("20组样本(ms):>");
	while (n < 20){
		for (int i = 0; i < len; i++){
			arr1[i] = rand();
		}
		begintime = clock();	//计时开始;
		charu_sort(arr1, len);//插入排序;
		endtime = clock();	//计时结束;
		sum = sum + endtime - begintime;//总时间;
		printf(" %d ", endtime - begintime);
		if (n == 19){
			printf("\n");
		}
		n++;
	}
	printf("排序所花平均时间:> %d \n", (sum / 20));
}
int main(){
	int input = 0;
	int len = 10;
	while (input<1||input>5){
		printf("1.选择排序  2.冒泡排序  3.合并排序  4.快速排序  5.插入排序\n");
		printf("请输入你的选择:>");
		scanf("%d", &input);
		switch (input){
		case 1:
			while (len <= 100000){
				printf("数组长度为%d时：\n",len);
				select_time(len); //数据规模为10时;
				if (len != 100000){
					printf("----------------------------------------------------------------------------------\n");
				}
				len = len * 10;
			}
			break;
		case 2:
			while (len <= 100000){
				printf("数组长度为%d时：\n", len);
				maopao_time(len);//计算冒泡排序所用的时间;
				if (len != 100000){
					printf("----------------------------------------------------------------------------------\n");
				}
				len = len * 10;
			}
			break;
		case 3:
			while (len <= 100000){
				printf("数组长度为%d时：\n", len);
				merge_time(len);//计算合并排序所用的时间;
				if (len != 100000){
					printf("----------------------------------------------------------------------------------\n");
				}
				len = len * 10;
			}
			break;
		case 4:
			while (len <= 100000){
				printf("数组长度为%d时：\n", len);
				quick_time(len);//计算快速排序所用的时间;
				if (len != 100000){
					printf("----------------------------------------------------------------------------------\n");
				}
				len = len * 10;
			}
			break;
		case 5:
			while (len <= 100000){
				printf("数组长度为%d时：\n", len);
				charu_time(len);//计算插入排序所用的时间;
				if (len != 100000){
					printf("----------------------------------------------------------------------------------\n");
				}
				len = len * 10;
			}
			break;
		default:
			printf("选择错误，请重新输入！");
		}
	}
	/*for (i = 0; i < len; i++){
		printf("%d\n", arr1[i]);
	}*/
	system("pause");
	return 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
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323

4.运行效果

选择排序：

冒泡排序：

归并排序：

快速排序：

插入排序：

5.算法复杂度分析及经验归纳
算法的复杂度分析：

经验归纳：（主要说明编写程序时遇到的问题）
（1）原先设想在每一个排序函数中计算时间，但由于归并排序、快速排序使用了递归算法，因此经过考虑重新写了计算排序时间的函数，在函数中调用相应排序函数。
（2）认识到初始化的重要性，首次测试时，时间出现了负值，但在计算时间的函数中输出开始时间和结束时间都无误，输出两数相减时却出现负值，多次调式后无果，最后将begintime，endtime初始化后程序无误。（逻辑上并无问题，但有时可能会出现意想不到的结果，个人当前看法）
（3）全局变量和局部变量一定要分清楚，程序测试时，第一次调用计算排序时间的函可以打印出来，但以后就不能，分析程序时因为n（样本数）设为了全局变量，一次调用之后修改了n的值，第二次便不能进入调用函数中的循环。