c语言数据结构实现55、7、45、69、70、24、21、1、16、 37归并排序
时间: 2023-07-03 13:07:22 浏览: 34
归并排序是一种稳定的排序算法,它的基本思想是将待排序序列分成若干个子序列,每个子序列都是有序的,然后再将子序列合并成一个有序的序列。
具体实现过程如下:
1. 将待排序的序列拆分成若干个子序列,每个子序列都是有序的。
2. 将相邻的子序列进行合并,得到新的有序序列。
3. 重复步骤2,直到所有的子序列都合并为一个序列。
下面是C语言实现归并排序的代码:
```c
#include <stdio.h>
// 合并两个有序序列
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
// 将左半部分复制到L数组
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
// 将右半部分复制到R数组
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 合并左右两个有序序列
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 处理剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序
void merge_sort(int arr[], int left, int right)
{
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main()
{
int arr[] = {55, 7, 45, 69, 70, 24, 21, 1, 16, 37};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
merge_sort(arr, 0, n - 1);
printf("排序后:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
```
输出结果为:
```
排序前:55 7 45 69 70 24 21 1 16 37
排序后:1 7 16 21 24 37 45 55 69 70
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)