使用python实现归并排序

朱雀 2022-06-07 07:19 222阅读 0赞

def merge(left, right):
        """归并两个数组 :param left: 第一个数组 :param right: 第二个数组 :return: 归并后的有序的的数组 """
        print("left", left)
        print("right", right)
    
        i, j = 0, 0
        n1, n2 = len(left), len(right)
        r = []
        while i < n1 and j < n2:
            while i < n1:
                if j == n2:
                    break
                if left[i] <= right[j]:
                    r.append(left[i])
                else:
                    break
                i += 1
            while j < n2:
                if i == n1:
                    break
                if right[j] <= left[i]:
                    r.append(right[j])
                else:
                    break
                j += 1
        r.extend(left[i:])
        r.extend(right[j:])
        return r
    
    
    def merge_sort(a):
        """ 使用递归来完成归并 :param a: 要排序的数组 :return: 返回值为排好序的数组 """
        if len(a) == 1:
            return a
    
        mid = len(a) >> 1
    
        left = merge_sort(a[:mid])  # 给左边排序
        right = merge_sort(a[mid:])  # 给右边排序
        return merge(left, right)
    
    
    if __name__ == "__main__":
        a = [10, 2, 3, 6, 8, 1, 10, 100, 200, 6]  # , 3, 10, 4, 3, 10, 10, 4, 3, 10]
        print(a)
        b = merge_sort(a)
        print(b)

发表评论取消回复

表情：

评论列表（有 0 条评论，222人围观）

还没有评论，来说两句吧...

相关阅读

相关 python 排序（三）归并排序

一、介绍归并排序与快速排序都是利用了分治的策略基本原理与思想： 1、将一个序列从中间位置分成两个序列 2、将两个子序列重复第一步的操作，直到所有子序列长度为一

电玩女神/ 2023年08月17日 15:31/ 0 赞/ 120 阅读

相关 Python：22归并排序

归并排序（Merge sort，或mergesort）创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的

约定不等于承诺〃/ 2023年05月28日 11:18/ 0 赞/ 110 阅读

相关归并排序（Python）

归并排序 <table> <thead> <tr> <th>排序算法</th> <th>平均时间复杂度</th> <th>空间复杂度</

悠悠/ 2023年01月03日 04:19/ 0 赞/ 177 阅读

相关 Python算法：归并排序

转自：[http://www.pinlue.com/article/2020/09/1916/3211244788559.html][http_www.pinlue.com_a

ゝ一世哀愁。/ 2022年12月11日 09:22/ 0 赞/ 115 阅读

相关 python实现归并排序

归并排序 “归并"是将两个或者两个以上的有序表组成一个新的有序表。假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为一，然后两两归并，得到n//2个长度为

末蓝、/ 2022年11月02日 11:55/ 0 赞/ 198 阅读

相关快速排序，归并排序，堆排序python实现

http://blog.csdn.net/u011608357/article/details/37724329 快速排序的时间复杂度最好情况下为O(n\lo

淡淡的烟草味﹌/ 2022年07月17日 02:53/ 0 赞/ 265 阅读

相关使用python实现归并排序

def merge(left, right): """归并两个数组 :param left: 第一个数组 :param right: 第二个数组 :re

朱雀/ 2022年06月07日 07:19/ 0 赞/ 223 阅读

相关改进版python实现的归并排序

def merge(a, begin, mid, end): left = a[begin:mid] right = a[mi

傷城~/ 2022年06月06日 06:53/ 0 赞/ 181 阅读

相关【数据结构算法】：Python实现归并排序

动图展示算法时间复杂度o(n\logn) ![849589-20171015230557043-37375010.gif][] python 归并的思路在于

小咪咪/ 2022年05月16日 00:38/ 0 赞/ 235 阅读

相关 python实现归并排序算法

前面我们讲了[归并排序算法][Link 1]，接下来我们来python代码实现呗，如下 !/usr/bin/python -- coding: utf-8

待我称王封你为后i/ 2022年05月09日 00:28/ 0 赞/ 237 阅读