首页 / 算法 / 算法学习之排序(6)--合并排序

算法学习之排序(6)--合并排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法学习之排序(6)--合并排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2779字，纯文字阅读大概需要4分钟。

内容图文

一.算法描述

    归并排序将一个序列分成两个长度相等的子序列，为每一个子序列调用归并排序进行排序，然后再将它们合并成一个序列。合并两个子序列的过程称为归并，归并排序的运行时间并不依赖与输入数组中元素的组合方式。
    归并排序总是递归调用自己对子序列进行排序，递归退出的条件为数组中只包含一个元素时，函数不进行其他操作，直接返回。


二.时间复杂度

    归并排序每次都是将序列分成相等的两个子序列，因此，归并排序的时间复杂度与输入数组中的元素是否已经排序无关，在最好情况下，平均情况下和最差情况下的时间复杂度都为O(nlogn)。



三.空间复杂度

    归并排序的归并过程需要将两个子序列进行归并，如果是使用数组之类的结构存储数据的话，需要将两个子序列复制到额外的空间中，然后再进行归并，因此，使用数组作为存储结构的话，空间复杂度为O(n)。如果是使用的是链表作为数据的存储结构的化，那么两个子序列进行归并的过程只是将链表中的元素放到另外一个链表中，并不需要复制元素的值，空间复杂度为O(1)。



四.C++实现 

#include <iostream>

#include "Sort.h"
#include "randomarray.h"

bool Merge(std::vector<int>::iterator Ite, int LeftIndex, int RightIndex)
{
    if (LeftIndex >= RightIndex)
    {
        return false;
    }

    if (LeftIndex == (RightIndex - 1))
    {
        return true;
    }


    int Mid = (LeftIndex + RightIndex) / 2;


    // copy the array
    std::vector<int> LeftArray;
    for (int Index = LeftIndex; Index < Mid; Index++)
    {
        int Tmp = *(Ite + Index);
        LeftArray.push_back(*(Ite + Index));
    }

    std::vector<int> RightArray;
    for (int Index = Mid; Index < RightIndex; Index++)
    {
        int Tmp = *(Ite + Index);
        RightArray.push_back(*(Ite + Index));
    }


    // merge the sub array
    for (int Index_left = 0, Index_right = 0, Index = LeftIndex;
    Index < RightIndex;
    Index++)
    {
        // Ended merge the left array
        if (Index_left >= LeftArray.size())
        {
            int Tmp = RightArray[Index_right];
            *(Ite + Index) = RightArray[Index_right++];
            continue;
        }

        // Ended merge the right array
        if (Index_right >= RightArray.size())
        {
            int Tmp = LeftArray[Index_left];
            *(Ite + Index) = LeftArray[Index_left++];
            continue;
        }

        // merge the two array
        if (RightArray[Index_right] > LeftArray[Index_left])
        {
            int Tmp = LeftArray[Index_left];
            *(Ite + Index) = LeftArray[Index_left++];
        }
        else
        {
            int Tmp = RightArray[Index_right];
            *(Ite + Index) = RightArray[Index_right++];
        }
    }

    return true;

}






bool MergeSort(std::vector<int>::iterator Ite, int LeftIndex, int RightIndex)
{
    // return false if the LeftIndex >= RightIndex
    if (LeftIndex >= RightIndex)
    {
        return false;
    }


    // return true when there are only one element in the array
    if (LeftIndex == (RightIndex - 1))
    {
        return true;
    }


    // split the array to two sub array
    int Mid = (LeftIndex + RightIndex) / 2;
    MergeSort(Ite, LeftIndex, Mid);
    MergeSort(Ite, Mid, RightIndex);

    // Merge the sub array
    return Merge(Ite, LeftIndex, RightIndex);

}


bool MergeSort(std::vector<int>& Array)
{
    int Size = Array.size();

    if (Size == 0)
    {
        return false;
    }

    if (Size == 1)
    {
        return true;
    }

    return MergeSort(Array.begin(), 0, Size);
}


五.参考文献

[1] Shaffer C A. Practical Introduction to Data Structure and Algorithm Analysis (C++ Edition)[J]. 2002.
[2] 科曼 and 金贵, 算法导论: 机械工业出版社, 2006.
[3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "算法导论 (影印版)," ed: 北京: 高等教育出版社.






原文：http://blog.csdn.net/sheng_ai/article/details/44664619

内容总结

以上是互联网集市为您收集整理的算法学习之排序(6)--合并排序全部内容，希望文章能够帮你解决算法学习之排序(6)--合并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1150637.html

来源：【匿名】