归并排序算法

归并排序

1算法介绍

和选择排序一样，归并排序的性能不受输入数据的影响，但体现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。归并排序是创建在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
2根本头脑

根本思路就是将数组分成二组 A，B，如果这二组组内的数据都是有序的，那么就可以 很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将 A，B 组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以以为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。如许通过先递归的分解数列，再合并数列就完成了归并排序。

1. #include <stdio.h>
3. void find(int arr[], int left, int mid, int right)
4. {
5.     int i, j, k;             // 定义索引变量
6.     int n1 = mid - left + 1; // 计算左边子数组的长度
7.     int n2 = right - mid;    // 计算右边子数组的长度
8.     int L[n1], R[n2];        // 创建左右两个临时数组
9.     for (i = 0; i < n1; i++)
10.     {
11.         L[i] = arr[left + i]; // 将左子数组元素复制到L中
12.     }
13.     for (j = 0; j < n2; j++)
14.     {
15.         R[j] = arr[mid + 1 + j]; // 将右子数组元素复制到R中
16.     }
17.     i = 0;    // 初始化左子数组索引
18.     j = 0;    // 初始化右子数组索引
19.     k = left; // 初始化合并后数组的起始位置
20.     while (i < n1 && j < n2)
21.     {
22.         if (L[i] <= R[j])  // 当左右子数组都未完全遍历时，进行合并操作
23.         {                  // 如果左子数组的当前元素小于等于右子数组的当前元素
24.             arr[k] = L[i]; // 将左子数组的元素放入合并后的数组
25.             i++;           // 移动左子数组的索引
26.         }
27.         else
28.         {
29.             arr[k] = R[j]; // 将右子数组的元素放入合并后的数组
30.             j++;           // 移动右子数组的索引
31.         }
32.         k++; // 移动合并后数组的索引
33.     }
34.     while (i < n1)
35.     {                  // 如果左子数组还有剩余元素
36.         arr[k] = L[i]; // 将左子数组的剩余元素放入合并后的数组
37.         i++;           // 移动左子数组的索引
38.         k++;           // 移动合并后数组的索引
39.     }
40.     while (j < n2)
41.     {                  // 如果右子数组还有剩余元素
42.         arr[k] = R[j]; // 将右子数组的剩余元素放入合并后的数组
43.         j++;           // 移动右子数组的索引
44.         k++;           // 移动合并后数组的索引
45.     }
46.     return;
47. }
48. void merge(int arr[], int left, int right)
49. {
50.     if (left < right)
51.     {                                        // 如果左边界小于右边界，说明还有多个元素需要排序
52.         int mid = left + (right - left) / 2; // 计算中点，避免溢出
53.         merge(arr, left, mid);               // 对左子数组进行归并排序
54.         merge(arr, mid + 1, right);          // 对右子数组进行归并排序
55.         find(arr, left, mid, right);         // 合并两个已排序的子数组
56.     }
57.     return;
58. }
60. int main()
61. {
62.     int arr[] = {38, 27, 43, 3, 9, 82, 10};
63.     int n = sizeof(arr) / sizeof(arr[0]);
64.     merge(arr, 0, n - 1); // 调用归并排序函数，对数组进行排序
65.     printf("排序后为: \n");
66.     for (int i = 0; i < n; i++)
67.     {
68.         printf("%d ", arr[i]);
69.     }
70.     printf("\n");
71.     return 0;
72. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。