数据结构-排序-合并排序

淩亂°似流年 2023-10-04 16:27 12阅读 0赞

#### 合并排序法 ####

合并排序法（Merge Sort）的工作原理是针对已经排好的两个或者两个以上的数列（或数据文件），通过合并的方式将其组合成一个大的且已经排好序的数列（或数据文件），步骤如下：

*  将N个长度为1的键值成对的合并成N/2个长度为2的键值组
 *  将N/2个长度为2的键值组成对地合并成N/4个长度为4的键值组
 *  将键值组不断地合并，知道合并成一组长度为N的键值组为止

**合并排序法的分析**

*  使用合并排序法，n项数据一般需要约logn次处理，每次处理的时间复杂度O(n)，所以合并排序法的最佳情况、最差情况及平均情况复杂度为O(nlogn)
 *  由于在排序过程中需要一个与数列（或数据文件大小相同的额外空间，故其空间复杂度O(n)
 *  是一个稳定（stable）的排序方式

"""
    合并排序：两个已经有顺序的数组进行合并排序
    """
    list1 = [21,6,4,3,999]
    list2 = [71,2,3,2,999]
    list3=[]
    """
    选择排序，先将数组进行排序
    """
    def select_sort(data,size):
        #第一次遍历，从第一个元素开始，逐个向后比较
        for base in range(len(data)):
            small = base
            #和第一层循环的元素逐个比较
            for next in range(base,size):
                if data[small] > data[next]:
                    small = next
            data[base],data[small] = data[small],data[base]
    
    """
    合并排序，将排序好的数组进行合并排序
    """
    def Merge(data,size1,size2):
        global list1
        global list2
        global list3
    
        index1 = 0
        index2 = 0
        for index3 in range(len(list1)+len(list2)-2):
            #逐个比较两个元组中的数据大小，将小的存放在新的数组中
            if list1[index1] < list2[index2]:
                data.append(list1[index1])
                #将index+1，下次循环比较下一个元素
                index1+=1
                print("此数字{}取自第一个数列".format(data[index3]))
            else:
                data.append(list2[index2])
                #将index2+=1，下次循环比较下一个元素
                index2+=1
                print("此数字{}取自第二个数列".format(list3[index3]))
            print("目前的合并排序结果是：")
            for i in range(index3 + 1):
                print(list3[i],'',end='')
            print('\n')
    
    """
    程序入口
    """
    def merge_sort():
        global list1
        global list2
        global list3
    
        #先对数组进行排序
        select_sort(list1,len(list1)-1)
        select_sort(list2,len(list2)-1)
    
        print("第一个数组的排序结果：")
        for i in range(len(list1)-1):
            print(list1[i],'',end='')
        print('')
        print("第二个数组的排序结果：")
        for i in range(len(list2)-1):
            print(list2[i],'',end='')
        print('')
    
        print("===========================================")
    
        #两个数组合并排序
        Merge(list3,len(list1)-1,len(list2)-1)
    
        print("===========================================")
    
        print("\n合并排序的结果：")
        for i in range(len(list1)+len(list2)-2):
            print(list3[i],'',end='')
        print('\n')
    
    if __name__ == '__main__':
        merge_sort()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210625200333136.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70