python 排序（三）归并排序

电玩女神 2023-08-17 15:31 56阅读 0赞

## **一、介绍** ##

归并排序与快速排序都是利用了分治的策略

基本原理与思想：

1、将一个序列从中间位置分成两个序列

2、将两个子序列重复第一步的操作，直到所有子序列长度为一

3、将所有子序列进行归并，每两个序列比较第一个元素的大小，将小的拿出来

## **二、代码实现** ##

def merger(a, b):
        c = []
        h = j = 0
        while j < len(a) and h < len(b):
            if a[j] < b[h]:
                c.append(a[j])
                j += 1
            else:
                c.append(b[h])
                h += 1
        if j == len(a):
            for i in b[h:]:
                c.append(i)
        else:
            for i in a[j:]:
                c.append(i)
        return c
    
    def merger_sort(lis):
        #print lis
        if len(lis) <= 1:
            return lis
        mid = len(lis) // 2
        left_lis = merger_sort(lis[:mid])
        right_lis = merger_sort(lis[mid:])
        return merger(left_lis, right_lis)
    
    
    
    if __name__ == '__main__':
        lis = [14, 2, 34, 43, 21, 19,14,33,25,64,11,13]
        print merger_sort(lis)

## **三、总结** ##

**稳定性：稳定，因为每次排序的过程都是一样的**

**时间复杂度：****O(nlongn)**

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 python希尔排序、归并排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插

Myth丶恋晨/ 2023年06月11日 10:21/ 0 赞/ 56 阅读

相关归并排序（Python）

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

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

相关排序算法第三谈：归并排序

> 归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单

小灰灰/ 2023年01月02日 01:17/ 0 赞/ 77 阅读

相关【排序】归并排序

归并排序 `归并操作（merge）`，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作. 参考之前的，[合并两个有序数组][Link 1

短命女/ 2022年12月13日 12:40/ 0 赞/ 163 阅读

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

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

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

相关【排序】归并排序

归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列,首先做两两归并，得到n /

落日映苍穹つ/ 2022年06月18日 10:45/ 0 赞/ 222 阅读

相关【算法三】—— 归并排序

归并排序插入排序算法采取增量式（Incremental）的策略解决问题，每次添一个元素到已排序的子序列中，逐渐将整个数组排序完毕，它的时间复杂度是O(n2)。下面介绍另

痛定思痛。/ 2022年05月30日 08:36/ 0 赞/ 124 阅读

相关归并类排序-----归并排序

/归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合

绝地灬酷狼/ 2022年05月03日 01:56/ 0 赞/ 226 阅读

相关 Python之归并排序

归并排序：是一种递归算法，它持续地将一个列表平均分成两半。如果列表是空的或者只有一个元素，那么它就被排好了(最基本情况)。如果列表里的元素超过一个，就把列表继续拆分，然后

小鱼儿/ 2022年02月20日 08:49/ 0 赞/ 176 阅读