排序算法---归并排序
原创不易，转载请注明出处。欢迎点赞收藏~
归并排序是一种常见的排序算法，它采用了分治的思想。它将一个待排序的数组递归地分成两个子数组，分别对两个子数组进行排序，然后将排好序的子数组合并成一个有序数组。
具体的归并排序过程如下：
- 将待排序的数组不断地二分，直到每个子数组只剩下一个元素。
- 对每个子数组进行合并操作，即将两个有序的子数组合并成一个有序数组。合并操作是通过比较两个子数组的首元素，选取较小的元素放入临时数组中，然后移动相应的指针，重复此过程直到其中一个子数组为空，再将另一个子数组中的剩余部分直接放入临时数组中。
- 重复步骤2，直到所有的子数组都被合并成一个有序数组。
归并排序的时间复杂度为 O(nlogn)，其中 n 表示待排序数组的长度。这是因为在每一层递归中，需要将所有的子数组都进行合并，而合并两个长度为 n 的有序数组的时间复杂度为 O(n)。总共需要进行 logn 层的递归，因此时间复杂度为 O(nlogn)。
归并排序的空间复杂度为 O(n)，主要是由于合并过程中需要使用一个临时数组来存储排序结果。
归并排序是一种稳定的排序算法，适用于各种规模的数据集。但由于它需要额外的空间来存储临时数组，所以在处理大规模数据时，可能会占用较多的内存。
以下是一个基于C语言的归并排序示例：
#include <stdio.h>
// 合并两个有序数组
void merge(int arr[], int left[], int leftSize, int right[], int rightSize)
{
int i = 0, j = 0, k = 0;
// 比较两个子数组的元素，将较小的元素放入原始数组arr中
while (i < leftSize && j < rightSize)
{
if (left[i] <= right[j])
{
arr[k++] = left[i++];
}
else
{
arr[k++] = right[j++];
}
}
// 将剩余部分的元素放入arr中
while (i < leftSize)
{
arr[k++] = left[i++];
}
while (j < rightSize)
{
arr[k++] = right[j++];
}
}
// 归并排序
void merge_sort(int arr[], int size)
{
// 递归终止条件：当数组只有一个元素时，无需继续划分
if (size <= 1)
{
return;
}
int mid = size / 2;
int left[mid];
int right[size - mid];
// 将数组划分为两个子数组
for (int i = 0; i < mid; i++)
{
left[i] = arr[i];
}
for (int i = mid; i < size; i++)
{
right[i - mid] = arr[i];
}
// 对两个子数组分别进行归并排序
merge_sort(left, mid);
merge_sort(right, size - mid);
// 合并两个有序子数组
merge(arr, left, mid, right, size - mid);
}
int main()
{
int arr[] = {7, 2, 4, 1, 5, 3};
int size = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组:\n");
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
merge_sort(arr, size);
printf("\n排序后的数组:\n");
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
putchar('\n');
return 0;
}
这段代码实现了归并排序算法。归并排序是一种基于分治思想的排序算法，它将待排序的数组分成两个子数组，分别进行排序，然后合并两个有序的子数组，从而得到完整的有序数组。
代码中的merge()函数用于合并两个有序数组。它通过比较两个子数组的元素，将较小的元素依次放入原始数组arr中。最后，将剩余部分的元素放入原始数组中，以确保所有元素都被归并到正确的位置。
merge_sort()函数是归并排序的核心部分。它首先递归地将数组划分为两个子数组，然后对这两个子数组分别调用merge_sort()函数进行排序。最后，调用merge()函数将两个有序的子数组合并为一个有序数组。
在main()函数中，我们声明了一个整型数组arr并初始化了一些元素。然后，我们调用merge_sort()函数对数组进行归并排序，并打印原始数组和排序后的数组。
最终输出的结果是原始数组和排序后的数组。你可以根据需要修改输入的数组和数组长度，来验证归并排序的效果。
运行如上代码，你可以看到以下输出：
