排序算法——归并排序

亦凉 2022-06-12 00:49 257阅读 0赞

## 前言 ##

将待排序序列R\[0...n-1\]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

*[参考资料][Link 1]*

## 1. 编码 ##

//display
    template<typename T> struct Disp
    {
        void operator()(T value)
        {
            cout << value << "\t";
        }
    };
    
    void Merge(std::vector<int>& vec, int left, int midle, int right)
    {
        int i = left;       //第一个序列的起始位置
        int j = midle+1;    //第二个序列的起始位置
        int pos = 0;        //临时数组下标计数
    
    
        int* temp_array = new int[right-left+1];    //临时数组
    
    
        while(i<=midle && j<=right) //遍历两个序列，将小的数字放在前面
        {
            if(vec[i] < vec[j])
            {
                temp_array[pos++] = vec[i++];
            }
            else
            {
                temp_array[pos++] = vec[j++];
            }
        }
    
    
        while(i<=midle) //第一个序列没走完，那么将第一个序列的元素添加到后面去
            temp_array[pos++] = vec[i++];
    
    
        while(j<=right) //第二个序列没走完，那么将第二个序列的元素添加到后面去
            temp_array[pos++] = vec[j++];
    
    
        //更新原始的数组
        for(int i=0, k=left; k<=right; k++, i++)
            vec[k] = temp_array[i];
    
    
        delete[] temp_array;
        temp_array = nullptr;
    }
    
    
    void MergeSort(std::vector<int>& vec)
    {
        int len(vec.size());
        if(len == 0) return;
        cout << "display origin array:" << endl;
        for_each(vec.begin(), vec.end(), Disp<int>());  //打印原始的数据
    
    
        for (int gap = 1; gap<len; gap=2*gap)
        {
            int i = 0;
    
    
            // 归并gap长度的两个相邻子表
            for (i=0; i+2*gap-1<len; i=i+2*gap)
            {
                Merge(vec, i, i+gap-1, i+2*gap-1);
            }
    
    
            // 余下两个子表，后者长度小于gap
            if (i+gap-1 < len)
            {
                Merge(vec, i, i+gap-1, len-1);
            }
        }
    
    
        cout << "\narray sorted:" << endl;
        for_each(vec.begin(), vec.end(), Disp<int>());
    }

[Link 1]: http://www.cnblogs.com/jingmoxukong/p/4308823.html