排序算法---归并排序

原创不易，转载请注明出处。欢迎点赞收藏~

归并排序是一种常见的排序算法，它采用了分治的思想。它将一个待排序的数组递归地分成两个子数组，分别对两个子数组进行排序，然后将排好序的子数组合并成一个有序数组。

具体的归并排序过程如下：

1. 将待排序的数组不断地二分，直到每个子数组只剩下一个元素。
2. 对每个子数组进行合并操作，即将两个有序的子数组合并成一个有序数组。合并操作是通过比较两个子数组的首元素，选取较小的元素放入临时数组中，然后移动相应的指针，重复此过程直到其中一个子数组为空，再将另一个子数组中的剩余部分直接放入临时数组中。
3. 重复步骤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()函数对数组进行归并排序，并打印原始数组和排序后的数组。

最终输出的结果是原始数组和排序后的数组。你可以根据需要修改输入的数组和数组长度，来验证归并排序的效果。

运行如上代码，你可以看到以下输出：