• 常见七大排序（汇总）

    目录

    引言

    交换函数

    直接插入排序

    思想

    时间复杂度

    希尔排序

    思想

    时间复杂度

    选择排序

    思想

    时间复杂度

    堆排序

    思想

    时间复杂度

    冒泡排序

    思想

    时间复杂度

    快速排序（递归）

    霍尔法

    前后指针法

    三数取中 & 随机值法

    第一种是随机值法

    第二种是三数取中

    快速排序（非递归）

    归并排序（递归）

    思想

    时间复杂度

    归并排序（非递归）

    测试验证（100万个数测试看强度）

    总代码（gitee）

    结语

    引言

    本篇文章会对常见的七大排序进行讲解：

    • 直接插入排序   InsertSort
    • 希尔排序   ShellSort
    • 选择排序   SelectSort
    • 堆排序   HeapSort
    • 冒泡排序   BubbleSort
    • 快速排序   QuickSort
    • 归并排序   MergeSort

    其中，快排与归并排序除了讲解递归版本之外，还会讲解一下非递归的版本

    交换函数

    这是一个小的函数，只是后面会频繁用到，这里就简单做一下逻辑的分离

    Swap函数代码如下：

    1. void Swap(int* a, int* b)
    2. {
    3. 	int tmp = *a;
    4. 	*a = *b;
    5. 	*b = tmp;
    6. }

    直接插入排序

    思想

    直接插入排序就好像我们平时打扑克牌，每次拿到牌的时候都会洗牌

    我们每张牌都会用到，我们抽取出其中一张牌，然后将其插入到对应的位置上，当我们把每一张牌都如上操作插入一遍之时，我们就排序好了

    如下图：

    如上我们会看到：在换到 2 的时候最为特殊，他在交换了一次之后并没有停下，而是不断让前面的数跟他比较，在前面没有比他大的数字的时候，才插入下来

    而这个逻辑的实现也较为容易，我们只需要创建一个变量（end），这个变量代表着这是数组中的第几个数，再将该变量的下一个数给存起来，记作 int tmp = a [ end + 1 ]

    如果 end 变量的下一个（是跟tmp比较）比他小（假设排升序，左小右大），那么我们就让 end 变量代表的数将其覆盖，随后 end--。设置一个循环，当 end 减小到 <0 时，就代表 tmp 存的数是整个数组里面最小的一个

    这时我们再让 tmp 将 end + 1 位置的数给覆盖

    注：因为不是每一个数都是最小的，我们用 end 的数 将 end + 1 位置的数给覆盖了之后，原本 end 位置的数就空出来了，但是我们的 end 是先减减，然后才判断的，所以 tmp 覆盖的位置应该是 end + 1

    如果不理解的话，也可以参考下图：

    插入排序代码如下：

    1. //直接插入排序
    2. void InsertSort(int* a, int n)
    3. {
    4. 	for (int i = 0; i < n - 1; i++)
    5. 	{
    6. 		int end = i;
    7. 		int tmp = a[end + 1];
    8. 		while (end >= 0)
    9. 		{
    10. 			if (a[end] > tmp)
    11. 			{
    12. 				a[end + 1] = a[end];
    13. 				end--;
    14. 			}
    15. 			else
    16. 				break;
    17. 		}
    18. 		a[end + 1] = tmp;
    19. 	}
    20. }

    因为 end + 1 位置的数据会被覆盖，所以需要提前存一份

    我们 while 循环的条件是 end >= 0，如果 end + 1 位置的数大于 tmp 代表的数，就覆盖，并end--

    时间复杂度

    这个排序的时间复杂度也比较好算，每个数都要由第一个 for 循环遍历一遍

    遍历每一个数时还要将每个数再遍历一遍

    所以该数的时间复杂度为 O(N^2)

    希尔排序

    思想

    我们学完了插入排序之后，我们会发现每个数都是拿出来，找位置，交换，就像是打扑克牌刚拿到牌时洗牌一样，拿一张，挑合适的位置，插入，如此反复

    如上图，每一次交换都是两张两张之间进行的

    但是，大佬 希尔 发现了不对劲

    如果需要排序的数组接近有序的话，那么直接插入排序的效率将会非常高

    所以大佬就想着，能不能在直接插入排序的基础上进行改进，在两张两张之间排序之前，先将其变成接近有序的

    这就是——预排序

    不一定非要两个两个，让其跨度大一点呢？

    多来几组呢？

    让这些个组先粗略地排一遍，那么不就接近有序了！

    但是只是跨一个，或是两个，抑或是三个之间交换，这样子排似乎不够

    最后希尔大佬发现，先让间隔 gap 等于 排序数组总数的一半，在进行完一次预排序之后，再让 gap 除等 2，一直循环，直到 gap<1 ，这时候的效率是最高的，时间复杂度接近 O(N*logN) 

    这是非常快的！

    拿N^2 与 N*logN对比一下

    假设有100万个数据

    2^20 为1’048‘576，接近100万，且当作100万来算

    N^2  要排序  100万 * 100万次

    N*logN 大概要排序   100万*20次

    快了不是一点半点！！！

    但是后来，有人发现，我们不需要分那么多组，太麻烦了

    我们可以只用一组，让这一组拍完之后不断向后移动即可，如下：

    我们先将其中一次的逻辑实现一遍：

    先假设 gap = 3

    那么我们就是将每个间隔对应位置的数给排好

    假如我们现在要排的是如下图所示的 3

    那么我们就需要先将 3 和 1 进行对比

    如果 3 大于 1，那么我们就用 3 将 1 给覆盖，由于要被覆盖，所以我们需要先将 1 位置的数据先存起来，记作 tmp

    由于数据是从前往后排的，我们只是截取了 3 这个点作为例子，因此，3 前面的数据肯定是已经排序好了的

    接着，我们让 1 和 2 进行比较，2 > 1，所以 2 将原本 3 的位置给覆盖

    最后当 1 无法向后再走的时候，1 再将原本 2 的位置给覆盖掉

    这其实和我们上文提到的 直接插入排序 的思路是一摸一样的，如果有疑惑的，可以将上文插入排序的逻辑理一理

    单次预排序代码如下：

    1. int gap = 3;
    2.  
    3. int end = i;//假设i位置就代表我们说的3的位置
    4. int tmp = a[end + gap];
    5. while (end >= 0)
    6. {
    7. 	if (a[end] > tmp)
    8. 	{
    9. 		a[end + gap] = a[end];
    10. 		end -= gap;
    11. 	}
    12. 	else
    13. 		break;
    14. }
    15. a[end + gap] = tmp;

    在加上希尔大佬的想法：先设gap为总数的一半，再不断将其除等 2

    当 gap 为 1 的时候，其实就是 直接插入排序

    综上，总代码如下：

    1. //希尔排序
    2. void ShellSort(int* a, int n)
    3. {
    4. 	int gap = n;
    5. 	while (gap > 1)
    6. 	{
    7. 		gap = gap / 3 + 1;
    8. 		for (int i = 0; i < n - gap; i++)
    9. 		{
    10. 			int end = i;
    11. 			int tmp = a[end + gap];
    12. 			while (end >= 0)
    13. 			{
    14. 				if (a[end] > tmp)
    15. 				{
    16. 					a[end + gap] = a[end];
    17. 					end -= gap;
    18. 				}
    19. 				else
    20. 					break;
    21. 			}
    22. 			a[end + gap] = tmp;
    23. 		}
    24. 	}
    25. }

    时间复杂度

    具体时间复杂度的算法涉及到数学中的概率等等知识点，讲明白的时候已经是数学问题了，所以各位可以直接记结论

    接近 O(N*logN)

    选择排序

    思想

    其实选择排序很好理解,其主要思想就是：

    定义出变量begin和end，begin初始化为0，end为n-1（共有n个元素）

    不断地遍历数组，每遍历一次，就找出最小值和最大值，再将这两个分别放到begin和end位置上

    最后begin++，end--

    每一次都找到begin与end范围内的最大与最小

    代码（有坑的，待会儿填）如下：

    1. int begin = 0, end = n - 1;
    2. while (begin < end)
    3. {
    4. 	int mini = begin, maxi = begin;
    5. 	for (int i = begin + 1; i <= end; i++)
    6. 	{
    7. 		if (a[i] < a[mini])mini = i;
    8. 		if (a[i] > a[maxi])maxi = i;
    9. 	}
    10. 	Swap(&a[begin], &a[mini]);
    11. 	Swap(&a[end], &a[maxi]);
    12. 	begin++, end--;
    13. }

    如果这时候你去运行代码，你会发现结果是错误的，而且出错的是最中间的两个元素

    我们用图解的方式来了解一下为什么：

    我们会发现，到了最后一步的时候，begin先和min换一次，但是end和max又换回来了

    也就是说，本来是换好了的，但是换了两遍又换回来了

    所以我们可以加个判断：当begin等于max的时候，我们就将max的值赋值为min

    最后的结果就是end自己和自己换了一次，结果就正确了

    完整代码如下：

    1. //选择排序
    2. void SelectSort(int* a, int n)
    3. {
    4. 	int begin = 0, end = n - 1;
    5. 	while (begin < end)
    6. 	{
    7. 		int mini = begin, maxi = begin;
    8. 		for (int i = begin + 1; i <= end; i++)
    9. 		{
    10. 			if (a[i] < a[mini])mini = i;
    11. 			if (a[i] > a[maxi])maxi = i;
    12. 		}
    13. 		Swap(&a[begin], &a[mini]);
    14. 		if (begin == maxi)maxi = mini;
    15. 		Swap(&a[end], &a[maxi]);
    16. 		begin++, end--;
    17. 	}
    18. }

    时间复杂度

    不难看出，每个数都遍历一遍的同时，都会再找一遍最大值和最小值

    所以时间复杂度是  O(N^2)

    堆排序

    思想

    堆排序的核心思想就是建堆，升序建大堆，降序建小堆

    我们先来说一下堆已经建好了的情况下，我们该怎么排序：（这里假设我们排的是升序）

    这是一个已经建好了的大堆

    我们先将最末尾的数字与最顶上的数字进行交换，由于顶上的数字是最大的，所以交换完之后，就代表这个数字已经被排好了

    你可以理解成是从后面开始往前排

    交换完了之后，我们让控制总数的那个变量减减一下，那么总数就少了一个，代表最后一个已经排序好的数字就不会再受到干扰了

    最后对这个大堆进行向下调整，再一次选出最大的那个数字放在堆顶，交换，减减，向下调整，如此往复

    图解如下：

    建堆和排序代码如下：

    1. void HeapSort(int* a, int n)
    2. {
    3. 	//建大&小堆
    4. 	for (int i = (n - 2) / 2; i >= 0; i--)
    5. 		AdjustDown(a, n, i);
    6.  
    7. 	//首尾交换 + 排序
    8. 	int end = n - 1;
    9. 	while (end)
    10. 	{
    11. 		Swap(&a[0], &a[end]);
    12. 		AdjustDown(a, end--, 0);//向下调整
    13. 	}
    14. }

    接着我们再来讲一讲向下调整法：

    向下调整法本质上，设当前节点为父节点，先在两个子节点里面找到大的那一个（假设此处是建大堆）

    对比父节点与大的那个子节点，父节点大就终止循环，子节点大就交换两节点，以子节点为新的父节点，往下n*2+1个位置的节点作为新的字节点

    当子节点 > 数组总个数 时，退出循环

    补充一个点，我们可以使用假设法找到两个子节点中大的那个节点

    先假设其中一个是大的那个

    再 if 判断一下：如果该节点没有另一个大，就换成另一个为子节点，相反则不做处理

    向下调整代码如下：

    1. //堆排序(升序建大堆√，降序建小堆)
    2. void AdjustDown(int* a, int n, int parent)
    3. {
    4. 	int child = parent * 2 + 1;
    5.  
    6. 	while (child < n)
    7. 	{
    8. 		//假设法找大孩子
    9. 		if (child + 1 && a[child] < a[child + 1])child++;
    10.  
    11. 		if (a[child] > a[parent])
    12. 		{
    13. 			Swap(&a[child], &a[parent]);
    14. 			parent = child;
    15. 			child = child * 2 + 1;
    16. 		}
    17. 		else
    18. 			break;
    19. 	}
    20. }

    时间复杂度

    由于堆排序是二叉树结构，树的高度是logN

    我们可以推理一下公式：

    树的总数：N = 2^0 + 2^1 +......+ 2^(n-1)

    树的总高度为 n-1

    N = 2^0 + 2^1 +......+ 2^(n-1)

    2N = 2^1 + 2^2 +......+ 2^n

    上述两式相减：N = 2^n - 2^0 = 2^n - 1

    所以树的高度大致为 logN

    所以就是遍历了 N*logN 次

    时间复杂度就是   O(N*logN)

    冒泡排序

    思想

    冒泡排序本质上就是一个 for 循环嵌套

    外层的for循环代表的是一共要进行多少趟冒泡

    嵌套在里面的那一层代表的是每一趟冒泡的具体过程

    每一趟冒泡就是（假设要升序）：如果后一个比前一个小，那么就交换

    第一趟冒泡结束之后，最大的那个数字就被排好了；第二趟冒泡之后，第二大的就被排好了，如此往复

    代码如下：

    1. //冒泡排序
    2. void BubbleSort(int* a, int n)
    3. {
    4. 	for (int i = 0; i < n - 1; i++)
    5. 	{
    6. 		for (int j = 0; j < n - 1 - i; j++)
    7. 		{
    8. 			if (a[j] > a[j + 1])
    9. 				Swap(&a[j], &a[j + 1]);
    10. 		}
    11. 	}
    12. }

    时间复杂度

    O(N^2)

    快速排序（递归）

    霍尔法

    霍尔法的本质思想就是：先将最左边的数定义为key

    然后两个变量begin和end，分别从左边与右边出发

    为了保证最后停下位置的数一定比key要小，所以需要end先从右边走

    如果遇到比 key 小的数，那么 end 就停下来

    接着 begin 走，如果遇到的数比 key 要大，也停下来

    最后交换 begin 和 end 

    接着，一个从右边出发，一个从左边出发，不断反复，直到 begin >= end，终止循环

    当循环终止的时候，就代表着 begin 和 end 指向一个地方

    这样子做完之后，最后的结果就是key位置的数排好了，key左边的数都比key代表的数要小，右边的都比key代表的数要大

    图解如下：

    当我们将上图中的5给排好了之后，我们可以使用递归的方法，左边和右边都使用上述同样的方法，我们需要传的是一个范围

    原函数开始是传 0 和 7（一共8个数）

    排序完了之后，我们就分别传 0     key-1，key+1     7

    每一个排序完了之后，我们都按这种方法不断递归下去

    图解如下：

    既然是递归，那么就肯定需要返回条件，如若不然则会无限递归下去

    由上图可得，返回条件有两种情况：

    此时 2 是key

    1. key 的左边还有数，所以传过去的范围就是一样的，即 begin == key-1
    2. key 的右边没有数，所以传过去的范围是 key-1 > end

    综上，我们可以知道返回条件是：if（left >= right）    return;

    综上，代码如下：

    1. //快排
    2. void QuickSort(int* a, int left,int right)
    3. {
    4. 	if (left >= right)
    5. 		return;
    6.  
    7. 	int begin = left, end = right;
    8. 	int key = left;
    9.  
    10. 	while (left < right)
    11. 	{
    12. 		//right先走
    13. 		while (right > left && a[right] >= a[key])right--;
    14.         //left走
    15. 		while (right > left && a[left] <= a[key])left++;
    16.  
    17. 		Swap(&a[left], &a[right]);
    18. 	}
    19. 	Swap(&a[left], &a[key]);
    20. 	key = left;
    21.  
    22. 	QuickSort(a, begin, key - 1);
    23. 	QuickSort(a, key + 1, end);
    24. }

    前后指针法

    实际上，这种方法比霍尔法更为方便，只不过毕竟是霍尔大佬整出的快排，学快排肯定要学一下霍尔法

    而前后指针的逻辑也很简单

    我们有一前一后两个指针，我们最后的目的是让两个指针之间的数为大于 key 的数（升序），而前指针左边的数都是小于 key 的数

    最后将 key 与前指针交换，就达到了和霍尔法一样的效果

    其主要思想如下：

    前面的指针为 prev，后面的指针为 cur，记最左边的那个数为 key

    如果 cur 指向的值 < key 指向的值（升序），那么我们就将 prev++，接着交换 prev 和 cur，最后 cur++，如果 cur 指向的值 > key 指向的值，那么直接 ++cur 即可

    因为我们需要达到的结果是：prev 和 cur 之间包含的是 > key 的值，而由于最后的步骤是将 prev 和 key 进行一个交换，之后再进行递归，所以 prev 的值是应该小于 key 代表的值的

    这时我们需要分几种情况的分析：

    1. prev 的下一个就是 cur（cur 代表的值 < key 代表的值）：由于 prev 是需要小于 key 的，所以如果 prev 的下一个就是 cur 的话，那么就意味着 prev 和 cur 之间可以不包括这个数据，按照如上的做法，我们先++prev，然后交换 prev 和 cur（自己和自己换），再++cur，结果是对的
    2. prev 与 cur 之间有值（cur 代表的值 > key 代表的值）：由于 prev 和 cur 之间包含的值是大于 key 的，所以直接 cur++ 即可
    3. prev 与 cur 之间有值（cur 代表的值 < key 代表的值）：我们先++prev，由于 prev 和 cur 之间的值都是大于 key 的值，所以++prev 之后的就是大于 key 的值，由于现在 cur 指向的值 < key，所以我们就将 prev 和 cur 交换一下，这样就达成了我们的目的

      图解如下：

    上述逻辑的代码如下（未改进前的版本）：

    1. int key = left;
    2. int prev = left;
    3. int cur = right;
    4.  
    5. while(cur <= right)
    6. {
    7.     if(a[cur] < a[key])
    8.     {
    9.         ++prev;
    10.         Swap(&a[prev], &a[cur]);
    11.         ++cur;
    12.     }
    13.     else
    14.     {
    15.         ++cur;
    16.     }
    17.     ++cur;
    18. }
    19. a[key] = a[prev];
    20. key = prev;

    但是有人觉得这样子写太啰嗦了，反正 cur 都是要++的，干脆合在一起算了

    所以就有了下面的代码：

    1. int prev = left, cur = prev + 1;
    2.  
    3. int key = left;
    4. while (cur <= right)
    5. {
    6. 	if (a[cur] < a[key] && ++prev != cur)
    7. 		Swap(&a[prev], &a[cur]);
    8. 	++cur;
    9. }
    10. Swap(&a[prev], &a[key]);
    11. key = prev;

    再加上递归和返回条件

    总代码如下：

    1. void QuickSort(int* a, int left, int right)
    2. {
    3. 	if (left < right)
    4. 		return;
    5. 	int prev = left, cur = prev + 1;
    6.  
    7. 	int key = left;
    8. 	while (cur <= right)
    9. 	{
    10. 		if (a[cur] < a[key] && ++prev != cur)
    11. 			Swap(&a[prev], &a[cur]);
    12. 		++cur;
    13. 	}
    14. 	Swap(&a[prev], &a[key]);
    15. 	key = prev;
    16.  
    17. 	QuickSort(a, left, key - 1);
    18. 	QuickSort(a, key + 1, right);
    19. }

    三数取中 & 随机值法

    快排好是好，但是他也分情况

    由于快排每一次都是排序好一个位置的数，然后再将左边和右边分为两个区间，再不断递归下去的

    快排最好的情况就是：

    每次都是在最中间的位置分出左右区间，随后递归，这时时间复杂度为O(N*logN)

    快排最坏的情况就是：

    每次都是在最边边的位置选区间，也就是接近有序的情况，这时时间复杂度接近  O(N^2)

    所以如果面临的要排序的数组接近有序的话，我们该如何处理这种情况呢？

    第一种是随机值法

    随机值法就是：从数组中随机选一个数，将这个数与 key 位置的数字进行交换，以这个数作为新的 key

    代码如下：

    1. int randi = rand() % (right - left);
    2. randi += left;
    3. Swap(&a[left], &a[randi]);

    由于我们写的是递归，我们选的数字可能并不是从 0 位置开始的，所以 randi 要 += left 保证 randi 在的位置是待排序那一段数组的起始位置

    第二种是三数取中

    有人觉得按随机值法不太可靠，不太稳定，不是很喜欢，所以就发明了这种三数取中的方法

    三数取中法的本质就是：

    将待排序数组的头、尾、中间位置的数进行比较，将排在中间位置的值返回

    如果待排序数组接近有序的话，我们用一手三数取中，不就可以尽可能地保证，快排在中间位置分左右区间再递归吗？这多有效率啊

    具体逻辑就是比较，这里不做过多解释

    三数取中代码如下：

    1. int GetMid(int* a, int left, int right)
    2. {
    3. 	int mid = (right + left) / 2;
    4.  
    5. 	if (a[left] < a[mid])
    6. 	{
    7. 		if (a[mid] < a[right])
    8. 			return mid;
    9. 		else if (a[left] < a[right])
    10. 			return right;
    11. 		else
    12. 			return left;
    13. 	}
    14. 	else
    15. 	{
    16. 		if (a[mid] > a[right])
    17. 			return mid;
    18. 		else if (a[left] < a[right])
    19. 			return left;
    20. 		else
    21. 			return right;
    22. 	}
    23. }

    快速排序（非递归）

    快速排序的非递归版本，主体上和递归版本没有什么区别，逻辑还是那个逻辑，还是前后指针法、霍尔法完成选数字分区域

    唯一不同的就在于：

    以前我们对分完区域后的数组段是递归处理

    现在我们是用   栈  +  循环  的方式来模拟实现递归的

    我们将区域压入栈内，比如先压 0  9  ，后面可能会压  0   5，7   9  ，不断重复下去

    我们每排完一次序，我们就从 栈 里面取数据，再用取出的这两个数据进行压栈

    你会发现，我们每从栈里面取一次数据，就相当于进行了一次递归的过程

    而当栈里面没有数据了的时候，也就代表我们已经排序好了

    由于C语言不像C++有 stl库可以直接使用，所以我们只能现场手撕一个

    为了不耽误大家时间，我在这里就简单介绍一下我会使用到的关于栈的函数名：

    • STInit  栈的初始化
    • STPush  压栈
    • STPop  出栈
    • STEmpty  判断栈是否为空
    • STDestroy  销毁

    由于主题逻辑和递归是一摸一样的，这里就直接放代码了

    代码如下：

    1. void QuickSortNonR(int* a, int left, int right)
    2. {
    3. 	ST st;
    4. 	STInit(&st);
    5. 	STPush(&st, right);
    6. 	STPush(&st, left);
    7.  
    8. 	while (!STEmpty(&st))
    9. 	{
    10. 		int begin = STTop(&st);
    11. 		STPop(&st);
    12.  
    13. 		int end = STTop(&st);
    14. 		STPop(&st);
    15.  
    16.         //单趟排序
    17. 		int key = begin;
    18. 		int prev = begin;
    19. 		int cur = begin + 1;
    20.  
    21. 		while (cur <= end)
    22. 		{
    23. 			if (a[cur] < a[key] && ++prev != cur)
    24. 				Swap(&a[prev], &a[cur]);
    25.  
    26. 			++cur;
    27. 		}
    28.  
    29. 		Swap(&a[key], &a[prev]);
    30. 		key = prev;
    31.  
    32. 		if (key + 1 < end)
    33. 		{
    34. 			STPush(&st, end);
    35. 			STPush(&st, key + 1);
    36. 		}
    37.  
    38. 		if (begin < key-1)
    39. 		{
    40. 			STPush(&st, key-1);
    41. 			STPush(&st, begin);
    42. 		}
    43. 	}
    44. 	STDestroy(&st);
    45. }

    归并排序（递归）

    思想

    我们先通过一张图片来看一看，归并排序是一个什么东西：

    你可以理解成，先将待排序数组以二叉树的形式分好，再从底层开始一个一个排

    当然你也可以说，这是  后序

    同时我们还需要另外 malloc 一块空间，因为我们是通过选数的方式，将小的数（升序）先放到数组里面，然后再 memcpy 回原数组，中间需要一个不被销毁的中转站

    我们将 malloc 出来的这块空间且指向这块空间的指针称为 tmp

    我们将这一段待排序数组分成以 mid 为中心的两个区域，begin->mid     mid+1->end

    随后我们将这两段进行排序，设左边的那段为左数组，右边那段为右数组

    我们这样判断：左数组的第一个和右数组的第一个比，谁小就先将其放在 tmp 数组里面

    再不断地比较下去，直到有一边没有数字了，循环终止

    接着我们还需要各自判断一遍：左数组还有没有数，如果有，就证明左数组里剩下的数比右数组的都要大，就将其依次放入 tmp 中

    右数组同理

    图解如下：

    如果 begin 和 end 相等的话，就代表现在递归到只剩一个数了，这时就返回

    所以我们的递归判断条件是：if（end == begin）return;

    代码如下：

    1. void _MergeSort(int* a, int begin, int end, int* tmp)
    2. {
    3. 	if (begin == end)
    4. 		return;
    5.  
    6. 	int mid = (begin + end) / 2;
    7. 	int begin1 = begin, end1 = mid;
    8. 	int begin2 = mid + 1, end2 = end;
    9.  
    10. 	_MergeSort(a, begin, mid, tmp);
    11. 	_MergeSort(a, mid + 1, end, tmp);
    12.  
    13. 	int i = begin;
    14.  
    15. 	while (begin1 <= end1 && begin2 <= end2)
    16. 	{
    17. 		if (a[begin1] <= a[begin2])
    18. 			tmp[i++] = a[begin1++];
    19. 		else
    20. 			tmp[i++] = a[begin2++];
    21. 	}
    22. 	while(begin1 <= end1)
    23. 		tmp[i++] = a[begin1++];
    24. 	while (begin2 <= end2)
    25. 		tmp[i++] = a[begin2++];
    26.  
    27. 	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
    28. }
    29.  
    30. void MergeSort(int* a, int n)
    31. {
    32. 	int* tmp = (int*)malloc(sizeof(int) * n);
    33. 	if (tmp == NULL)
    34. 	{
    35. 		perror("malloc fail");
    36. 		return;
    37. 	}
    38. 	_MergeSort(a, 0, n - 1, tmp);
    39.  
    40. 	free(tmp);
    41. 	tmp = NULL;
    42. }

    时间复杂度

    由于这是一个树结构，树的高度为 logN，待排序数组有 N 个数

    所以时间复杂度为   O(N*logN)

    归并排序（非递归）

    由于递归给 ban 掉了，所以我们现在首要的问题就是：如何先两两排，再四四排等等，就像递归一样

    我们核心逻辑不变，还是两个数组段之间进行比较，还是需要 malloc 出一块 tmp 数组作为中转站

    这时我们可以引入一个 gap

    gap 代表的是当前是多少个数之间进行比较，图解如下：

    但是由于并不是每一个数组都是偶数，而且即使是偶数个，之后也会出现越界的情况，所以我们需要分开讨论

    我们对区域的划分创建了四个变量：

    • begin1
    • end1
    • begin2
    • end2

    其中，除了 begin1 不会出现越界情况之外，其他的每一个变量都会出现越界的情况

    如果是 end1 或 begin2 越界了的话，我们就不用再排序下去了

    • end1：假设有数组段 0  3，4  8，9  10。这时我们就可以让 0  3，4  8 这两个数组之间排，排完了之后再让 0  8，9  10 两个数组之间排，所以 end1 越界无需接着排序下去
    • begin2：假设有数组段 0  3，4  8，9  13，begin2 越界就代表着在场的数组段为奇数段，有一段没有对应的数组两两比较，所以 begin2 越界也无需接着排序下去
    • end2：如果是 end2 越界，而其他变量没有越界的话，那么就意味着场上的数组为奇数个，只是最后两个数组可能一个有 6 个数，另一个有 4 个数，不一样而已，所以 end2 越界我们还是要接着排序下去的，只是我们需要改一下 end2 的值，如果共有 n 个数的话，我们就需要将 end2 赋值为 n-1（因为 end2 代表的是一个位置，end2 越界时，数组最后一个数的位置就是最后一个数组的边界）

    综上：我们要将这几个变量控制好，排序才不会出错，控制代码如下：

    1. if (begin2 >= n || end1 >= n)
    2. 	break;
    3. if (end2 >= n)
    4. 	end2 = n - 1;

    而我们第一次排序时，每组都为 gap=1 个数，而后不断将其乘等2

    而循环结束的条件就是：当 gap < n 时，退出循环

    整体代码如下：

    1. void MergeSortNonR(int* a, int n)
    2. {
    3. 	int* tmp = (int*)malloc(sizeof(int) * n);
    4. 	if (tmp == NULL)
    5. 	{
    6. 		perror("malloc fail");
    7. 		return;
    8. 	}
    9.  
    10. 	int gap = 1;
    11.  
    12. 	while (gap < n)
    13. 	{
    14. 		for (int j = 0; j < n; j += 2 * gap)
    15. 		{
    16. 			int begin1 = j, end1 = begin1 + gap - 1;
    17. 			int begin2 = begin1 + gap, end2 = begin2 + gap - 1;
    18.  
    19. 			if (begin2 >= n || end1 >= n)
    20. 				break;
    21. 			if (end2 >= n)
    22. 				end2 = n - 1;
    23.  
    24. 			int i = j;
    25.  
    26. 			while (begin1 <= end1 && begin2 <= end2)
    27. 			{
    28. 				if (a[begin1] <= a[begin2])
    29. 					tmp[i++] = a[begin1++];
    30. 				else
    31. 					tmp[i++] = a[begin2++];
    32. 			}
    33. 			while (begin1 <= end1)
    34. 				tmp[i++] = a[begin1++];
    35. 			while (begin2 <= end2)
    36. 				tmp[i++] = a[begin2++];
    37.  
    38. 			memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));
    39. 		}
    40. 		gap *= 2;
    41. 	}
    42.  
    43. 	free(tmp);
    44. 	tmp = NULL;
    45. }

    测试验证（100万个数测试看强度）

    总代码（gitee）

    今天用到的全部代码都在下方链接中（除了快排的非递归）

    Sort-All-blog

    结语

    隔了很长一段时间没有写博客（中间的时间都拿去学线代了doge）

    如果觉得这篇博客能给你带来帮助的话，希望各位能多多支持呀！！！

  • 相关阅读:
    node笔记记录78模板引擎4
    开关电源测试方案介绍：如何进行电源耐压测试？
    leetcode 1884-鸡蛋掉落-两枚鸡蛋
    前端从零到一开发vscode插件并发布到插件市场
    普冉PY32系列(七) SOP8,SOP10,SOP16封装的PY32F002A/PY32F003管脚复用
    【leetcode】 盛最多水的容器
    springboot+jsp高校学生宿舍管理系统-宿管带前端
    Linux实训——单机版聊天室
    javacpp 映射
    【(C语言)数据结构奋斗100天】顺序表和链表
  • 原文地址：https://blog.csdn.net/2302_80023639/article/details/138127042