【排序算法】C语言实现归并排序，包括递归和迭代两个版本

文章目录

• 🚀前言
• 🚀归并排序介绍及其思想
• 🚀递归实现
• 🚀迭代实现

  🚀前言

  大家好啊！阿辉接着更新排序算法，今天要讲的是归并排序，这里阿辉将讲到归并排序的递归实现和迭代实现，话不多说，开始咱们今天的学习吧！！！！

  🚀归并排序介绍及其思想

  归并排序这是阿辉讲的第一个时间复杂度O(nlogn)的排序算法，额外空间复杂度是O(n)，归并排序可以做到稳定性。

  思想

  归并排序的思想就是分治，分治的思想是将一个大问题分解成若干个小问题，然后分别解决这些小问题，最后将这些小问题的解合并起来得到原问题的解

  由分治的思想很容易，想到用递归来实现归并排序，我们接着看👇

  🚀递归实现

  关于归并排序的递归方法主要由三个大的逻辑组成：

  • 分解：将待排序的数组分成两个子数组
  • 解决：对每个子数组进行排序
  • 合并：将排序好的子数组合并成一个有序的数组

    这里我们使用递归很轻松就能把主逻辑写好，大家都知道写递归必须要有限制条件否则会造成死递归，对于归并排序的限制条件很简单，对于数组只有一个元素时自然就是有序的，直接返回即可

    主逻辑：

    merge函数相当于黑盒，作用就是把两个有序数组合成一个大的有序数组

    void MergeSort(int a[], int l, int r) {// C/C++归并排序递归版本，主逻辑
    	if (r == l) {//递归限制条件
    		return;
    	}
    	int m = l + ((r - l) >> 1);//数组中位置下标
    	MergeSort(a, l, m);//左部分排序
    	MergeSort(a, m + 1, r);//右部分排序
    	merge(a, l, m, r);//两部分有序数组合并
    }
    

    整个归并排序最重要的部分也就是有序数组合并的部分：

    

    merge函数实现，还是不太懂的可以看一下下面的代码，有详细的注释

    C语言版本：

    void merge(int a[], int l, int m, int r) {
    	int* help = (int*)malloc((r - l + 1) * 4);//申请辅助空间
    	int i = 0;//作为help指针的偏移量，存储两有序数组排好序的大数组
    	int first = l;//作为左部分数组的起始下标
    	int second = m + 1;//作为右部分数组的起始下标
    	while (first //哪一方下标越界就说明不用继续比较了
    		//三目运算代码更简洁，谁小谁在前先赋值给help，后置++，
    		// 赋值后i向后偏移一个位置，second或first也向后偏移一个位置
    		help[i++] = a[first] 
    		help[i++] = a[first++];
    	}
    	while (second 
    		help[i++] = a[second++];
    	}
    	//最后把help管理的值，还原到原数组a中
    	for (i = 0; i