归并排序——C语言实现_c实现归并排序

归并排序是利用归并的思想实现的排序方法。它的原理是假设初始化序列中有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1。然后两两归并，得到(n/2 + n% 2)个长度为2或1的有序子序列；再两两归并，…，如此重复，直到得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。一般用的归并排序就是2路归并排序。
过程如下图所示：

归并排序可以由递归实现，也可以由迭代实现。

一、归并排序的递归实现
思路：
首先用递归实现将原长度的序列逐步拆分成左、右两个子序列，子序列的长度是原序列长度的一半，直到子序列的长度为1时递归停止；
在拆分结束，递归的回归过程中调用排序函数，将左、右子序列排成一个有序的新序列，用最终的新序列来替换原序列的值。

#include<iostream>
using namespace std;
#define MAXSIZE 10

void Sorting(int *list1, int list1_size, int *list2, int list2_size)//排序函数-排序过程
{
   
	int temp[MAXSIZE];//定义一个临时数组来存放排序后的新序列
	int i, j, k; // 分别为list1的下标，list2的下标和temp的下标
	i = j = k = 0;
	while (i < list1_size && j < list2_size)
	{
   
		if (list1[i] < list2[j])
		{
   
			temp[k] = list1[i];
			k++;
			i++;
		}
		else
		{
   
			temp[k] = list2[j];
			k++;
			j++;
		}
	}
	//没有比完的多余部分
	while (i < list1_size)
	
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