归并排序算法

归并排序

源码
验证
- 排序验证
- 耗时测试
使用方法
参考

源码

#define _CRT_SECURE_NO_WARNINGS //处理scanf报错问题
#include 
#include 

#define DEBUG_SWITCH 1
#if DEBUG_SWITCH
#define DEBUG_INFO(format, ...) printf("LINE: %d: "format"\n", __LINE__, ##__VA_ARGS__)
#else
#define DEBUG_INFO(format, ...) 
#endif

#define TRUE  1
#define FALSE 0

typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
typedef unsigned long int uint32_t;
typedef unsigned long long int uint64_t;

#define ARR_SIZE(arr,type) (sizeof(arr)/sizeof(type))

typedef struct
{
	uint8_t a;
	uint64_t b;
}test_def;

typedef struct merge_sort_def
{
	uint64_t len;
	uint8_t monotonicity;
	uint64_t *raw_data_point;
	uint64_t *temp_data_point;
	uint8_t (*merge_compare_callback)(struct merge_sort_def *data, uint64_t a, uint64_t b);
	uint8_t (*merge_sort_output)(struct merge_sort_def *data, uint64_t *output_buffer);
}merge_sort_def;

static uint8_t merge_compare(merge_sort_def *data, uint64_t a, uint64_t b)
{
#define SORT_DATA_TYPE test_def
#define SORT_CMP_DATA_NAME b
	
	return ((((SORT_DATA_TYPE *)data->raw_data_point[a])->SORT_CMP_DATA_NAME >= ((SORT_DATA_TYPE *)data->raw_data_point[b])->SORT_CMP_DATA_NAME) ? \
		data->monotonicity : !data->monotonicity);
}

uint8_t merge_sort_output(merge_sort_def *data, uint64_t *output_buffer)
{
#define SORT_DATA_TYPE test_def
#define SORT_CMP_DATA_NAME b

	uint8_t ret = FALSE;

	for (uint64_t i = 0; i < data->len; i++)
	{
#if DEBUG_SWITCH
		printf("%ld ", ((SORT_DATA_TYPE *)data->raw_data_point[i])->SORT_CMP_DATA_NAME);
#endif
		((SORT_DATA_TYPE *)output_buffer)[i].SORT_CMP_DATA_NAME = ((SORT_DATA_TYPE *)data->raw_data_point[i])->SORT_CMP_DATA_NAME;
	}
	printf("\r\n");

	return ret;
}

static void merge(merge_sort_def *data, uint64_t left, uint64_t mid, uint64_t right)
{
	uint64_t i = left;//左序列指针
	uint64_t j = mid + 1;//右序列指针
	uint64_t t = 0;//临时数组指针
	while (i <= mid && j <= right) 
	{
		if (data->merge_compare_callback(data, i,j))
		{
			data->temp_data_point[t++] = data->raw_data_point[i++];
		}
		else
		{
			data->temp_data_point[t++] = data->raw_data_point[j++];
		}
	}
	while (i <= mid) 
	{//将左边剩余元素填充进temp中
		data->temp_data_point[t++] = data->raw_data_point[i++];
	}
	while (j <= right) 
	{//将右序列剩余元素填充进temp中
		data->temp_data_point[t++] = data->raw_data_point[j++];
	}
	t = 0;
	//将temp中的元素全部拷贝到原数组中
	while (left <= right) 
	{
		data->raw_data_point[left++] = data->temp_data_point[t++];
	}
}

static void merge_sort(merge_sort_def *data, uint64_t left, uint64_t right)
{
	if (left < right) 
	{
		uint64_t mid = (left + right) / 2;
		merge_sort(data, left, mid);//左边归并排序，使得左子序列有序
		merge_sort(data, mid + 1, right);//右边归并排序，使得右子序列有序
		merge(data, left, mid, right);//将两个有序子数组合并操作
	}
}

uint8_t merge_sort_init(merge_sort_def *data, uint64_t len, uint8_t monotonicity, \
	uint64_t *raw_data_buf, uint64_t *temp_data_buf, \
	uint8_t(*merge_compare_callback)(struct merge_sort_def *data, uint64_t a, uint64_t b), uint8_t(*merge_sort_output)(struct merge_sort_def *data, uint64_t *output_buffer))
{
	uint8_t ret = FALSE;
	if ((data != NULL) && (raw_data_buf != NULL) && (temp_data_buf != NULL) && (merge_compare != NULL) && (len >= (uint64_t)2))
	{
		data->len = len;
		data->monotonicity = monotonicity & (uint8_t)0x01;
		data->raw_data_point = raw_data_buf;
		data->temp_data_point = temp_data_buf;
		data->merge_compare_callback = merge_compare;
		data->merge_sort_output = merge_sort_output;
		ret = TRUE;
	}
	else
	{
		/* No thing */
	}
	return ret;
}

#define ARR_MAX 10
int main()
{
	static test_def data[ARR_MAX] = { 0 };
	static test_def output_data[ARR_MAX] = { 0 };
	static uint64_t merge_sort_raw_data[ARR_MAX] = { 0 };
	static uint64_t merge_sort_temp_data[ARR_MAX] = { 0 };

	static merge_sort_def merge_sort_data = { 0 };
		 
	for (uint64_t i = 0; i < ARR_SIZE(data, test_def); i++)
	{
		data[i].a = rand();
		data[i].b = rand();
		merge_sort_raw_data[i] = (uint64_t)&data[i];
#if DEBUG_SWITCH
		printf("%ld ", data[i].b);
#endif
	}
	printf("\r\n");

	uint64_t start, end;
	start = GetTickCount();
	merge_sort_init(&merge_sort_data, ARR_SIZE(data, test_def), TRUE, \
		merge_sort_raw_data, merge_sort_temp_data, \
		&merge_compare, &merge_sort_output);
	merge_sort(&merge_sort_data, 0, merge_sort_data .len - 1);
	merge_sort_data.merge_sort_output(&merge_sort_data, (uint64_t *)output_data);
	end = GetTickCount();
	printf("start: %lld ms  end: %lld ms  time: %lld ms\n", start, end, end - start);


	start = GetTickCount();
	merge_sort_init(&merge_sort_data, ARR_SIZE(data, test_def), FALSE, \
		merge_sort_raw_data, merge_sort_temp_data, \
		&merge_compare, &merge_sort_output);
	merge_sort(&merge_sort_data, 0, merge_sort_data.len - 1);
	merge_sort_data.merge_sort_output(&merge_sort_data, (uint64_t *)output_data);
	end = GetTickCount();
	printf("start: %lld ms  end: %lld ms  time: %lld ms\n", start, end, end - start);
}

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

验证

排序验证

产生10个随机数进行排序

耗时测试

产生0XFFFFFF个数据进行排序

在这里插入图片描述

使用方法

定义比较回调函数

只需要修改相应的宏即可
SORT_DATA_TYPE 结构体数组类型
SORT_CMP_DATA_NAME 需要对比的数据类型
如果存在多层嵌套,需要自己修改成对应的大小比较函数即可

static uint8_t merge_compare(merge_sort_def *data, uint64_t a, uint64_t b)
{
#define SORT_DATA_TYPE test_def
#define SORT_CMP_DATA_NAME b
	
	return ((((SORT_DATA_TYPE *)data->raw_data_point[a])->SORT_CMP_DATA_NAME >= ((SORT_DATA_TYPE *)data->raw_data_point[b])->SORT_CMP_DATA_NAME) ? \
		data->monotonicity : !data->monotonicity);
}
1
2
3
4
5
6
7
8

定义结果获取函数

若输入与输出数据类型相同,只需要修改相应的宏即可
若不同,则可自行修改获取排序结果

uint8_t merge_sort_output(merge_sort_def *data, uint64_t *output_buffer)
{
#define SORT_DATA_TYPE test_def
#define SORT_CMP_DATA_NAME b

	uint8_t ret = FALSE;

	for (uint64_t i = 0; i < data->len; i++)
	{
#if DEBUG_SWITCH
		printf("%ld ", ((SORT_DATA_TYPE *)data->raw_data_point[i])->SORT_CMP_DATA_NAME);
#endif
		((SORT_DATA_TYPE *)output_buffer)[i].SORT_CMP_DATA_NAME = ((SORT_DATA_TYPE *)data->raw_data_point[i])->SORT_CMP_DATA_NAME;
	}
	printf("\r\n");

	return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

定义缓存

数据输入缓存
数据输出缓存(不能和输入共用,用于接收排序后的结果)
排序输入缓存(存储输入数据的地址)
排序临时缓存
归并排序句柄

static test_def input_data[ARR_MAX] = { 0 };
static test_def output_data[ARR_MAX] = { 0 };
static uint64_t merge_sort_raw_data[ARR_MAX] = { 0 };
static uint64_t merge_sort_temp_data[ARR_MAX] = { 0 };

static merge_sort_def merge_sort_data = { 0 };
1
2
3
4
5
6

初始化排序输入缓存

获取输入数据数组的地址

for (uint64_t i = 0; i < ARR_SIZE(input_data, test_def); i++)
{
	merge_sort_raw_data[i] = (uint64_t)&input_data[i];
}
1
2
3
4

定义并初始化排序句柄

static merge_sort_def merge_sort_data = { 0 };
merge_sort_init(&merge_sort_data, ARR_SIZE(input_data, test_def), TRUE, \
	merge_sort_raw_data, merge_sort_temp_data, \
	&merge_compare, &merge_sort_output);
1
2
3
4

运行排序

merge_sort_run(&merge_sort_data);
1

获取结果

merge_sort_data.merge_sort_output(&merge_sort_data, (uint64_t *)output_data);
1

参考

图解排序算法(四)之归并排序

相关阅读:
java计算机毕业设计大学校友信息管理系统源码+系统+lw文档+mysql数据库+部署
 React 任务调度
 OpenHarmony环境搭建报错： ImportError: cannot import name ‘VERSION‘ from ‘hb.__main__‘
黑猫带你学Makefile第10篇：如何将未被编译的代码/自己写的驱动编译进uboot
Makefile 变量值
 探索Django：从项目创建到图片上传的全方位指南
 OS·03包管理器
 掌握Docker：让你的应用轻松部署和管理
 大白话讲Java的锁
 k8s的coreDNS添加自定义hosts
原文地址：https://blog.csdn.net/m0_38139533/article/details/126570305