python算法与数据结构-归并排序算法

柔光的暖阳◎ 2023-10-06 13:25 42阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 9][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 10][]

代码如下所示:

# -*-coding=utf-8-*-
    def merge_sort(alist):
        """归并排序"""
        n = len(alist)
        if n<=1:
            return  alist
        mid = n//2
        #print('mid结果是',mid) #mid结果是 4   mid结果是 2  mid结果是 1 mid结果是 1 mid结果是 2 mid结果是 1等等
        # print('mid前结果', alist[:mid],'mid后结果', alist[mid:])
        """
        mid前结果 [54, 26, 93, 17] mid后结果 [77, 31, 44, 55, 20]
        mid前结果 [54, 26] mid后结果 [93, 17]
        mid前结果 [54] mid后结果 [26]
        mid前结果 [93] mid后结果 [17]
        mid前结果 [77, 31] mid后结果 [44, 55, 20]
        mid前结果 [77] mid后结果 [31]
        mid前结果 [44] mid后结果 [55, 20]
        mid前结果 [55] mid后结果 [20]
        """
        #left 采用归并排序后形成的有序的新的列表
        left_li = merge_sort(alist[:mid]) #这个函数是递归分解后的数组
    
        #right 采用归并排序后形成的有序的新的列表
        right_li = merge_sort(alist[mid:]) #这个函数是递归分解后的数组
        #print('左侧开始结果', left_li, '右侧开始结果', right_li)
        """
        左侧开始结果 [54] 右侧开始结果 [26]
        左侧开始结果 [93] 右侧开始结果 [17]
        左侧开始结果 [26, 54] 右侧开始结果 [17, 93]
        左侧开始结果 [77] 右侧开始结果 [31]
        左侧开始结果 [55] 右侧开始结果 [20]
        左侧开始结果 [44] 右侧开始结果 [20, 55]
        左侧开始结果 [31, 77] 右侧开始结果 [20, 44, 55]
        左侧开始结果 [17, 26, 54, 93] 右侧开始结果 [20, 31, 44, 55, 77]
        """
        #return 999
        #将两个有序的子序列合并为一个新的整体
        #merge(left,right)
        left_pointer,right_pointer = 0,0
        result = []
    
        while left_pointer < len(left_li) and right_pointer < len(right_li):
              if left_li[left_pointer] <= right_li[right_pointer]:
                  result.append(left_li[left_pointer])
                  left_pointer += 1
              else:
                  result.append(right_li[right_pointer])
                  right_pointer += 1
              # print('第一次循环result结果',result)
              # return result
    
        #print('左侧result结果',left_li,'右侧result结果',right_li)
        """
    左侧result结果 [54] 右侧result结果 [26]
    左侧result结果 [93] 右侧result结果 [17]
    左侧result结果 [26, 54] 右侧result结果 [17, 93]
    左侧result结果 [77] 右侧result结果 [31]
    左侧result结果 [55] 右侧result结果 [20]
    左侧result结果 [44] 右侧result结果 [20, 55]
    左侧result结果 [31, 77] 右侧result结果 [20, 44, 55]
    左侧result结果 [17, 26, 54, 93] 右侧result结果 [20, 31, 44, 55, 77]
        """
        #print('左侧游标结果',left_pointer,'左侧结果值',left_li[left_pointer:],'右侧游标结果',right_pointer,'右侧结果值',right_li[right_pointer:])
        """
        左侧游标结果 0 左侧结果值 [54] 右侧游标结果 1 右侧结果值 []
        左侧游标结果 0 左侧结果值 [93] 右侧游标结果 1 右侧结果值 []
        左侧游标结果 2 左侧结果值 [] 右侧游标结果 1 右侧结果值 [93]
        左侧游标结果 0 左侧结果值 [77] 右侧游标结果 1 右侧结果值 []
        左侧游标结果 0 左侧结果值 [55] 右侧游标结果 1 右侧结果值 []
        左侧游标结果 1 左侧结果值 [] 右侧游标结果 1 右侧结果值 [55]
        左侧游标结果 1 左侧结果值 [77] 右侧游标结果 3 右侧结果值 []
        左侧游标结果 3 左侧结果值 [93] 右侧游标结果 5 右侧结果值 []
        """
        result += left_li[left_pointer:]
        result += right_li[right_pointer:]
        return  result
    
    if __name__ == "__main__":
            li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
            print(li)
            sorted_li = merge_sort(li)
            print(sorted_li)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020072016383648.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200720163902939.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200720163929446.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200720163947171.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200720164004372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200720164016457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200720164038329.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200720164106248.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200720164135445.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/2020072016415271.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200720164247489.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70