【C语言】【排序算法】----- 归并排序

由于迩来要测验，很久没有发博客了，非常歉仄各人对我的支持。之后我会不绝更新博客，继续创作出高质量的文章，盼望能帮到各人！


一、归并排序根本头脑

归并排序（MERGE-SORT）是创建在归并操纵上的一种有用的排序算法,该算法是采取分治法，即分解和归并。先使每个子序列有序，再使子序列段间有序，末了归并成一个有序数组。

二、递归实现

• 根本思绪：
  ① 申请一个空间tmp，巨细为两个已经排好序列之和，该空间用来存放归并后的序列。
  ② 设定两个下标，分别指向两段已排好序的起始位置。
  ③ 比力两个下标所指向的元素巨细，选择较小的元素放入到归并空间，而且移动指针指向下一位置。
  ④ 不绝重复步调③，直到当某一指针到达序列尾部。
  ⑤ 然后将另一序列剩下的全部元素直接插入到归并序列的尾端。
  
• 代码实现：
  

1. //归并排序递归
2. void _MergeSort(int* a, int* tmp, int begin, int end)
3. {
4.         //只有一个元素或不存在这样的区间时
5.         if (begin >= end)
6.         {
7.                 return;
8.         }
9.         //分成两段区间，分别有序时在进行归并
10.         int mid = (begin + end) / 2;
11.         _MergeSort(a, tmp, begin, mid);
12.         _MergeSort(a, tmp, mid + 1, end);
13.         //第一个数组的两端
14.         int begin1 = begin, end1 = mid;
15.         //第二个数组的两端
16.         int begin2 = mid + 1, end2 = end;
17.         //由于两段数组都是从begin开始，因此将begin给i确保其在相同的区间上
18.         int i = begin;
19.         while (begin1 <= end1 && begin2 <= end2)
20.         {
21.                 if (a[begin1] < a[begin2])
22.                 {
23.                         tmp[i++] = a[begin1++];
24.                 }
25.                 else
26.                 {
27.                         tmp[i++] = a[begin2++];
28.                 }
29.         }
30.         //有一个排完了，剩下的直接放入
31.         while (begin1 <= end1)
32.         {
33.                 tmp[i++] = a[begin1++];
34.         }
35.         while (begin2 <= end2)
36.         {
37.                 tmp[i++] = a[begin2++];
38.         }
39.         //tmp已经归并成功，将tmp复制会数组a中
40.         memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
41. }
43. void MergeSort(int* a, int n)
44. {
45.         assert(a);
46.         //创建一个临时数组
47.         int* tmp = (int*)malloc(sizeof(int) * n);
48.         if (tmp == NULL)
49.         {
50.                 perror("malloc fail");
51.                 return;
52.         }
53.         _MergeSort(a, tmp, 0, n - 1);
54.         free(tmp);
55.         tmp = NULL;
56. }

复制代码

三、非递归实现

非递归实现是一种迭代式的排序算法，它克制了递归所带来的额外开销，通常利用循环的方式来办理。

• 根本思绪:
  将一个数组通过gap分为几组举行归并，然后让gap每次扩大2倍，但gap < 数组元素个数的巨细。
  
• 越界标题：
  我们可以很轻易想到代码实现的思绪，但难点就在于怎样控制每一段区间的界限，从而克制下标越界的标题。
  这里有三种大概会出现越界的标题，分别为：
  ①当第一段区间末端end1大于或即是该区间元素个数。
  ②当第二段区间不存在，必要举行修改区间。
  办理方法：
  ①第一种标题我们可以让其直接break。由于其右边没数据存在，因此就算进入循环中剩余的元素也不会发生改变。
  ②第二种标题，当第二段区间bgein2大于或即是该区间元素个数时，不进入循环，直接break；当第二段区间的末端end2大于或即是n时，我们只需将end2修改为n-1即可，由于n-1恰恰为整个数组的界限。
  
• 代码实现：
  留意：
  当我们将临时数组tmp拷贝回原数组时：
  ①起始点为：tmp + i，由于i是每次归并后第一个元素的第一个位置。
  ②拷贝归去的元素个数：end2 - i + 1。由于end2指向的每次归并后第二组元素的末了一个位置，而i所指向的是每次归并后的第一个元素的第一个位置。
  

1. //归并排序的非递归实现
2. void MergeSortNonR(int* a, int n)
3. {       
4.         //开辟一个临时数组，来存取排好序的元素
5.         int* tmp = (int*)malloc(sizeof(int) * n);
6.         if (tmp == NULL)
7.         {
8.                 perror("malloc fail");
9.                 return;
10.         }
11.         int gap = 1;
12.         int i = 0;
13.         int j = 0;
14.         while (gap < n)
15.         {
16.                 for (i = 0; i < n; i += 2 * gap)
17.                 {
18.                         //[i,i+gap-1]  [i+gap,i+2*gap-1}
19.                         int begin1 = i;
20.                         int end1 = i + gap - 1;
21.                         int begin2 = i + gap;
22.                         int end2 = i + 2 * gap - 1;
23.                         j = i;
24.                         // 考虑end1 begin2 end2三者分别越界的问题
25.                         if (end1 >= n)
26.                         {
27.                                 break;
28.                         }
29.                         else if (begin2 >= n)
30.                         {
31.                                 break;
32.                         }
33.                         else if (end2 >= n)
34.                         {
35.                                 end2 = n - 1;
36.                         }
37.                         while (begin1 <= end1 && begin2 <= end2)
38.                         {
39.                                 if (a[begin1] < a[begin2])
40.                                 {
41.                                         tmp[j++] = a[begin1++];
42.                                 }
43.                                 else
44.                                 {
45.                                         tmp[j++] = a[begin2++];
46.                                 }
47.                         }
48.                         while (begin1 <= end1)
49.                         {
50.                                 tmp[j++] = a[begin1++];
51.                         }
52.                         while (begin2 <= end2)
53.                         {
54.                                 tmp[j++] = a[begin2++];
55.                         }
56.                         memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
57.                 }
58.                 gap *= 2;
59.         }
60.         free(tmp);
61.         tmp = NULL;
62. }

复制代码

四、服从分析

归并排序的时间复杂度为：O(N * log2N) 由于向下递归的时间复杂度为O(log2N)，再遍历一次数组的时间复杂度为O(N)。
归并排序的空间复杂度为：O(N) 必要创建一个辅助数组tmp用来存归并后的序列。
归并排序的稳固性：稳固。根据arr[begin1] <= arr[begin2]，我们可以得出类似的元素先排第一组，然后再排第二组的元素，因此类似元素的相对位置不会改变。