前言
本文将继续介绍两种高效的排序算法——归并排序、计算排序。
归并排序在一些场合下（如外部排序）非常有效，当数据量非常大且无法全部加载到内存时，可以将其分块处理。
而计数排序是一种非比较排序算法，适用于特定范围内的整数排序，在许多数情况下计算排序可以秒杀我们介绍过的所有排序。
一、排序算法
1、归并排序
| 算法思路：
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列间段有序。
动图演示：
代码实现：
//子函数
void _MergeSort(int arr, int tmp, int begin, int end)
{
if (begin == end)
{
return;
}
int mid = (begin + end) / 2;
//[begin, mid] [mid + 1, end]
_MergeSort(arr, tmp, begin, mid);
_MergeSort(arr, tmp, mid + 1, end);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
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 + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并排序
void MergeSort(int arr, int n)
{
int tmp = (int)malloc(n sizeof(int));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(arr, tmp, 0, n - 1);
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
归并排序有几个需要特别注意的点：
分割区间一定要按[begin, mid] [mid + 1, end]分，不然会导致死循环
memcpy(arr + begin, tmp + begin, (end - begin + 1) sizeof(int));
一定是归并一组拷贝一组，因为如果存在越界的情况还整体拷贝肯定会出错
归并排序算法的时间复杂度是：O(NlogN)，空间复杂度是：O(N).
2、归并非递归
递归改非递归有两种办法，一种是用栈模拟，一种是用循环处理。
上篇文章中快排非递归我们是利用栈实现的，但是归并的非递归使用栈解决不了，因为快排的递归过程是一个类似前序遍历的过程，而归并是一个类似后续的过程，它是先将区间循环分割成只有一个数据，再反向进行归并，栈是做不到这一点的。
所以归并的非递归我们考虑用循环来实现。
我们可以直接将原数组一一归并，再二二归并，再四四归并……
//归并非递归
void MergeSortNonR(int arr, int n)
{
int tmp = (int)malloc(n sizeof(int));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//gap是每组归并数据的个数
int gap = 1;
while (gap < n)
{
//i表示每组归并的起始位置
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int j = i;
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, (end2 - i + 1) * sizeof(int));
}
gap *= 2;//一一归，二二归，四四归
}
free(tmp);
tmp = NULL;
}
