前言
一种将无序数组进行排序的方法。
归并排序，相关定义可以参考wiki：
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
主要思想有2：
- 有序数组。在插入排序中也有此思想
- 合并两两有序数组，通过引入额外的临时数组实现。
本文代码基本未优化，是一种原始逻辑的体现。
环境
编辑器：vs2019
文件：.c类型
正文
代码参考：
#include <stdio.h>
// 归并排序，主要思想：合并两个有序数组，通过引入额外的临时数组实现。
// 递归归并排序，每一次递归，改变一次有序数组长度。
// 普通归并排序，从小到大
void merge_sort_normal(int source_array[], int source_array_length)
{
int start; // 两两分组的总起点索引
int* b = (int*)malloc(source_array_length * sizeof(int)); // 引入临时数组， 临时数组存放每次排序后的结果。
// 分组, 每组元素数量：1, 2, 4, 8 ...
for (int gap = 1; gap < source_array_length; gap += gap)
{
// 合并两两分组
for (start = 0; start < source_array_length; start += gap * 2)
{
// 临时数组的索引
int b_index = start;
// 左边数组的起点索引
int start_left = start;
// 左边数组的结束索引
int end_left = start_left + gap - 1;
// 右边数组的起点索引
int start_right = start + gap;
// 右边数组的结束索引
int end_right = start_right + gap - 1;
// 1. 当左边数组不满时,或没有右边数组时
if (end_left >= source_array_length - 1)
{
for (; b_index < source_array_length; b_index++)
{
b[b_index] = source_array[b_index];
}
break;
}
// 2. 当右边数组不满时
if (end_right > source_array_length - 1)
{
end_right = source_array_length - 1;
}
// 3. 开始合并两数组
while (start_left <= end_left && start_right <= end_right)
{
if (source_array[start_right] > source_array[start_left])
{
b[b_index] = source_array[start_left];
b_index++;
start_left++;
}
else
{
b[b_index] = source_array[start_right];
b_index++;
start_right++;
}
}
// 4. 经过【3】步骤的合并，存在某个数组没有完全插入临时数组的情况
// 当左数组未插完
while (start_left <= end_left)
{
b[b_index] = source_array[start_left];
b_index++;
start_left++;
}
// 当右数组未插完
while (start_right <= end_right)
{
b[b_index] = source_array[start_right];
b_index++;
start_right++;
}
}
// 每次两两分组合并后， 都需要将临时数组的值赋值回原数组。
if (source_array != b)
{
for (int i = 0; i < source_array_length; i++)
{
source_array[i] = b[i];
}
}
}
}
// 递归归并排序，从小到大
// 其中额外引入gap，初始值设为1
void merge_sort_recursive(int source_array[], int source_array_length, int gap)
{
int start;
int* b = (int*)malloc(source_array_length * sizeof(int));
for (start = 0; start < source_array_length; start += gap * 2)
{
int b_index = start;
int start_left = start;
int end_left = start_left + gap - 1;
int start_right = start + gap;
int end_right = start_right + gap - 1;
if (end_left >= source_array_length - 1)
{
for (; b_index < source_array_length; b_index++)
{
b[b_index] = source_array[b_index];
}
break;
}
if (end_right > source_array_length - 1)
{
end_right = source_array_length - 1;
}
while (start_left <= end_left && start_right <= end_right)
{
if (source_array[start_right] > source_array[start_left])
{
b[b_index] = source_array[start_left];
b_index++;
start_left++;
}
else
{
b[b_index] = source_array[start_right];
b_index++;
start_right++;
}
}
while (start_left <= end_left)
{
b[b_index] = source_array[start_left];
b_index++;
start_left++;
}
while (start_right <= end_right)
{
b[b_index] = source_array[start_right];
b_index++;
start_right++;
}
}
if (source_array != b)
{
for (int i = 0; i < source_array_length; i++)
{
source_array[i] = b[i];
}
}
gap += gap;
if (gap >= source_array_length)
{
return 0;
}
merge_sort_recursive(source_array, source_array_length, gap);
}
int* upset_array(int source_list[], int source_list_length)
{
for (int i = 0; i < source_list_length; i++)
{
int rand_index = rand() % source_list_length;
int tmp_value = source_list[i];
source_list[i] = source_list[rand_index];
source_list[rand_index] = tmp_value;
}
return source_list;
}
int main()
{
// 生成随机测试列表
int test_list[20];
int test_list_length = sizeof(test_list) / sizeof(int);
printf("测试列表： \n");
for (int i = 0; i < test_list_length; i++)
{
test_list[i] = rand() % 100;
printf("%d ", test_list[i]);
}
printf("\n");
// 普通归并排序
merge_sort_normal(test_list, test_list_length);
printf("普通归并排序结果： \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
// 打乱数组
upset_array(test_list, test_list_length);
printf("打乱测试列表： \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
// 递归归并排序
merge_sort_recursive(test_list, test_list_length, 1);
printf("递归归并排序结果： \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
return 0;
}
执行结果参考：
image.png
