解释归并排序法
时间: 2023-06-28 07:14:15 浏览: 45
归并排序法是一种基础的排序算法,其基本思想是将待排序的序列递归地分成两个子序列,分别进行排序,然后再将两个已排序的子序列合并成一个有序序列。具体过程如下:
1. 将待排序的序列平均分成两个子序列,然后分别对这两个子序列进行排序(递归调用归并排序)。
2. 合并两个已排序的子序列,生成一个新的有序序列。
下面是用C语言实现归并排序的示例代码:
```c
void merge(int arr[], int left, int mid, int right, int temp[])
{
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = 0; i < k; i++) {
arr[left + i] = temp[i];
}
}
void merge_sort(int arr[], int left, int right, int temp[])
{
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid, temp);
merge_sort(arr, mid + 1, right, temp);
merge(arr, left, mid, right, temp);
}
}
void sort(int arr[], int len)
{
int temp[len];
merge_sort(arr, 0, len - 1, temp);
}
```
在这段代码中,我们使用了递归来实现归并排序。首先定义一个 `merge` 函数,用于将两个已排序的子序列合并成一个新的有序序列。在 `merge` 函数中,我们定义三个指针 `i`、`j` 和 `k`,分别指向左子序列、右子序列和临时数组的起始位置。然后依次比较左右两个子序列中的元素,将较小的元素放入临时数组中,直到一个子序列遍历结束。然后将另一个子序列中剩余的元素依次放入临时数组中。最后将临时数组中的元素复制回原数组中。
接着定义一个 `merge_sort` 函数,用于对序列进行递归排序。在 `merge_sort` 函数中,我们首先判断左右边界是否相等,如果不相等,则计算出序列的中间位置 `mid`,然后递归地将左右两部分进行排序,最后再将两个已排序的子序列合并起来。
最后,我们定义一个 `sort` 函数,用于调用 `merge_sort` 函数对整个序列进行排序。
归并排序的时间复杂度为 $O(n\log n)$,是一种稳定的排序算法。