数据结构实训项目---比较一些排序

文章背景

我以前一直以为各种排序都差不多,只要越快写出来越好,浪费时间在这上面干嘛,直到我写了才发现这些排序各有千秋,如图:

当数据规模为100

当数据规模为20000时

当数据规模为20w时(再多就不测试了,我的int类型的数据装不下比较次数了,复述的比较次数就是超出范围了,而且等待时间太久了)

程序崩了,我就不放了,运行时间太久了

在进行排序之间需要准备一些处理 1,我采用宏定义的方法定义需要排序的一维数组的大小

#define MAX_SIZE 200000 //进行排序的规模
#define MAX_TRAVEL 100 //在需要遍历数组的个数超过这个时,则不会遍历

每次要修改规模时,都需要去修改,很麻烦,但是我知道聪明的你肯定会知道使用变量来解决这个问题

2,需要用到的头文件

#include
#include 
#include
#include

3,这是产生随机数的方法

int* createRandomIntList() {
	int* intList = (int*)malloc(sizeof(int)*MAX_SIZE); // 开辟空间
	printf("产生的随机数如下:n");
	for (int i = 0; i < MAX_SIZE; i++) {
		intList[i] = rand() % 100; // 产生[0-100)的随机数
	}
	travelList(intList);
	return intList;
}

4,遍历数组

void travelList(int* list) {
	if (MAX_SIZE > MAX_TRAVEL) {
		printf("随机数组的大小超过了最大遍历数,则不会遍历输出!n");
		return;
	}
	printf("==============开始遍历=================n");
	for (int i = 0; i < MAX_SIZE; i++) {
		if (!(i % 5)) {
			printf("n");
		}
		printf("%dt", list[i]);
	}
	printf("n==============遍历结束=================n");
}

5,需要比较各个算法的各种属性,如运算时间,移动次数等,用一个结构体来对这些属性进行抽象,方便书写和阅读代码

typedef struct Tool{
	char name[20] = ""; // 记录算法名字
	int compareTime = 0; // 记录比较次数
	int moveTime = 0; //记录移动次数
	long begainTime = 0; // 记录开始时间
	long endTime = 0;// 记录结束时间
};

6,格式化输出这些信息的函数

void printTool(Tool tool) {
	printf("=====================%s============================n",tool.name);
	printf("排序规模(个):%dn",MAX_SIZE);
	printf("程序运行时间:%ld个时钟周期n",tool.endTime - tool.begainTime);
	printf("移动次数:%dn比较次数:%dn",tool.moveTime,tool.compareTime);
	printf("=================================================n");
}

一切准备就绪,现在步入正题,在这里我将实现5个算法:

1,直接选择排序：通过n-I次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。

Tool zhiJie_sort(int* _list) {
	int* list = copyList(_list);
	Tool tool;
	strcpy_s(tool.name, "直接排序");
	tool.begainTime = clock();
	for (int i = 0; i < MAX_SIZE; i++) {
		int min = list[i];
		int k = i;
		for (int j = i + 1; j < MAX_SIZE; j++) {
			tool.compareTime++;
			if (min > list[j]) {
				min = list[j];
				k = j;
			}
		}
		if (k != i) {
			int a = list[i];
			list[i] = list[k];
			list[k] = a;
			tool.moveTime++;
		}
	}
	tool.endTime = clock();
	printf("n直接排序成功!n");
	travelList(list);
	printTool(tool);
	return tool;
}

2,冒泡排序：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较

Tool qiPao_sort(int* _list) {
	int* list = copyList(_list);
	Tool tool;
	strcpy_s(tool.name, "冒泡排序");
	tool.begainTime = clock();
	for (int i = 0; i < MAX_SIZE; i++) {
		for (int j = 0; j < MAX_SIZE-1-i; j++) {
			tool.compareTime++;
			if (list[j] > list[j + 1]) {
				int a = list[j];
				list[j] = list[j+1];
				list[j+1] = a;
				tool.moveTime++;
			}
		}
	}
	tool.endTime = clock();
	travelList(list);
	printTool(tool);
	return tool;
}

3,希尔排序：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

void shell_sort(int* list,int begPosition,int endPosition,Tool* tool,int* times) {
	(*times)++;
	int keyValue = list[begPosition]; // 枢轴值
	int key = begPosition; // 记录空位置
	for (int i = begPosition, j = endPosition; i compareTime++;
		if (keyValue>list[j]) { // 从右边开始比较
			list[key] = list[j];// 将右边小于枢值移到左边
			key = j;// 记录空值位置
			tool->moveTime++;
			while (keyValue >= list[i] && i!=key) {//从左边开始比较
				tool->compareTime++;
				i++;
			}
			if (i == key) {
				break;
			}
			list[key] = list[i];			// i 为空位置
			key = i;
			tool->moveTime++;
		}
	}
	list[key] = keyValue;
	if (MAX_TRAVEL > MAX_SIZE) {
		printf("第%d躺移动结果:n", *times);
		travelList(list);
	}
	tool->moveTime++;
	if (begPosition != key) {
		shell_sort(list, begPosition, key, tool,times);
	}
	if (key + 1 < endPosition) {
		shell_sort(list, key + 1, endPosition, tool,times);
	}
}

4,直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。设整个排序有n个数，则进行n-1趟插入，即：先将序列中的第1个记录

Tool insert_sort(int* _list) {
	int* newList = (int*)malloc(sizeof(int)*MAX_SIZE);
	Tool tool;
	strcpy_s(tool.name, "直接插入排序");
	tool.begainTime = clock();
	newList[0] = _list[0];
	for (int i = 1; i < MAX_SIZE; i++) { // i 表示开始插入i个元素
		int insertValue = _list[i]; // 插入的值
		int isInsert = false;
		for (int j = 0; j  insertValue) { // 找到插入位置
				for (int k = i; k > j; k--) {
					newList[k] = newList[k - 1];
					tool.moveTime++;
				}
				newList[j] = insertValue;
				isInsert = true;
				break;
			}
		}
		if (!isInsert) {
			newList[i] = insertValue;
		}
	}
	tool.endTime = clock();
	travelList(newList);
	printTool(tool);
	return tool;
}

5,堆排序

void heapAdjust(int* list, int s, int m,Tool* tool)//一次筛选的过程
{
	int min = list[s]; // 假设节点处的值最小
	for (int j = 2 * s; j <= m; j = j * 2)//通过循环沿较大的孩子结点向下筛选
	{
		if (j < m && list[j] < list[j + 1]) {
			j++;//j为较大的记录的下标
			tool->compareTime++;
		} 
		if (min > list[j]) break; // 找到比根大的位置,跳出调整循环,插入节点处
		list[s] = list[j];
		tool->moveTime++;
		s = j;
	}
	list[s] = min;//插入
	tool->moveTime++;
}


void heap_sort(int* _list, int n,Tool* tool)
{
	// 将数组里的元素向后移预留出0的位置,方便逻辑实现
	int* list =(int*) malloc(sizeof(int)*(MAX_SIZE+1));
	// 因此排序长度加一
	n += 1;
	// 元素后移
	for (int i = MAX_SIZE; i > 0; i--) {
		list[i] = _list[i - 1];
	}
	for (int i = n / 2; i > 0; i--)//初始化堆
	{
		heapAdjust(list, i, n,tool);
	}
	for (int i = n; i >0; i--)
	{
		int temp = list[1];
		list[1] = list[i];
		list[i] = temp;//将堆顶记录与未排序的最后一个记录交换
		tool->moveTime++;
		heapAdjust(list, 1, i - 1,tool);//重新调整为顶堆
	}
	// 输出排序结果
	if (MAX_SIZE > MAX_TRAVEL) {
		return;
	}
	for (int i = 1; i <= MAX_SIZE; i++) {
		printf("%dt",list[i]);
		if (!(i % 5)) {
			printf("n");
		}
	}
}

其他还有很多排序,都各有各的好处

开始测试

#include"App6.h"
bool toolIsEmpty(Tool tool) {
	if (!strcmp(tool.name, "")) {
		return true;
	}
	return false;
}
void copyTool(Tool* newT, Tool* oldT) {
	newT->begainTime = oldT->begainTime;
	newT->compareTime = oldT->compareTime;
	newT->endTime = oldT->endTime;
	newT->moveTime = oldT->moveTime;
	strcpy_s(newT->name,oldT->name);
}

bool addTool(Tool tools[], Tool tool) {
	int i = 0;
	while (!toolIsEmpty(tools[i])) {
		i++;
	}
	copyTool(&tools[i], &tool);
	return true;
}

void travelTools(Tool tools[]) {
	for (int i = 0; !toolIsEmpty(tools[i]); i++) {
		printTool(tools[i]);
	}
}

void sortTools(Tool tools[],int key=1) {
	switch (key) {
	case 1: // 运行时间
		for (int i = 0; !toolIsEmpty(tools[i]); i++) {
			long min = tools[i].endTime - tools[i].begainTime;
			for (int j = i; !toolIsEmpty(tools[j]); j++) {
				long big = tools[j].endTime - tools[j].begainTime;
				if (min > big) {
					Tool tool = tools[i];
					tools[i] = tools[j];
					tools[j] = tool;
				}
			}
		}
	}
	travelTools(tools);
}

void menue() {
	Tool tools[6];
	int* list = createRandomIntList();
	int ope = 1; 
	while (ope){
		Tool tool;
		printf("ntt欢迎来到排序综合系统！ntt菜单n
		(1)-- - 直接插入排序n
		(2)-- - 直接选择排序n
		(3)-- - 冒泡排序n
		(4)-- - 快速排序n
		(5)-- - 堆排序n
		(6)-- - 时间效率比较n
		(7)-- - 显示随机数n
		(0)-- - 退出系统n");
		scanf_s("%d", &ope);
		switch (ope)
		{
		case 0:
			printf("正在退出系统n");
			break;
		case 1:
			// 直接插入排序
			tool = insert_sort(list);
			addTool(tools, tool);
			break;
		case 2: //直接选择排序
			tool = zhiJie_sort(list);
			addTool(tools, tool);
			break;
		case 3: // 冒泡排序
			tool = qiPao_sort(list);
			addTool(tools, tool);
			break;
		case 4:// 快速排序
		{
			tool.begainTime = clock();
			int times = 0;
			strcpy_s(tool.name, "shell排序");
			int* _list = copyList(list);
			shell_sort(_list, 0, MAX_SIZE - 1, &tool, ×);
			tool.endTime = clock();
			addTool(tools, tool);
			travelList(_list);
			printf("shell排序成功!n");
			printTool(tool);
		}
			break;
		case 5:// 堆排序
			tool.begainTime = clock();
			strcpy_s(tool.name, "堆排序");
			heap_sort(list, MAX_SIZE - 1,&tool);
			tool.endTime = clock();
			addTool(tools,tool);
			printTool(tool);
			break;
		case 6: //时间效率比较
			sortTools(tools);
			break;
		case 7: //显示随机数
			travelList(list);
			break;
		default:
			printf("输入错误,请重新输入!n");
			break;
		}
	}
}

int main() {
	menue();
	return 0;
}

运行效果

注:规模较小时会输出排序结果,规模较大时结果就没算法的一些属性那么重要,则不输出结果

1,直接插入排序运行效果

2,直接选择排序运行效果

3,冒泡排序运行效果

4,快速排序运行效果

5,堆排序

6,时间比较规模较小时

数据规模较大时

全部代码

#define MAX_SIZE 20
#define MAX_TRAVEL 100
#include
#include 
#include
#include
typedef struct Tool{
	char name[20] = ""; // 记录算法名字
	int compareTime = 0; // 记录比较次数
	int moveTime = 0; //记录移动次数
	long begainTime = 0; // 记录开始时间
	long endTime = 0;// 记录结束时间
};

void travelList(int* list) {
	if (MAX_SIZE > MAX_TRAVEL) {
		printf("随机数组的大小超过了最大遍历数,则不会遍历输出!n");
		return;
	}
	printf("==============开始遍历=================n");
	for (int i = 0; i < MAX_SIZE; i++) {
		if (!(i % 5)) {
			printf("n");
		}
		printf("%dt", list[i]);
	}
	printf("n==============遍历结束=================n");
}

int* createRandomIntList() {
	int* intList = (int*)malloc(sizeof(int)*MAX_SIZE); // 开辟空间
	printf("产生的随机数如下:n");
	for (int i = 0; i < MAX_SIZE; i++) {
		intList[i] = rand() % 100; // 产生[0-100)的随机数
	}
	travelList(intList);
	return intList;
}
int* copyList(int* list) {
	int* newList = (int*)malloc(sizeof(int) * MAX_SIZE);
	for (int i = 0; i < MAX_SIZE; i++) {
		newList[i] = list[i];
	}
	return newList;
}

void printTool(Tool tool) {
	printf("=====================%s============================n",tool.name);
	printf("排序规模(个):%dn",MAX_SIZE);
	printf("程序运行时间:%ld个时钟周期n",tool.endTime - tool.begainTime);
	printf("移动次数:%dn比较次数:%dn",tool.moveTime,tool.compareTime);
	printf("=================================================n");
}


Tool zhiJie_sort(int* _list) {
	int* list = copyList(_list);
	Tool tool;
	strcpy_s(tool.name, "直接排序");
	tool.begainTime = clock();
	for (int i = 0; i < MAX_SIZE; i++) {
		int min = list[i];
		int k = i;
		for (int j = i + 1; j < MAX_SIZE; j++) {
			tool.compareTime++;
			if (min > list[j]) {
				min = list[j];
				k = j;
			}
		}
		if (k != i) {
			int a = list[i];
			list[i] = list[k];
			list[k] = a;
			tool.moveTime++;
		}
	}
	tool.endTime = clock();
	printf("n直接排序成功!n");
	travelList(list);
	printTool(tool);
	return tool;
}

Tool qiPao_sort(int* _list) {
	int* list = copyList(_list);
	Tool tool;
	strcpy_s(tool.name, "气泡排序");
	tool.begainTime = clock();
	for (int i = 0; i < MAX_SIZE; i++) {
		for (int j = 0; j < MAX_SIZE-1-i; j++) {
			tool.compareTime++;
			if (list[j] > list[j + 1]) {
				int a = list[j];
				list[j] = list[j+1];
				list[j+1] = a;
				tool.moveTime++;
			}
		}
	}
	tool.endTime = clock();
	travelList(list);
	printTool(tool);
	return tool;
}

Tool insert_sort(int* _list) {
	int* newList = (int*)malloc(sizeof(int)*MAX_SIZE);
	Tool tool;
	strcpy_s(tool.name, "直接插入排序");
	tool.begainTime = clock();
	newList[0] = _list[0];
	for (int i = 1; i < MAX_SIZE; i++) { // i 表示开始插入i个元素
		int insertValue = _list[i]; // 插入的值
		int isInsert = false;
		for (int j = 0; j  insertValue) { // 找到插入位置
				for (int k = i; k > j; k--) {
					newList[k] = newList[k - 1];
					tool.moveTime++;
				}
				newList[j] = insertValue;
				isInsert = true;
				break;
			}
		}
		if (!isInsert) {
			newList[i] = insertValue;
		}
	}
	tool.endTime = clock();
	travelList(newList);
	printTool(tool);
	return tool;
}


void shell_sort(int* list,int begPosition,int endPosition,Tool* tool,int* times) {
	(*times)++;
	int keyValue = list[begPosition]; // 枢轴值
	int key = begPosition; // 记录空位置
	for (int i = begPosition, j = endPosition; i compareTime++;
		if (keyValue>list[j]) { // 从右边开始比较
			list[key] = list[j];// 将右边小于枢值移到左边
			key = j;// 记录空值位置
			tool->moveTime++;
			while (keyValue >= list[i] && i!=key) {//从左边开始比较
				tool->compareTime++;
				i++;
			}
			if (i == key) {
				break;
			}
			list[key] = list[i];			// i 为空位置
			key = i;
			tool->moveTime++;
		}
	}
	list[key] = keyValue;
	if (MAX_TRAVEL > MAX_SIZE) {
		printf("第%d躺移动结果:n", *times);
		travelList(list);
	}
	tool->moveTime++;
	if (begPosition != key) {
		shell_sort(list, begPosition, key, tool,times);
	}
	if (key + 1 < endPosition) {
		shell_sort(list, key + 1, endPosition, tool,times);
	}
}


void heapAdjust(int* list, int s, int m,Tool* tool)//一次筛选的过程
{
	int min = list[s]; // 假设节点处的值最小
	for (int j = 2 * s; j <= m; j = j * 2)//通过循环沿较大的孩子结点向下筛选
	{
		if (j < m && list[j] < list[j + 1]) {
			j++;//j为较大的记录的下标
			tool->compareTime++;
		} 
		if (min > list[j]) break; // 找到比根大的位置,跳出调整循环,插入节点处
		list[s] = list[j];
		tool->moveTime++;
		s = j;
	}
	list[s] = min;//插入
	tool->moveTime++;
}


void heap_sort(int* _list, int n,Tool* tool)
{
	// 将数组里的元素向后移预留出0的位置,方便逻辑实现
	int* list =(int*) malloc(sizeof(int)*(MAX_SIZE+1));
	// 因此排序长度加一
	n += 1;
	// 元素后移
	for (int i = MAX_SIZE; i > 0; i--) {
		list[i] = _list[i - 1];
	}
	for (int i = n / 2; i > 0; i--)//初始化堆
	{
		heapAdjust(list, i, n,tool);
	}
	for (int i = n; i >0; i--)
	{
		int temp = list[1];
		list[1] = list[i];
		list[i] = temp;//将堆顶记录与未排序的最后一个记录交换
		tool->moveTime++;
		heapAdjust(list, 1, i - 1,tool);//重新调整为顶堆
	}
	// 输出排序结果
	if (MAX_SIZE > MAX_TRAVEL) {
		return;
	}
	for (int i = 1; i <= MAX_SIZE; i++) {
		printf("%dt",list[i]);
		if (!(i % 5)) {
			printf("n");
		}
	}
}
bool toolIsEmpty(Tool tool) {
	if (!strcmp(tool.name, "")) {
		return true;
	}
	return false;
}
void copyTool(Tool* newT, Tool* oldT) {
	newT->begainTime = oldT->begainTime;
	newT->compareTime = oldT->compareTime;
	newT->endTime = oldT->endTime;
	newT->moveTime = oldT->moveTime;
	strcpy_s(newT->name,oldT->name);
}

bool addTool(Tool tools[], Tool tool) {
	int i = 0;
	while (!toolIsEmpty(tools[i])) {
		i++;
	}
	copyTool(&tools[i], &tool);
	return true;
}

void travelTools(Tool tools[]) {
	for (int i = 0; !toolIsEmpty(tools[i]); i++) {
		printTool(tools[i]);
	}
}

void sortTools(Tool tools[],int key=1) {
	switch (key) {
	case 1: // 运行时间
		for (int i = 0; !toolIsEmpty(tools[i]); i++) {
			long min = tools[i].endTime - tools[i].begainTime;
			for (int j = i; !toolIsEmpty(tools[j]); j++) {
				long big = tools[j].endTime - tools[j].begainTime;
				if (min > big) {
					Tool tool = tools[i];
					tools[i] = tools[j];
					tools[j] = tool;
				}
			}
		}
	}
	travelTools(tools);
}

void menue() {
	Tool tools[6];
	int* list = createRandomIntList();
	int ope = 1; 
	while (ope){
		Tool tool;
		printf("ntt欢迎来到排序综合系统！ntt菜单n
		(1)-- - 直接插入排序n
		(2)-- - 直接选择排序n
		(3)-- - 冒泡排序n
		(4)-- - 快速排序n
		(5)-- - 堆排序n
		(6)-- - 时间效率比较n
		(7)-- - 显示随机数n
		(0)-- - 退出系统n");
		scanf_s("%d", &ope);
		switch (ope)
		{
		case 0:
			printf("正在退出系统n");
			break;
		case 1:
			// 直接插入排序
			tool = insert_sort(list);
			addTool(tools, tool);
			break;
		case 2: //直接选择排序
			tool = zhiJie_sort(list);
			addTool(tools, tool);
			break;
		case 3: // 冒泡排序
			tool = qiPao_sort(list);
			addTool(tools, tool);
			break;
		case 4:// 快速排序
		{
			tool.begainTime = clock();
			int times = 0;
			strcpy_s(tool.name, "shell排序");
			int* _list = copyList(list);
			shell_sort(_list, 0, MAX_SIZE - 1, &tool, ×);
			tool.endTime = clock();
			addTool(tools, tool);
			travelList(_list);
			printf("shell排序成功!n");
			printTool(tool);
		}
			break;
		case 5:// 堆排序
			tool.begainTime = clock();
			strcpy_s(tool.name, "堆排序");
			heap_sort(list, MAX_SIZE - 1,&tool);
			tool.endTime = clock();
			addTool(tools,tool);
			printTool(tool);
			break;
		case 6: //时间效率比较
			sortTools(tools);
			break;
		case 7: //显示随机数
			travelList(list);
			break;
		default:
			printf("输入错误,请重新输入!n");
			break;
		}
	}
}

int main() {
	menue();
	return 0;
}

代码写得很赶,当数据规模大的时候还是有很多bug,可能是算法的不稳定性,也很大可能是我考虑不周,很多算法上的细节没处理好,欢迎大家评论,我将认真阅读大家的意见!

数据结构实训项目---比较一些排序

C/C++/C#相关栏目本月热门文章