当前位置： 首页 > article >正文

【数据结构课设--内部排序算法的性能分析系统】

article 2025/3/12 12:37:06

设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。

基本要求：
(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；
(2)待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；
(3)输出比较结果；
(4)验证各算法每次排序的稳定性；
(5)输出界面的优化。

代码如下：

#include <stdio.h> // 包含标准输入输出库
#include <stdlib.h> // 包含标准库函数，如malloc和rand
#include <time.h> // 包含时间相关的函数，如time和rand
#include <windows.h> // 包含Windows API函数，如QueryPerformanceCounter

// 定义数组长度和测试次数
#define MAXSIZE 50000
#define NUMTESTS 5
typedef bool Bool;
Bool foundUnstable = false; // 稳定性标志

// 数据 结构定义
typedef struct {
	int value; // 数据值
	int originalIndex; // 原始索引
} Data;

//一个基于数组的结构，它使用数组来存储数据元素，是一个具有数组特性的结构。
typedef struct {
	Data *array; // 指向数据的指针
	int length; // 数据长度
} LinkList;



// 排序函数声明
void BubbleSort(LinkList *L, long long *cmpNum, long long *chgNum);
void InsertSort(LinkList *L, long long *cmpNum, long long *chgNum);
void SelectSort(LinkList *L, long long *cmpNum, long long *chgNum);
void QuickSort(LinkList *L, long long *cmpNum, long long *chgNum);
void ShellSort(LinkList *L, long long *cmpNum, long long *chgNum);
void HeapSort(LinkList *L, long long *cmpNum, long long *chgNum);
Bool isStable(LinkList *L); // 检查排序是否稳定

// 打印数组函数声明
void printArray(LinkList *L);

// 生成随机数组函数声明
void generateRandomArray(LinkList *L, int length);

// 打印排序结果函数声明
void PrintResults(const char* name, long long CmpNum, long long ChgNum, Bool stable, LARGE_INTEGER startTime, LARGE_INTEGER endTime,LARGE_INTEGER freq);
// 打印时间复杂度描述
void printTimeComplexity(const char *name, const char *worstCase, const char *avgCase, const char *bestCase);

// 打印排序结果函数声明
void PrintResults(const char* name, long long cmpNum, long long chgNum, Bool stable, LARGE_INTEGER startTime, LARGE_INTEGER endTime, LARGE_INTEGER freq) {
	double timeTaken = (double)(endTime.QuadPart - startTime.QuadPart) / freq.QuadPart;
	printf("\t\t\t\t排序算法：%-10s\n", name);
	printf("\t\t\t\t比较次数：%12lld\n", cmpNum);
	printf("\t\t\t\t交换次数：%12lld\n", chgNum);
	printf("\t\t\t\t稳定性：%s\n", stable ? "稳定" : "不稳定");
	printf("\t\t\t\t用时：%f 秒\n", timeTaken);
	
}

// 打印时间复杂度描述
void printTimeComplexity(const char *name, const char *worstCase, const char *avgCase, const char *bestCase) {
	printf("\t\t\t时间复杂度 - %s:\n", name);
	printf("\t\t\t  最坏情况: %s\n", worstCase);
	printf("\t\t\t  平均情况: %s\n", avgCase);
	printf("\t\t\t  最好情况: %s\n\n", bestCase);
	printf("************************************************************\n"); // 添加分隔符
}

int main() {
	// 创建链表结构
	LinkList L;
	int length; // 数组长度
	long long cmpNum, chgNum; // 比较和交换次数
	LARGE_INTEGER startTime, endTime, freq; // 高精度计时器变量
	Bool stable; // 稳定性标志
	
	// 获取计数器频率
	QueryPerformanceFrequency(&freq);
	
	// 输入数组长度
	printf("请输入数组长度（100-50000）：");
	scanf("%d", &length);
	if (length < 100 || length > MAXSIZE) {
		printf("无效的数组长度。必须在100到50000之间。\n");
		return 1;
	}
	
	// 分配内存
	L.array = (Data *)malloc(length * sizeof(Data));
	if (L.array == NULL) {
		printf("内存分配失败。\n");
		return 1;
	}
	L.length = length;
	
	// 生成随机数种子
	srand((unsigned)time(NULL));
	
	// 循环进行测试
	for (int i = 0; i < NUMTESTS; i++) {
		// 生成随机数组
		generateRandomArray(&L, length);
		printf("-----------------------------------------------------------------------\n");
		printf("\n\n\t\t\t Test %d:\n", i + 1);
		
		// 使用高精度计时器
		QueryPerformanceFrequency(&freq); // 获取计数器频率
		QueryPerformanceCounter(&startTime); // 开始计时
		
		// 调用排序函数并打印结果
		// BubbleSort
		cmpNum = 0; // 初始化比较次数为0
		chgNum = 0; // 初始化交换次数为0
		BubbleSort(&L, &cmpNum, &chgNum); // 调用冒泡排序函数
		QueryPerformanceCounter(&endTime); // 记录排序结束时间
		stable = isStable(&L); // 检查排序是否稳定
		PrintResults("BubbleSort", cmpNum, chgNum, stable, startTime, endTime, freq); // 打印排序结果
		printTimeComplexity("冒泡排序", "O(n^2)", "O(n^2)", "O(n) (已排序)");
		
		// InsertSort
		cmpNum = 0; 
		chgNum = 0; 
		generateRandomArray(&L, length); 
		QueryPerformanceCounter(&startTime);
		InsertSort(&L, &cmpNum, &chgNum); 
		QueryPerformanceCounter(&endTime); 
		stable = isStable(&L);
		PrintResults("InsertSort", cmpNum, chgNum, stable, startTime, endTime, freq); 
		printTimeComplexity("插入排序", "O(n^2)", "O(n^2/2)", "O(n) (已排序)");
		
		
		// SelectSort
		cmpNum = 0; 
		chgNum = 0;
		generateRandomArray(&L, length); 
		QueryPerformanceCounter(&startTime); 
		SelectSort(&L, &cmpNum, &chgNum); 
		QueryPerformanceCounter(&endTime); 
		stable = isStable(&L); 
		PrintResults("SelectSort", cmpNum, chgNum, stable, startTime, endTime, freq); 
		printTimeComplexity("选择排序", "O(n^2)", "O(n^2)", "O(n^2) (已排序)");
		
		// QuickSort
		cmpNum = 0; 
		chgNum = 0; 
		generateRandomArray(&L, length); 
		QueryPerformanceCounter(&startTime); 
		QuickSort(&L, &cmpNum, &chgNum); 
		QueryPerformanceCounter(&endTime); 
		stable = isStable(&L); 
		PrintResults("QuickSort", cmpNum, chgNum, stable, startTime, endTime, freq);
		printTimeComplexity("快速排序", "O(n^2) (最坏情况)", "O(n log n)", "O(n log n) (最好情况)");
		
		
		// ShellSort
		cmpNum = 0;
		chgNum = 0;
		generateRandomArray(&L, length);
		QueryPerformanceCounter(&startTime); 
		ShellSort(&L, &cmpNum, &chgNum);
		QueryPerformanceCounter(&endTime);
		stable = isStable(&L); 
		PrintResults("ShellSort", cmpNum, chgNum, stable, startTime, endTime, freq); 
		printTimeComplexity("希尔排序", "取决于间隔序列", "取决于间隔序列", "取决于间隔序列");
		
		// HeapSort
		cmpNum = 0; 
		chgNum = 0; 
		generateRandomArray(&L, length); 
		QueryPerformanceCounter(&startTime); 
		HeapSort(&L, &cmpNum, &chgNum); 
		QueryPerformanceCounter(&endTime); 
		stable = isStable(&L); 
		PrintResults("HeapSort", cmpNum, chgNum, stable, startTime, endTime, freq);
		printTimeComplexity("堆排序", "O(n log n)", "O(n log n)", "O(n log n)");
		
		// 打印排序后的数组
		printArray(&L);
	}
	
	// 释放链表内存
	free(L.array);
	
	return 0;
}


/// 排序函数实现
// 冒泡排序实现
void BubbleSort(LinkList *L, long long *cmpNum, long long *chgNum) {
	// 外层循环控制排序的趟数，每趟将一个最小的元素移动到其最终位置
	for (int i = 0; i < L->length - 1; i++) {
		// 内层循环进行实际的比较和交换操作
		for (int j = 0; j < L->length - i - 1; j++) {
			// 比较相邻元素，如果前者大于后者，则交换它们
			(*cmpNum)++;
			if (L->array[j].value > L->array[j + 1].value) {
				// 交换元素
				Data temp = L->array[j];
				L->array[j] = L->array[j + 1];
				L->array[j + 1] = temp;
				// 每次交换记为3次移动
				*chgNum += 3;
			}
			// 检查稳定性
			if (L->array[j].value == L->array[j + 1].value && L->array[j].originalIndex > L->array[j + 1].originalIndex) {
				foundUnstable = true; // 发现不稳定，记录下来
			} else {
				foundUnstable = false; // 如果顺序没有改变，则重置标志
			}
		}
	}
}

// 插入排序实现
void InsertSort(LinkList *L, long long *cmpNum, long long *chgNum) {
	// 从第二个元素开始，逐个插入到已排序序列的适当位置
	for (int i = 1; i < L->length; i++) {
		Data key = L->array[i]; // 当前要插入的元素
		int j = i - 1;
		// 从已排序序列的尾部开始，比较并移动元素，直到找到插入位置
		while (j >= 0 && L->array[j].value > key.value) {
			// 比较操作
			(*cmpNum)++;
			// 移动元素
			L->array[j + 1] = L->array[j];
			j = j - 1;
			// 每次移动记为3次操作
			*chgNum += 3;
		}
		// 插入元素
		L->array[j + 1] = key;
		// 检查稳定性
		if (L->array[j].value == L->array[j + 1].value && L->array[j].originalIndex > L->array[j + 1].originalIndex) {
			foundUnstable = true; // 发现不稳定，记录下来
		} else {
			foundUnstable = false; // 如果顺序没有改变，则重置标志
		}
	}
}

// 选择排序实现
void SelectSort(LinkList *L, long long *cmpNum, long long *chgNum) {
	// 遍历数组，每次找到最小元素的索引
	for (int i = 0; i < L->length - 1; i++) {
		int min_index = i;
		// 内层循环找到未排序部分的最小元素
		for (int j = i + 1; j < L->length; j++) {
			(*cmpNum)++; // 增加比较次数
			if (L->array[j].value < L->array[min_index].value) {
				min_index = j; // 更新最小元素的索引
			}
			// 检查稳定性
			if (L->array[j].value == L->array[j + 1].value && L->array[j].originalIndex > L->array[j + 1].originalIndex) {
				foundUnstable = true; // 发现不稳定，记录下来
			} else {
				foundUnstable = false; // 如果顺序没有改变，则重置标志
			}
		}
		// 如果最小元素不是当前位置的元素，则交换它们
		if (min_index != i) {
			Data temp = L->array[i];
			L->array[i] = L->array[min_index];
			L->array[min_index] = temp;
			// 每次交换记为3次操作
			*chgNum += 3;
		}
	}
}


// 快速排序辅助函数 - 分区操作
void quickSortPartition(LinkList *L, int low, int high, long long *cmpNum, long long *chgNum, int *pivotIndex) {
	// 选择最后一个元素作为基准
	Data pivot = L->array[high];
	int i = (low - 1); // 小于基准的元素的索引
	// 遍历数组，将小于基准的元素移动到左边
	for (int j = low; j <= high - 1; j++) {
		// 比较操作
		(*cmpNum)++;
		if (L->array[j].value < pivot.value) {
			i++;
			// 交换元素
			Data temp = L->array[i];
			L->array[i] = L->array[j];
			L->array[j] = temp;
			// 每次交换记为3次操作
			*chgNum += 3;
			
		}
		// 检查稳定性
		if (L->array[j].value == L->array[j + 1].value && L->array[j].originalIndex > L->array[j + 1].originalIndex) {
			foundUnstable = true; // 发现不稳定，记录下来
		} else {
			foundUnstable = false; // 如果顺序没有改变，则重置标志
		}
	}
	// 将基准元素放到正确的位置
	Data temp = L->array[i + 1];
	L->array[i + 1] = L->array[high];
	L->array[high] = temp;
	// 更新基准元素的索引
	*pivotIndex = i + 1;
}


// 快速排序递归函数
void quickSortRecursion(LinkList *L, int low, int high, long long *cmpNum, long long *chgNum) {
	// 如果低索引小于高索引，说明还有元素需要排序
	if (low < high) {
		int pivotIndex;
		// 对数组进行分区，并获取基准元素的索引
		quickSortPartition(L, low, high, cmpNum, chgNum, &pivotIndex);
		// 递归地对基准元素左侧的子数组进行快速排序
		quickSortRecursion(L, low, pivotIndex - 1, cmpNum, chgNum);
		// 递归地对基准元素右侧的子数组进行快速排序
		quickSortRecursion(L, pivotIndex + 1, high, cmpNum, chgNum);
	}
}

// 快速排序的入口函数
void QuickSort(LinkList *L, long long *cmpNum, long long *chgNum) {
	// 从数组的第一个到最后一个元素进行快速排序
	quickSortRecursion(L, 0, L->length - 1, cmpNum, chgNum);
}


// 希尔排序
void ShellSort(LinkList *L, long long *cmpNum, long long *chgNum) {
	int gap = L->length / 2; // 初始化间隔 gap 为数组长度的一半
	while (gap > 0) { // 当间隔不为零时，继续进行排序
		for (int i = gap; i < L->length; i++) { // 遍历数组，从间隔开始到数组末尾
			Data temp = L->array[i]; // 暂存当前元素
			int j; // 初始化 j 为 i
			for (j = i; j >= gap && L->array[j - gap].value > temp.value; j -= gap) { // 从 i 开始向前查找插入位置
				(*cmpNum)++; // 增加比较次数
				L->array[j] = L->array[j - gap]; // 移动元素到正确位置
				*chgNum += 3; // 增加 3 次操作计数（实际是赋值操作，但为了统计方便，这里记为交换）
			}
			L->array[j] = temp; // 将暂存的元素插入到正确位置
			// 检查稳定性
			if (j >= gap && L->array[j].value == L->array[j - gap].value && L->array[j].originalIndex < L->array[j - gap].originalIndex) {
				foundUnstable = true; // 发现不稳定，记录下来
			}	
		}
		gap /= 2; // 减小间隔，继续进行排序
	}
}

// 堆排序辅助函数
// heapify 函数用于将数组 L 的子树调整为最大堆
void heapify(LinkList *L, int n, int i, long long *cmpNum, long long *chgNum) {
	int largest = i; // 初始化 largest 为当前节点 i，即父节点
	int left = 2 * i + 1; // 计算左子节点的索引
	int right = 2 * i + 2; // 计算右子节点的索引
	
	// 如果左子节点存在，并且左子节点的值大于父节点的值
	if (left < n) {
		*cmpNum += 1; // 增加比较次数
		if (L->array[left].value > L->array[largest].value) {
			largest = left; // 更新 largest 为左子节点的索引
		}
	}
	// 如果右子节点存在，并且右子节点的值大于当前 largest 的值
	if (right < n) {
		*cmpNum += 1; // 增加比较次数
		if (L->array[right].value > L->array[largest].value) {
			largest = right; // 更新 largest 为右子节点的索引
		}
	}
	// 如果 largest 不等于 i，说明子节点中有更大的值
	if (largest != i) {
		Data temp = L->array[i]; // 交换父节点和 largest 节点的值
		L->array[i] = L->array[largest];
		L->array[largest] = temp;
		*chgNum += 3; // 增加 3 次交换操作计数（实际是赋值操作，但为了统计方便，这里记为交换）
		// 递归调用 heapify，继续调整受影响的子树
		heapify(L, n, largest, cmpNum, chgNum);
	}
}

// 堆排序主函数
void HeapSort(LinkList *L, long long *cmpNum, long long *chgNum) {
	int n = L->length; // 获取数组的长度
	// 从最后一个非叶子节点开始，建立最大堆
	for (int i = n / 2 - 1; i >= 0; i--) {
		heapify(L, n, i, cmpNum, chgNum); // 调整子树
	}
	// 排序过程，每次循环将堆顶元素（最大值）移动到数组的末尾
	for (int i = n - 1; i >= 0; i--) {
		Data temp = L->array[0]; // 将堆顶元素（最大值）暂存到 temp
		L->array[0] = L->array[i]; // 将堆顶元素与最后一个元素交换
		L->array[i] = temp;
		*chgNum += 3; // 增加 3 次交换操作计
		// 调用 heapify 函数，调整剩余元素，保持最大堆性质
		heapify(L, i, 0, cmpNum, chgNum); // 注意此时 n 已变为 i，因为堆的大小在减小
	// 检查稳定性
		for (int j = 0; j < i - 1; j++) {
			if (L->array[j].value == L->array[j + 1].value && L->array[j].originalIndex > L->array[j + 1].originalIndex) {
				foundUnstable = true; // 发现不稳定，记录下来
				break; // 一旦发现不稳定，退出循环
			}
		}
	}
}


// 检查排序是否稳定
Bool isStable(LinkList *L) {
	if (foundUnstable) {
		return false; // 如果发现不稳定，则返回false
	}
	// 如果没有发现不稳定，则遍历数组检查稳定性
	for (int i = 0; i < L->length - 1; i++) {
		if (L->array[i].value == L->array[i + 1].value && L->array[i].originalIndex > L->array[i + 1].originalIndex) {
			return false; // 发现不稳定，返回false
		}
	}
	return true; // 如果所有相等元素的顺序未改变，则排序稳定
}

// 打印数组内容
void printArray(LinkList *L) {
	// 遍历链表，打印每个元素的值
	for (int i = 0; i < L->length; i++) {
		printf("%d ", L->array[i].value);
	}
	printf("\n"); // 打印换行符，结束一行的打印
}

// 生成随机数组
void generateRandomArray(LinkList *L, int length) {
	// 遍历链表，为每个元素分配一个随机值和原始索引
	for (int i = 0; i < length; i++) {
		L->array[i].value = rand() % MAXSIZE; // 随机值
		L->array[i].originalIndex = i; // 原始索引
	}
}

http://www.kler.cn/a/545487.html

相关文章：

  • 考研操作系统----操作系统的概念定义功能和目标（仅仅作为王道哔站课程讲义作用）
  • 独立C++ asio库实现的UDP Server
  • 用python写一个聊天室程序
  • 使用Cocos Creator制作“打砖块”小游戏：从零开始的详细教程
  • 告别硬编码：用 load_dotenv 高效管理你的环境变量
  • 【Git版本控制器】：第一弹——Git初识，Git安装,创建本地仓库，初始化本地仓库，配置config用户名，邮箱信息
  • Trend Micro 网络安全●解决方案
  • 物联网平台-分布式的设备接入与管理系统
  • NGINX相关的知识点
  • 10. Hbase Compaction命令
  • 34.Qt使用回调函数
  • 财务主题数据分析-企业盈利能力分析
  • 人工智能时代下ai智能语音机器人如何以假乱真？
  • Oracle DBA 诊断及统计工具-1
  • Navicat导入海量Excel数据到数据库（简易介绍）
  • 前端IndexedDB使用教程
  • AI成为基础设施有哪些研究方向：模型的性能、可解释性，算法偏见
  • 数据操作与事务：确保数据一致性的关键
  • 接口自动化框架篇：框架中的数据流转处理！
  • Mac 下使用多版本 Node