数据结构-二路归并及归并排序

谁借莪１个温暖的怀抱￠ 2022-06-04 07:48 366阅读 0赞

#### **一、介绍：** ####

##### 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 #####

该算法的核心思想是二路归并。

--------------------

#### **二、二路归并介绍** ####

##### **<1>在归并的过程中步骤如下：** #####

##### ①设定两个指针（不一定非是指针，只需要记住对应开始下标即可），最初位置分别为两个已经排序序列的起始位置； #####

##### ②比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置； #####

##### ③重复步骤3直到某一指针达到序列尾； #####

##### ④将另一序列剩下的所有元素直接复制到合并序列尾； #####

--------------------

##### **<2>例如：将a1,a2两个有序数列合并为一个序列。** #####

void Merge(int* a1, int a1size, int* a2, int a2size, int* res)
    {
        //合并两个有序序列a1 a2 结果保存在res数组中
        int a1_index, a2_index, res_index;
        a1_index = a2_index = res_index = 0;
        while (a1_index < a1size && a2_index < a2size)
        {
            if (a1[a1_index] < a2[a2_index])
                res[res_index++] = a1[a1_index++];
            else
                res[res_index++] = a2[a2_index++];
        }
    
        //将a1或a2剩余部分插入到res
        while (a1_index < a1size)
            res[res_index++] = a1[a1_index++];
        while (a2_index < a2size)
            res[res_index++] = a2[a2_index++];
    }
    
    int main()
    {
        int a1[] = { 2,3,5 };
        int a2[] = { 2,9 };
        int a1size = sizeof(a1) / sizeof(a1[0]);
        int a2size = sizeof(a2) / sizeof(a2[0]);
        int a3size = a1size + a2size;
        int* a3 = new int[a3size];
    
        Merge(a1, a1size, a2, a2size, a3);
    
        for (int i = 0; i < a3size; i++)
            cout << a3[i] << " " << endl;
    
        system("pause");
        return 0;
    }

##### 输出结果为：2 2 3 5 9 #####

--------------------

##### **<3>图解二路归并：** #####

![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]

--------------------

#### **三、归并排序主体思想：** ####

##### 1. Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。 #####

##### 2. Conquer: 对这两个子序列分别采用归并排序。 #####

##### 3. Combine: 将两个排序好的子序列合并成一个最终的排序序列。 #####

##### 简而言之就是将整个数组划分到不能再划分为止，划分的过程可以通过递归来实现而，再依次进行归并操作，在归并的过程中，借助另一个数组来暂时存放该区间排序后的结果，再拷贝回原数组。来张图形象的理解下： #####

![这里写图片描述][SouthEast 3]

--------------------

#### **四、代码实现及测试：** ####

#include <iostream>
    
    using namespace std;
    
    //将子序列归并为一个完整序列
    void Merge(int* a, int first, int mid, int last, int* res)
    {
        //将a[first mid] a[mid+1 last]排序合并
        int first_start = first, first_end = mid;
        int second_start = mid + 1, second_end = last;
        int res_index = 0;
        while (first_start <= mid && second_start <= last)
        {
            if (a[first_start] < a[second_start])
                res[res_index++] = a[first_start++];
            else
                res[res_index++] = a[second_start++];
        }
    
        while (first_start <= mid)
            res[res_index++] = a[first_start++];
    
        while (second_start <= last)
            res[res_index++] = a[second_start++];
    
        //拷贝回原来的空间
        for (int i = 0; i < res_index; i++)
            a[first + i] = res[i];
    }
    
    //递归不断划分区间
    void merge_sort(int* a, int first, int last, int* res)
    {
        if (first >= last)
            return;
    
        int mid = (first + last) / 2;
        merge_sort(a, first, mid, res);     //左边有序    
        merge_sort(a, mid + 1, last, res);  //右边有序    
        Merge(a, first, mid, last, res);    //将左右两个有序数列进行排序归并
    }
    
    
    bool MergeSort(int a[], int n)
    {
        int *res = new int[n];
        if (res == NULL)
            return false;
        merge_sort(a, 0, n - 1, res);
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
    
        delete[] res;
        return true;
    }
    
    
    int main()
    {
        int a[] = {
       3,2,5,9,2};
        MergeSort(a, sizeof(a) / sizeof(a[0]));
    
        system("pause");
        return 0;
    }

##### 输入结果为：2 2 3 5 9 #####

--------------------

#### **五：图示整个归并排序过程：** ####

![这里写图片描述][SouthEast 4]

--------------------

#### **六、优化思路** ####

##### 由于使用递归的方式将数组划分到不能再划分为止，再依次进行排序后归并，栈帧开销非常大，可以采用小区间优化的方式，在划分的过程中判断子序列的元素个数，若小于10（可根据情况而定），可利用插入排序来直接完成此段空间的排序过程。这样一来就可以减少递归次数，尤其是当数据量变大时就会很明显（插入排序讲解参考[插入排序讲解][Link 1]） #####

--------------------

#### **七、非递归实现** ####

##### 非递归实现中，就不需要先划分为一个再归并，而是直接可以归并两个元素，然后四个，八个…，假如数组为6,2,8,1,5,4，非递归过程图示如下： #####

![这里写图片描述][SouthEast 5]

--------------------

##### 代码实现： #####

void Merge(int* a, int first, int mid, int last, int* res)
    {
        //将a[first mid] a[mid+1 last]排序合并
        int first_start = first, first_end = mid;
        int second_start = mid + 1, second_end = last;
        int res_index = 0;
        while (first_start <= mid && second_start <= last)
        {
            if (a[first_start] < a[second_start])
                res[res_index++] = a[first_start++];
            else
                res[res_index++] = a[second_start++];
        }
    
        while (first_start <= mid)
            res[res_index++] = a[first_start++];
    
        while (second_start <= last)
            res[res_index++] = a[second_start++];
    
        //拷贝回原来的空间
        for (int i = 0; i < res_index; i++)
            a[first + i] = res[i];
    }
    
    //len为数组元素个数
    void MergeSortNR(int* a,int len)
    {
        int size = 1; //size为一半部分的元素个数
        int left, right, mid;
        left = right = mid = 0;
        int* tmp = new int[len];
    
        while (size <= len - 1)
        {
            left = 0;
            while (left + size <= len -1)
            {
                //mid等于left+子序列一半的个数-1;
                mid = left + size - 1;
                right = mid + size;
    
                //若right超出数组范围，right=最后一个元素下标
                if (right > len - 1)
                    right = len - 1;
    
                Merge(a, left, mid, right, tmp);
                left = right + 1;
            }
            size *= 2;
        }
    }

[SouthEast]: /images/20220604/9aaaf7556b24414b84844836d8233864.png
[SouthEast 1]: /images/20220604/a21a68e643784ab3bf01a099ad0cd364.png
[SouthEast 2]: /images/20220604/dee0e24c468d40e9a9794fb70086677b.png
[SouthEast 3]: /images/20220604/e5cca09265c74f3896bdc942363638bc.png
[SouthEast 4]: /images/20220604/a602571722624ad6a030e67427e32885.png
[Link 1]: http://blog.csdn.net/sssssuuuuu666/article/details/78705431
[SouthEast 5]: /images/20220604/782002da2ac549d08767734867d8fea1.png