【算法】排序算法——归并排序-蒲公英云

#

【fishing-pan：https://blog.csdn.net/u013921430转载请注明出处】

前言

归并排序是分治法在排序问题上的运用，因此为了更好地了解归并排序，首先了解一下分治法。分治法的基本思想是：将原问题分解为几个规模较小但是类似于原问题的子问题，递归地求解这些子问题，然后合并子问题的解来建立原问题的解。

分治模式在每层递归时有三个步骤：

分解原问题为若干子问题，这些子问题是原问题的规模较小的实例；

解决子问题，递归地求解子问题；若子问题足够小，直接求解；

合并子问题的解，获得原问题的解。

归并排序算法遵循分治模式，操作如下：

分解：分解待排序的具有n个元素的序列，成为具有n/2个元素的两个子序列；

解决：使用归并排序递归地排序子序列；

合并：合并已排序的两个子序列产生已排序的答案。

归并排序

在归并排序中，首先将初始序列不断分解，当分解至子序列长度为1时，便开始递归排序。如下图所示，图中初始序列本分解为8个长度为1的子序列，而后开始归并排序；

20180509124319952 图 1

在进行排序时，需要一个函数merge（）进行操作，在这个函数中有三个下标，分别指向两个子序列中的元素以及归并产生的有序序列中的位置；以上图第二层中的9、11与5、8序列为例，merge（）函数执行的操作可以用下图表示。

20180509130445567 图 2

在上图中，第一次进行对比后将5放入归并序列中，然后将j与k各往后移动一位。在第二次对比完后，j已经移动到序列尾部，此时只剩下第一个序列中的元素，因为元素已经是有序的，所以直接放入归并序列即可。可以从这一步看出，merge（）的时间复杂度为Θ（n）。

编写代码

首先设计一个函数merge_sort（）对序列进行二分，当二分至子序列中只含有一个元素时，因为单个元素自身就是“有序”的，无需进行比较；然后将两个具有单个元素的子序列进行归并，这时候就需要调用merge（）函数进行归并排序，返回有序的序列。如此往复，直至所有的元素都被排序。思路理清楚了，可以开始写代码；

bool merge_sort(vector<int> &a,int begin,int end)
{
    //--若只传递了一个参数，无需进行排序，直接返回  
    if (begin >= end)
    {
        return true;
    }
    int mid = (end + begin) / 2;
    merge_sort(a, begin, mid);
    merge_sort(a, mid + 1, end);
    //--经过上面的归并后两个子序列内部已经是有序的，若两个子序列中第二个子序列的第一个元素已经大于第一个子序列的最后一个元素，则不需要排序；
    if (a[mid] <= a[mid + 1])
    {
        return true;
    }
    merge(a, begin, mid, mid + 1, end);
    return true;
}

merge（）函数的功能在上面已经介绍过了，输入参数是主序列以及四个序号，四个序列号分别表示两个子序列的区间。首先创建两个临时序列用于存放子序列，然后开始比较临时序列中的元素，将元素依次存放入主序列当中，实现代码如下；

void merge(vector<int> &a, int l_begin, int l_end,int r_begin,int r_end)
{
    //if (l_begin == l_end&&r_begin == r_end)     //--如果只有一个元素，则只需比较一次比较了；
    //{
    //    if (a[l_begin]>a[r_begin])
    //    {
    //        int s = a[r_begin];
    //        a[r_begin] = a[l_begin];
    //        a[l_begin] = s;        
    //    }
    //    return ;
    //}
    //
    int leng1 = l_end - l_begin + 1;
    int leng2 = r_end - r_begin + 1;
    //--创建两个临时的vector进行存放序列；
    vector<int> temp_L;
    vector<int> temp_R;
    for (int i = 0; i < leng1; i++)
    {
        temp_L.push_back(a[l_begin+i]);
    }
    for (int i = 0; i < leng2; i++)
    {
        temp_R.push_back(a[r_begin + i]);
    }
    int i = 0;
    int j = 0;
    while (i < leng1 && j < leng2)
    {
        if (temp_L[i] <= temp_R[j])
        {
            a[l_begin + i + j] = temp_L[i];
            i++;
        }
        else
        {
            a[l_begin + i + j] = temp_R[j];
            j++;
        }
    }
    //--当某个其中一个序列的元素已经全部被放置进入归并后的序列，此时直接将第另一个剩下部分序列放入归并序列即可；
    while (i <leng1)
    {
        a[l_begin + i + j] = temp_L[i];
        i++;
    }
    while (j <leng2)
    {
        a[l_begin + i + j] = temp_R[j];
        j++;
    }
    return ;
}

运行结果

原始序列

排序结果

70 1

算法分析

时间复杂度

观察图1可以知道在每一层中每个元素都需要merge（）函数进行归并排序，每一层的时间复杂度为Θ（n），而在分解序列时，只需要找到序列的中点，这一步的时间复杂度为Θ（1），为低阶项；进行二分归并时，总共会有 70 2 层，所以时间复杂度为 70 3 = 70 4 ，忽略低阶项后，算法的时间复杂度为 70 5 。（注：分析时间复杂度时常用 70 6 表示 70 7 ， 70 6 但是在数学中代表 70 8 ）。

空间复杂度

从代码中不难看出，在进行归并时需要一个临时的空间存放序列，所以不是原地排序，排序的空间复杂度为 70 9 。

排序稳定性

归并排序是稳定排序。

完整代码

为了方便大家测试，在这里提供所有代码；

//------------------------------------
//----潘正宇，归并排序
//----2018.01.25
//------------------------------------
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
void merge(vector<int> &a, int l_begin, int l_end, int r_begin, int r_end);
bool merge_sort(vector<int> &a,int begin,int end)
{
    //--若只传递了一个参数，无需进行排序，直接返回  
    if (begin >= end)
    {
        return true;
    }
    int mid = (end + begin) / 2;
    merge_sort(a, begin, mid);
    merge_sort(a, mid + 1, end);
    //--经过上面的归并后两个子序列内部已经是有序的，若两个子序列中第二个子序列的第一个元素已经大于第一个子序列的最后一个元素，则不需要排序；
    if (a[mid] <= a[mid + 1])
    {
        return true;
    }
    merge(a, begin, mid, mid + 1, end);
    return true;
}
void merge(vector<int> &a, int l_begin, int l_end,int r_begin,int r_end)
{
    //if (l_begin == l_end&&r_begin == r_end)     //--如果只有一个元素，则只需比较一次比较了；
    //{
    //    if (a[l_begin]>a[r_begin])
    //    {
    //        int s = a[r_begin];
    //        a[r_begin] = a[l_begin];
    //        a[l_begin] = s;        
    //    }
    //    return ;
    //}
    //
    int leng1 = l_end - l_begin + 1;
    int leng2 = r_end - r_begin + 1;
    //--创建两个临时的vector进行存放序列；
    vector<int> temp_L;
    vector<int> temp_R;
    for (int i = 0; i < leng1; i++)
    {
        temp_L.push_back(a[l_begin+i]);
    }
    for (int i = 0; i < leng2; i++)
    {
        temp_R.push_back(a[r_begin + i]);
    }
    int i = 0;
    int j = 0;
    while (i < leng1 && j < leng2)
    {
        if (temp_L[i] <= temp_R[j])
        {
            a[l_begin + i + j] = temp_L[i];
            i++;
        }
        else
        {
            a[l_begin + i + j] = temp_R[j];
            j++;
        }
    }
    //--当某个其中一个序列的元素已经全部被放置进入归并后的序列，此时直接将第另一个剩下部分序列放入归并序列即可；
    while (i <leng1)
    {
        a[l_begin + i + j] = temp_L[i];
        i++;
    }
    while (j <leng2)
    {
        a[l_begin + i + j] = temp_R[j];
        j++;
    }
    return ;
}
void main()
{
    ifstream inmyfile("123.txt");
    ofstream outmyfile("1234.txt");
    string line;
    vector<int> A;
    if (inmyfile)
    {
        int x;
        while (getline(inmyfile,line))
        {
            istringstream is(line);
            string s;
            while (is>>s)
            {
                x = atoi(s.c_str());
                A.push_back(x);
            }
        }
    }
    else
    {
        cout << "get input file was fail" << endl;
    }
    int len = A.size();
    merge_sort(A, 0, len-1);
    for (int i = 0; i < len; i++)
    {
        outmyfile << A[i] << " ";
    }
    cout << endl;
    cout << A[10];
    system("pause");
}