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

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

一、【实验目的】

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

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

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

二、【实验内容】

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

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

三、【实验源代码】

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 冒泡排序
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;
}

四、实验结果
奇了怪了