归并排序

发表于 更新于 分类于

  归并排序算法介绍...

归并排序

  • 归并算法，核心机制是分而治之，每次对数据进行拆分，然后合并，每次拆分直到每次排序的元素个数为1，的时候，单个元素必然是有序的，然后合并便可。

1、有序子列的归并 - 伪代码

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
// L 左边的起始位置 R 右边的起始位置 RightEnd 右边的终点位置
void Merge(ElementType A[],ElementType tempA[],int L,int R,int RightEnd)
{
    leftEnd = R - 1  // 左边部分有序元素的结束位置
    temp_index = L;  // 存放结果数组的初始位置
    NumElements = RightEnd - L + 1;   // 计算元素的总个数 - 左右两部份紧挨着 

    while(L <= LeftEnd && R <= RightEnd)
    {
        if(A[L] < A[R])
        {
            tempA[temp_index++] = A[L++];
        }
        else  // A[L] > A[R]
        {
            tempA[temp_index++] = A[R++];
        }
    }
    while(L <= LeftEnd)
    {
        tempA[temp_index++] = A[L++];
    }
    while(R <= RightEnd)
    {
        tempA[temp_index++] = A[R++];
    }
    // 将有序的元素写回到A中
    for(int i =0;i < NumElements;i++,RightEnd--)
    {
        A[RightEnd] = tempA[RightEnd];
    }
}

2、归并的实现 - 递归

  • 归并算法的实现有不同的方式，相比之下递归的实现方式相对直观，此处是递归实现的伪代码：
1
2
3
4
5
6
7
8
9
10
11
void Msort(ElementType A[],ElementType tempA[],int L,int RightEnd)
{
    int center;  // 每次将元素对半砍开 
    if(L < RightEnd)
    {
        center = (L + RightEnd) / 2;          // 中间位置的元素
        MSort(A,tempA,L,center);              //左半部分 
        MSort(A,tempA,center+1，RightEnd);    //右半部分 
    	Merge(A,tempA,L,center+1,RightEnd);   // 合并两部分 
    }
}

2、归并的实现 - 非递归

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
void Merge_Sort(ElementType A[],int N)
{
    int length = 1;   // 最开始 有序子列的长度
    ElementType * tempA;   // 一个辅助交换的和A等大小的空间
    tempA = new ElementType[N];
    if(tempA != nullptr)
    {
        while(length < N)  // 随着有序子列的扩大，最终一定大于等于N
        {
            Merge_pass(A,tempA,N,length);
            length *= 2;
            Merge_pass(tempA,A,N,length);
            length *= 2;
        }
        delete [] tempA;
    }
    else
    {
        std::cout<<"error"<<std::endl;
    }
}

// 源元素位置 目标元素位置 元素个数 有序子列的大小
void Merge_pass(ElementType A,ElementType tempA,int N,int length)
{
    for(i = 0;i <= N - 2*length;i += 2*length)   // 2*length 每次合并的元素的个数 
    {
        Merge_(A,tempA,i,i+length,i+2*length - 1);  // 合并
    }
    if(i+legnth < N)  // 剩下的元素个数 > length, 表示还可以进行一次合并： 一组的个数
    {
        // 此时最后被合并的数据 个数 < 2*length 
		Merge_(A,tempA,i,i+length,N - 1);  // 合并
    }
    else
    {
        // 合并最后部分的元素
        for(j = i; j < N;j++)
        {
            tempA[j] = A[j];
        }
    }
}

void Merge_(ElementType A[],ElementType tempA[],int L,int R,int RightEnd)
{
    leftEnd = R - 1  // 左边部分有序元素的结束位置
    temp_index = L;  // 存放结果数组的初始位置
    NumElements = RightEnd - L + 1;   // 计算元素的总个数 - 左右两部份紧挨着 

    while(L <= LeftEnd && R <= RightEnd)
    {
        if(A[L] < A[R])
        {
            tempA[temp_index++] = A[L++];
        }
        else  // A[L] > A[R]
        {
            tempA[temp_index++] = A[R++];
        }
    }
    while(L <= LeftEnd)
    {
        tempA[temp_index++] = A[L++];
    }
    while(R <= RightEnd)
    {
        tempA[temp_index++] = A[R++];
    }
}