GDPU 算法分析与设计 天码行空 1

实验1 排序算法的效率分析

一、【实验目的】

（1）复习排序算法的实现过程；

（2）设计平均与最坏情况下时间复杂度的数据环境并理解相关含义；

（3）初步了解算法时间复杂度的分析方法。

二、【实验内容】

至少选择3种排序算法，要求对每种排序算法设计2组数据，其中一组为最坏情况，一组为一般情况（随机），数据规模不能少于10000。

记录不同情况下算法的实际运行时间，同时分析算法最坏情况与平均情况的运行次数。

三、【实验源代码】

#include 
#include 
#include 

// 冒泡排序
void bubbleSort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				// 交换arr[j]和arr[j+1]
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

// 快速排序
void quickSort(int arr[], int low, int high);

// 快速排序中的分区操作
int partition(int arr[], int low, int high) {
	int pivot = arr[high];
	int i = low - 1;
	for (int j = low; j < high; j++) {
		if (arr[j] < pivot) {
			i++;
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	int temp = arr[i + 1];
	arr[i + 1] = arr[high];
	arr[high] = temp;
	return i + 1;
}

// 快速排序递归函数
void quickSort(int arr[], int low, int high) {
	if (low < high) {
		int pi = partition(arr, low, high);
		quickSort(arr, low, pi - 1);
		quickSort(arr, pi + 1, high);
	}
}

// 归并排序中的合并操作
void merge(int arr[], int l, int m, int r) {
	int n1 = m - l + 1;
	int n2 = r - m;
	
	int L[n1], R[n2];
	
	for (int i = 0; i < n1; i++) {
		L[i] = arr[l + i];
	}
	for (int j = 0; j < n2; j++) {
		R[j] = arr[m + 1 + j];
	}
	
	int i = 0, j = 0;
	int k = l;
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		} else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}
	
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}
	
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

// 归并排序递归函数
void mergeSort(int arr[], int l, int r) {
	if (l < r) {
		int m = (l + r) / 2;
		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);
		merge(arr, l, m, r);
	}
}

int main() {
	const int n = 10000;
	int nums[n];
	srand(time(NULL));
	for (int i = 0; i < n; i++) {
		nums[i] = rand();
	}
	
	int copy[n];
	for (int i = 0; i < n; i++) {
		copy[i] = nums[i];
	}
	
	clock_t startTime, endTime;
	double duration;
	
	startTime = clock();
	bubbleSort(copy, n);
	endTime = clock();
	
	duration = ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;
	printf("冒泡排序 %.1f ms\n", duration);
	
	for (int i = 0; i < n; i++) {
		copy[i] = nums[i];
	}
	
	startTime = clock();
	mergeSort(copy, 0, n - 1);
	endTime = clock();
	
	duration = ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;
	printf("归并排序 %.1f ms\n", duration);
	
	for (int i = 0; i < n; i++) {
		copy[i] = nums[i];
	}
	
	startTime = clock();
	quickSort(copy, 0, n - 1);
	endTime = clock();
	
	duration = ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;
	printf("快速排序 %.1f ms\n", duration);
	
	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

四、实验结果
奇了怪了