归并排序（分治）

概念介绍

归并排序（Merge Sort）是一种经典的排序算法，基于分治的思想，它将待排序数组分成两个子数组，分别排序，然后合并这两个已排序的子数组以得到最终的排序结果。下面详细解释一下归并排序的原理，并提供一个案例步骤：

原理解释：

• 分治策略：首先将待排序数组分成两个较小的子数组，然后递归地对这两个子数组进行排序。这个过程一直持续到子数组的长度为 1，此时认为它们已经排好序。

• 合并操作：将两个已排序的子数组合并成一个有序数组。这一步骤利用了两个已排序数组的有序性，通过比较两个数组的第一个元素，将较小的元素放入结果数组中，并向后移动相应指针。

• 递归：归并排序的关键在于递归地将数组分成较小的部分，并对这些部分进行排序，最后再合并起来。递归的基本情况是当数组长度为 1 时，即认为它是有序的。

案例步骤：

1，假设我们有一个待排序数组 [38, 27, 43, 3, 9, 82, 10]。

2，拆分：首先将数组分成两半，得到 [38, 27, 43, 3] 和 [9, 82, 10]。

3，递归排序：分别对这两个子数组进行递归排序。对于 [38, 27, 43, 3]，继续拆分为 [38, 27] 和 [43, 3]，然后再拆分为 [38]、[27]、[43] 和 [3]。递归结束后，得到 [3, 27, 38, 43]。对于 [9, 82, 10]，继续拆分为 [9]、[82] 和 [10]，递归结束后，得到 [9, 10, 82]。

4，合并：将两个有序的子数组 [3, 27, 38, 43] 和 [9, 10, 82] 合并成一个有序数组。比较两个数组的第一个元素，取较小的放入结果数组中，然后移动相应指针。依次进行下去，直到一个子数组为空，将另一个子数组中的剩余元素依次放入结果数组中。

5，合并结果：得到最终的有序数组 [3, 9, 10, 27, 38, 43, 82]。

这就是归并排序的详细原理和案例步骤。它的时间复杂度为 O(nlogn)，空间复杂度为 O(n)，具有稳定性。

稳定性：

稳定性是指当有两个相等的元素在排序后的序列中相对位置不发生变化。换句话说，如果排序算法能够保持相等元素的相对顺序不变，那么它就是稳定的。

例如，考虑一个包含相等元素的数组 [2b, 1, 2a]，其中元素 2a 和 2b 的值相等。如果一个排序算法是稳定的，那么在排序后的序列中，元素 2a 和 2b 的相对位置应该与排序之前保持一致。如果排序算法是不稳定的，则无法保证这一点，可能会导致相等元素的相对顺序发生变化。

稳定性在某些场景下非常重要，特别是当需要按照多个条件进行排序时。在这种情况下，如果排序算法是稳定的，就可以先按照第一个条件进行排序，然后再按照第二个条件进行排序，而不会破坏第一个条件的排序结果。

归并排序是一种稳定的排序算法，因为它在合并过程中，对于相等的元素会保持它们原来的相对顺序。

画图理解如下

上分，下治

代码实现

需要一个辅助数组来实现，先分在按照合并有序数组的方法合并
1

void _mergesort(int* arr, int left, int right,int* tem)
{
	if (right - left <= 0 || arr == NULL)
	{
		return;
	}
	int mid = (right + left) >> 1;

	_mergesort(arr, left, mid,tem);
	_mergesort(arr, mid + 1, right,tem);

	int sta1 = left, end1 = mid;

	int sta2 = mid + 1, end2 = right;

	int index = left;

	while (sta1 <= end1 && sta2 <= end2)
	{
		if (arr[sta1] < arr[sta2])
		{
			tem[index++] = arr[sta1];
			sta1++;
		}
		else
		{
			tem[index++] = arr[sta2];
			sta2++;
		}
	}

	while (sta1 <= end1)
	{
		tem[index++] = arr[sta1++];
	}
	while (sta2 <= end2)
	{
		tem[index++] = arr[sta2++];
	}

	for (int i = left; i <= right; i++)
	{
		arr[i] = tem[i];
	}
}

void mergesort(int* arr, int n)
{
	int* tem = (int*)malloc(sizeof(int) * n);
	_mergesort(arr, 0, n - 1, tem);
	free(tem);
}
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
52