排序算法系列 - 合并排序


    合并排序是使用分治模式的一个实现实例。分治模式在每一层递归上都有三个步骤:

  •  分解(Divide) : 将原问题分解成一系列子问题
  • 解决(Conquer) : 递归地解决各子问题。若子问题足够小,则可以结束递归动作
  • 合并(Combine) : 将子问题的结果合并成原问题的解

合并排序(merge sort)算法完全按照了上述模式,直观地操作如下:

  • 分解: 将n个元素分成各含n/2个元素的子序列
  • 解决 : 用合并排序法对两个子序列递归地排序
  • 合并 : 合并两个已排序的子序列以得到排序结果

在对子序列排序时,长度为1时递归结束,单个元素被视为是已排好序的。

示例代码:

#include <iostream>
#include <cassert>
#include <climits>
#include <cstring>

using namespace std;


int merge(int *p, int lstart, int lend, int rend)
{
    //判断参数的合法性
    assert(lstart <= lend && lend < rend);

    //lstart是左边子数组的起始位置, lend 是左边子数组的结束位置,lend+1是右边数组的起始位置,end则是右边数组的结束位置
    int len_left = lend - lstart + 1;
    int len_right = rend - lend;

    int * pleft = new int[len_left + 1];  //每个数组后面新增一个哨兵
    int * pright = new int[len_right + 1];

    memset(pleft, 0 , sizeof(int) *(len_left + 1));
    memset(pright, 0 , sizeof(int) * (len_right + 1));

    //复制数组
    for(int i = 0; i < len_left; ++i)
    {
        //lstart并非下标表示,所以要-1
        pleft[i] = p[lstart - 1 + i];
    }

    for(int i = 0; i < len_right; ++i)
    {
        
        pright[i] = p[lend + i];
    }

    //添加哨兵值
    pleft[len_left] = INT_MAX;
    pright[len_right] = INT_MAX;

    //开始合并
    int i = 0, j= 0;
    //使用哨兵值,使我们不用考虑左右数组哪边先遍历完的问题

    for(int k = lstart - 1; k < rend; ++k)
    {
        if (pleft[i] <= pright[j])
        {
            //左边值小,因此放入p数组中
            p[k] = pleft[i];
            ++i;
        }
        else
        {
            p[k] = pright[j];
            ++j;
        }
    }

    //释放空间
    delete []pleft;
    delete []pright;

    return 0;
}

int merge_sort(int * p, int start, int end)
{
    //当起始大于等于终止时,终止二分
    if (start >= end)
    {
        return 0;
    }

    if (start < end)
    {
        int middle = (start + end)/2;

        //归并排序,应用分治算法的思想,分解-解决-合并
        merge_sort(p, start, middle);  //左边分
        merge_sort(p, middle+1, end);  //右边分
        merge(p, start, middle, end);  //合并结果       
    }
}

void print(int *p, int len)
{
    for(int i = 0; i < len; ++i)
    {
        cout<<p[i]<<"\t";
    }

    cout<<endl;
}

int main()
{
    cout<<"输入数组长度:"<<flush;

    int len;

    cin>>len;

    cout<<"请输入"<<len<<"个数组元素"<<endl;
    
    int *p = new int[len];
    memset(p, 0, sizeof(int) * len);

    for(int i = 0; i < len; ++i)
    {
        cin>>p[i];
    }

    cout<<"正在排序,请稍后....................."<<endl;

    merge_sort(p, 1, len);

    cout<<"排序后的结果如下:"<<endl;

    print(p, len);

    delete[]p;

    return 0;
}

评论

发表评论