python实现归并排序算法

待我称王封你为后i 2022-05-09 00:28 157阅读 0赞

前面我们讲了[归并排序算法][Link 1]，接下来我们来python代码实现呗，如下

#!/usr/bin/python
    # -*- coding: utf-8 -*-
    #归并排序
    
    def _last_merge_sort(list1, list2):
        i, j = (0, 0)
        temp = []
        while i < len(list1) and j <len(list2):
            if list1[i] <= list2[j]:
                temp.append(list1[i])
                i += 1
            else:
                temp.append(list2[j])
                j += 1
    
        if i == len(list1):#说明list1遍历完了，只剩下list2后面一点(有可能剩一个，有可能剩很多)，因为是排序好的，所以追加即可
            for k in list2[j:]:
                temp.append(k)
        else:
            for k in list1[i:]:
                temp.append(k)
        print "===================="+str(temp)
        return temp
    
    def _merge_sort(the_list):
        print the_list
        if len(the_list) == 1:
            return the_list
        else:
            mid = len(the_list)/2
            left = _merge_sort(the_list[:mid])
            right = _merge_sort(the_list[mid:])
            return _last_merge_sort(left, right)
    
    if __name__ == '__main__':
        the_list = [8, 4, 5, 7, 1, 3, 6, 2,8]
        print _merge_sort(the_list)

运行，结果如下

[8, 4, 5, 7, 1, 3, 6, 2, 8]
    [8, 4, 5, 7]
    [8, 4]
    [8]
    [4]
    ====================[4, 8]
    [5, 7]
    [5]
    [7]
    ====================[5, 7]
    ====================[4, 5, 7, 8]
    [1, 3, 6, 2, 8]
    [1, 3]
    [1]
    [3]
    ====================[1, 3]
    [6, 2, 8]
    [6]
    [2, 8]
    [2]
    [8]
    ====================[2, 8]
    ====================[2, 6, 8]
    ====================[1, 2, 3, 6, 8]
    ====================[1, 2, 3, 4, 5, 6, 7, 8, 8]
    [1, 2, 3, 4, 5, 6, 7, 8, 8]

符合预期

[Link 1]: https://blog.csdn.net/stronglyh/article/details/82891473