C++模板归并排序

旧城等待， 2022-08-21 00:20 139阅读 0赞

# C++模板归并排序 #

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。  
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。  
**递归法：**  
原理如下（假设序列共有n个元素）：  
将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素  
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素  
重复步骤2，直到所有元素排序完毕。

归并排序的性能描述：  
数据结构 数组  
最差时间复杂度 Θ(nlogn)  
最优时间复杂度 Θ(n)  
平均时间复杂度 Θ(nlogn)  
最差空间复杂度 Θ(n)

以上内容摘自**维基百科**

递归法应该是比较好理解的，分治模式的三个步骤：  
分解（Divide）  
解决（Conquer）  
合并（Combine）  
对于排序来说，我们分解到一个最小的问题就是子序列中只有一个元素（一个元素肯定是有序的嘛）。分解的过程就是通过不断递归实现的，通过递归返回到上层递归，开始完成1个元素到2个元素，2个元素到4个元素等等最终到有序序列过程的合并。

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

# 代码 #

递归实现二路归并排序  
这里有一点让我挠头的就是表示无穷大。。。书中直接用那个倒八字来表示了，而我用模板写，就要考虑不同数值类型的最大值，后来查资料用到了`<limits>`里面的`std::numeric_limits<T>::max()`来表示

/*MySort.h*/
    #ifndef MYSORT_H_
    #define MYSORT_H_
    #include <iostream>
    #include <limits>
    namespace MySort{
        template <typename T>
        void Merge(T*arr, int p, int q, int r)
        {
            int n1 = q - p + 1;//Llen
            int n2 = r - q;//Rlen
            T*L = new T[n1 + 1];
            T*R = new T[n2 + 1];
            int i, j;
            //创建两个array
            for (i = 0; i < n1; i++)
                *(L + i) = *(arr + p + i);
            for (j = 0; j < n2; j++)
                *(R + j) = *(arr + q + j + 1);
    
            //表示边界的无穷大
            *(L + n1) = std::numeric_limits<T>::max();
            *(R + n2) = std::numeric_limits<T>::max();
            i = 0;
            j = 0;
            for (int k = p; k <= r; k++)
            {
                if (*(L + i) <= *(R + j))
                {
                    *(arr + k) = *(L + i);
                    ++i;
                }
                else
                {
                    *(arr + k) = *(R + j);
                    ++j;
                }
            }
        }//Merge
        template <typename T>
        void MergeSort(T*arr, int p, int r)
        {
            if (p < r)
            {
                int q = p + (r - p) / 2;
                MergeSort(arr, p, q);//递归
                MergeSort(arr, q + 1, r);
                Merge(arr, p, q, r);
            }
        }//MergeSort
    }//namespace MySort
    #endif

测试程序

/*main.cpp*/
    #include <iostream>
    #include "MySort.h"
    using namespace std;
    int main()
    {
        double b[] = { 5.6, 3.9, 4.1, 4.8};
    
        MySort::MergeSort<double>(b, 0, (sizeof(b) / sizeof(double)) - 1);
        for (int i = 0; i < sizeof(b) / sizeof(double); i++)
        {
            cout << b[i] << " ";
        }
        cout << endl;
        system("PAUSE");
        return 0;
    }