数学建模社区-数学中国

标题: 【基于C的排序算法】归并排序 [打印本页]

作者: 杨利霞 时间: 2022-9-14 16:22
标题: 【基于C的排序算法】归并排序
【基于C的排序算法】归并排序

前言
本文基于C语言来分享一波笔者对于排序算法的归并排序的学习心得与经验，由于水平有限，纰漏难免，欢迎指正交流。

归并排序
基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

合并的思想其实和有道题目的思想如出一辙：

我们考虑新开一个数组来放入排序好的值，要不改变顺序的话就要用尾插，让nums1和nums2数组元素的较小值尾插到新数组中，两个数组总会有一个先插完，另一个数组就把剩下的全部尾插接在新数组后面。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gsgj7Cmx-1662793985599)(https://typora-picture-1313051246.cos.ap-beijing.myqcloud.com/归并原理.gif)]

int* merge(int* nums1, int m, int* nums2, int n)
{
int* arr = (int*)malloc((m + n));
if(arr == NULL)
{
      perror("malloc fail");
      return;
}

int p1 = 0;
int p2 = 0;
int cnt = 0;
while(p1 < m && p2 < n)
{
      if(nums1[p1] < nums2[p2])
      {
         arr[cnt++] = nums1[p1++];
      }
      else
      {
         arr[cnt++] = nums2[p2++];
      }
}
while(p1 < m)
      arr[cnt++] = nums1[p1++];

while(p2 < n)
      arr[cnt++] = nums2[p2++];

return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
所谓的合并就是利用这样尾插的思路，我们就想到要把原数组分解成两个有序子序列来合并，那么如何将原数组分解成有序子序列呢？容易想到用递归，其实非递归（迭代）也能实现，我们接下来具体来看看实现方法。

递归实现
通过二分分割出两个子序列，然后进行递归，先左后右，不断分割直到子序列仅有一个元素时子序列一定有序，这时候就可以往回退了，等到左右子序列都退回后就可以归并了，不过不能直接归并到原数组，因为会覆盖而丢失值，不妨归并到另一个辅助数组，归并后再拷贝回原数组，思想就是前面讲的合并的思想。

void _MergeSort(int* arr, int* tmp, int left, int right)
{
assert(arr);

if (left >= right)//递归结束条件不要漏了
      return;

int mid = (right - left) / 2 + left;

//划分左右子区间[left, mid]和[mid + 1, right]
_MergeSort(arr, tmp, left, mid);
_MergeSort(arr, tmp, mid + 1, right);

//归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
      if (arr[begin1] < arr[begin2])
         tmp[i++] = arr[begin1++];
      else
         tmp[i++] = arr[begin2++];
}

while (begin1 <= end1)
      tmp[i++] = arr[begin1++];
while (begin2 <= end2)
      tmp[i++] = arr[begin2++];

//拷贝回原数组——归并哪部分就拷贝哪部分回去
//而不是拷贝整个数组回去
memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));
}

void MergeSort(int* arr, int left, int right)
{
assert(arr);

int* tmp = (int*)malloc((right - left + 1) * sizeof(int));
if (tmp == NULL)
{
      perror("malloc fail");
      return;
}

_MergeSort(arr, tmp, left, right);

free(tmp);
tmp = NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
非递归实现
直接在原数组基础上归并，设gap是子区间元素个数，从gap = 1开始，因为仅有一个元素的子区间一定有序。为了方便，我们把gap=1叫做第一层，以此类推。

不同的gap值代表所在层数不同，每一层都是从左到右两组为一对地取对配对归并，i就是每对起始位置，之所以更新i的时候要i += 2 * gap是因为每队两组、每组gap个元素，所以要让i跑到下一对的起始位置的话不就要跳过一整对的空间嘛。

还要注意区间的取值，每个区间就是一组，就有gap个元素。

整体拷贝遇到越界就会比较难搞，所以我们这里用部分拷贝的思路，每次归并后直接拷贝，要注意一下指针偏移量不是begin1而是i，因为begin1已经在归并过程中被改变了。

代码实现

void MergeSortNonR(int* arr, int sz)
{
assert(arr);

int* tmp = (int*)malloc(sz * sizeof(int));
if (tmp == NULL)
{
      perror("malloc fail");
      return;
}

int gap = 1;
while (gap < sz)
{
      for (int i = 0; i < sz; i += 2 * gap)
      {
         int begin1 = i, end1 = begin1 + gap - 1;
         int begin2 = end1 + 1, end2 = begin2 + gap - 1;
         int j = begin1;

         //归并
         while (begin1 <= end1 && begin2 <= end2)
         {
            if (arr[begin1] < arr[begin2])
                  tmp[j++] = arr[begin1++];
            else
                  tmp[j++] = arr[begin2++];
         }

         while (begin1 <= end1)
            tmp[j++] = arr[begin1++];
         while (begin2 <= end2)
            tmp[j++] = arr[begin2++];

         //拷贝回原数组——归并哪部分就拷贝哪部分回去
         memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
      }
      gap *= 2;
}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
边界问题
实际上还需考虑是否越界的问题，上面那段代码并没有考虑，所以还需一些改进。为什么会存在越界的可能呢？因为我们是以gap的整数倍去取区间来归并的，而区间个数不一定总能满足两两配对。

举个例子，就把前面的那个数组后面加上个元素5，没有越界检测时出现的情况：

由上图可知越界分为三类（这里将[begin1, end1]、[begin2, end2]分别作为第一和第二组）

第一组越界（即end1越界）

应对方法：这种情况一般介于第一层和最后一层之间，break跳出for循环，不让越界值被访问。

第二组全部越界（即begin2和end2越界）

应对方法：这种情况一般在第一层，break跳出for循环，不让越界值被访问。

第二组部分越界（即end2越界）

应对方法：实际上这时候就到了最后一层了，把end2修正为sz - 1，不跳出for循环而继续归并。

其实第一种情况和第二种情况可以合并为一种情况，原因：

end1越界时begin2和end2由于比end1大，它们两个肯定也越界了，也就是说发生第一组越界时满足end1、begin2和end2都越界，即包括了第二组越界的条件，这两种情况都满足判断条件begin2 >= sz && end2 >= sz，同时第一和第二种情况的操作都一样——break跳出for循环，所以可以合并为只判断第二组是否全部越界。

拿两个数组试一下：

代码实现

void MergeSortNonR(int* arr, int sz)
{
assert(arr);

int* tmp = (int*)malloc(sz * sizeof(int));
if (tmp == NULL)
{
      perror("malloc fail");
      return;
}

int gap = 1;
while (gap < sz)
{
      for (int i = 0; i < sz; i += 2 * gap)
      {
         int begin1 = i, end1 = begin1 + gap - 1;
         int begin2 = end1 + 1, end2 = begin2 + gap - 1;
         int j = begin1;
//越界检测
         if (begin2 >= sz && end2 >= sz)
            break;
         if (end2 >= sz)
            end2 = sz - 1;
         //归并
         while (begin1 <= end1 && begin2 <= end2)
         {
            if (arr[begin1] < arr[begin2])
                  tmp[j++] = arr[begin1++];
            else
                  tmp[j++] = arr[begin2++];
         }

         while (begin1 <= end1)
            tmp[j++] = arr[begin1++];
         while (begin2 <= end2)
            tmp[j++] = arr[begin2++];

         //拷贝回原数组——归并哪部分就拷贝哪部分回去
         memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
      }
      gap *= 2;
}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
归并排序的特性总结：

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

————————————————
版权声明：本文为CSDN博主「桦秋静」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_61561736/article/details/126796657

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)