归并排序

发表于2022-02-20更新于2025-09-28阅读次数

代码逻辑

1
2
3
4
void Merge(int* dest, int* src, int left, int mid, int right)
{
    
}

src表示源数据，dest表示目标空间。left表示源数据的最左位置，mid表示源数据的中间位置，right表示源数据的最右位置。其中，left到mid数据要满足有序，mid到right要满足同向有序。

此函数欲将src中的数据归并到dest中，使整体有序。

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
void Copy(int* src, int* dest, int left, int right)
{
    while(left <= right)
    {
        dest[left] = src[left];
        ++left;
    }
}
void Merge(int* src, int* tmp, int left, int mid, int right)
{
    int i = left, j = mid + 1;
    int k = left;
    while(i <= mid && j <= right)
    {
        tmp[k++] = src[i] <= src[j] ? src[i++] : src[j++];
    }
    while(i <= mid)
    {
        tmp[k++] = src[i++];
    }
    while(j <= right)
    {
        tmp[k++] = src[j++];
    }
}
void MergePass(int* src, int* tmp, int left, int right)
{
    if(left < right)
    {
        int mid = (right + left) / 2;
        MergePass(src, tmp, left, mid);	     //左部分
        MergePass(src, tmp, mid + 1, right); //右部分
        
        Merge(src, tmp, left, mid, right);	 //左右两部分比对合并，tmp临时存储
        Copy(tmp, src, left, right);         //将tmp内容导到src，便于下次两部分均有序
    }
}
void MergeSort(int* br, int n)
{
    if(br == NULL || n <= 1)return;
    int* tmp = new int[n];
    MergePass(br, tmp, 0, n - 1);
    delete[]tmp;
}

非递归形式

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
/*
假设对0 1 2 3 4 5 6 7 8排序
Merge(src, dest, 0, 0, 1)  --s=1
				 2	2  3
				 4  4  5
				 6  6  7
Merge(src, dest, 0, 1, 3)  --s=2
				 4, 5, 7
Merge(src, dest, 0, 3, 7)  --s=4

*/
void Merge(int * src, int * dest, int left, int mid, int right);
// s代表当前一轮归并的元素数（一半规模）
void MergePass(int* src, int* dest, int n, int s)
{
    int i = 0;
    // for的条件判断是看 剩下的元素数还够不够凑一个2 * s（s是要归并的半块）
    for(i = 0; i + 2 * s - 1 <= n - 1; i += 2 * s)
    {
        Merge(src, dest, i, i + s - 1, i + 2 * s - 1);
    }
    if(n - 1 > i + s - 1)//对于[0 1]-[2 3] [4 5]-[6 7] [8 9]-[10]而言(11-1>8+2-1)，即[8 9][10]还需要再合并：即此处处理的是剩下的两块，右部分的一块不整齐（10）
    {
        Merge(src, dest, i, i + s - 1, n - 1);
    }
    else//[0 1 2 3]-[4 5 6 7] [8 9 10]而言(不满足if的11-1>10+1-1)，也就是说，8 9 10落单了，没有下一组与它们合并，则原样复制
    {
        for(int j = i; j < n; ++j)
        {
            dest[j] = src[j];
        }
    }
}
void MergeSort(int * ar, int n)
{
    if(ar == NULL || n <= 1)return;
    int * tmp = new[n];
    // s代表当前一轮归并的元素数（一半规模）
    int s = 1;
    while(s < n)
    {
        MergePass(ar, tmp, n, s);
        s += s;
        MergePass(tmp, ar, n, s);
        s += s;
    }
    delete[]tmp;
}

适用思想的题