Board logo

标题: 排序算法总结(python版)-5 [打印本页]

作者: look_w    时间: 2019-3-7 19:34     标题: 排序算法总结(python版)-5

归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
算法描述

    把长度为n的输入序列分成两个长度为n/2的子序列;
    对这两个子序列分别采用归并排序;
    将两个排序好的子序列合并成一个最终的排序序列。

    def merge(ls1,ls2):
        res = []
        index1 = index2 = 0
        while(index1 < len(ls1) and index2 < len(ls2)):
            if ls1[index1] <= ls2[index2]:
                res.append(ls1[index1])
                index1 += 1
            else:
                res.append(ls2[index2])
                index2 += 1
        res += (ls1[index1:] if index1 < len(ls1) else ls2[index2:])
        return res
    def MergeSort(ls):
        length = len(ls)
        if length < 2:
            return ls
        return merge(MergeSort(ls[:length//2]),MergeSort(ls[length//2:]))
    def MergeSort2(ls):
        index = 1
        while(index<len(ls)):
            index *= 2
            for i in range(0,len(ls),index):
                ls[i:i+index] = merge(ls[i:i+index//2],ls[i+index//2:i+index])
            print(ls)
        return ls

归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。




欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) Powered by Discuz! 7.0.0