精华内容
下载资源
问答
  • Python实现归并排序

    2020-07-14 23:10:27
    Python实现归并排序

    Python实现归并排序

    一、归并排序简介

    归并排序(Merge Sort)是建立在归并操作上的一种效率很高的排序算法,比较占用内存。该算法是分治法(Divide and Conquer)的一个典型应用。

    归并排序将两个或两个以上(一般是两个)有序的列表合并成一个新的有序列表。待排序列表是无序的,使用二分法递归地将列表最终拆分成只有一个元素的子表,只有一个元素的列表一定是有序的,此时递归往回合并,即可依次将待排序列表拆分然后合并成一个有序的列表。

    二、归并排序原理

    归并排序的原理如下:

    1. 假设有两个已经有序的列表,设定两个指针分别指向这两个列表的起始元素,申请内存空间新建一个空列表,比较两个指针指向的元素大小,将较小的元素添加到新列表中,然后将该指针向该列表的下一个元素偏移,继续比较两个指针指向的元素和添加较小的到新列表中。直到其中一个列表的数据全部被添加完时,把另一个列表中剩下的数据按顺序添加到新列表中。这就实现了将两个有序列表合并成一个新的有序列表的方法。

    2. 对待排序列表进行拆分,递归地拆分直到子列表中只有一个元素。

    3. 只有一个元素的子列表一定是有序的,使用1中的方法对有序的子列表进行合并。第一次合并后新列表是有两个元素的有序列表,递归地往回合并,直到所有数据都合并到一个新的有序列表中,列表排序完成。

    以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。

    要进行升序排列,则合并两个有序子列表时,子列表也要是升序排列的,子列表只有一个元素时,先添加较小的数据到新列表中(降序反之)。

    1. 先对待排序列表进行拆分,分成两个子列表,一般从 n/2 索引的位置进行拆分。例子中有12个元素,两个子列表都有6个元素。

    2. 进行合并的前提是两个子列表都是有序的。待排序列表是无序的,第一次拆分后无法保证两个子列表都是有序的,所以继续对子列表进行拆分。左边的子表有6个元素,继续拆分成两个有3个元素的子表。

    3. 现在的子表中有3个元素,还是无法保证一定有序,继续拆分。拆分后,一个子表只有1个元素,另一个子表有2个元素。

    4. 对于只有1个元素的子表,它一定是有序的,直接返回,等待与它一起拆分出来的另一个子表有序时进行合并。

    5. 对于有2个元素的子表,对它再进行一次拆分,分成两个都是只有1个元素的子表,然后进行合并,合并成有2个元素的有序列表。

    6. 将上面有1个元素的子表和经过一次合并后有2个元素的有序列表进行合并,合并成有3个元素的有序列表。

    7. 对同时拆分出来的另3个元素也进行相同的处理,递归拆分和合并成有3个元素的有序列表。

    8. 两个有3个元素的子表都有序后,对它们进行合并,合并成有6个元素的有序列表。

    9. 对同时拆分出来的另6个元素也进行相同的处理,递归拆分和合并成有6个元素的有序列表。

    10. 两个有6个元素的子表都有序后,对它们进行合并,合并成最终的有序列表,列表排序完成。排序结果如下图。

    三、Python实现归并排序

    # coding=utf-8
    def merge_sort(array):
        if len(array) == 1:
            return array
        left_array = merge_sort(array[:len(array)//2])
        right_array = merge_sort(array[len(array)//2:])
        return merge(left_array, right_array)
    
    
    def merge(left_array, right_array):
        left_index, right_index, merge_array = 0, 0, list()
        while left_index < len(left_array) and right_index < len(right_array):
            if left_array[left_index] <= right_array[right_index]:
                merge_array.append(left_array[left_index])
                left_index += 1
            else:
                merge_array.append(right_array[right_index])
                right_index += 1
        merge_array = merge_array + left_array[left_index:] + right_array[right_index:]
        return merge_array
    
    
    if __name__ == '__main__':
        array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
        print(merge_sort(array))

    运行结果:

    [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

    在代码中,先实现了将两个有序列表进行合并的 merge(left_array, right_array) 函数。在该函数中,传入的两个列表(左表和右表)都是排好序的(升序或降序,上面代码中是升序)。先声明两个游标指针和一个新列表,两个指针一开始分别指向两个列表的起始位置,将两个指针指向的数据进行比较,然后将较小的数据添加到新列表中,被添加数据的指针向右移。当其中一个列表中的数据全部被添加到新列表中(指针再右移就会越界)时,此列表为空,停止移动和比较,此时,另一个列表中还剩若干个(1~n个)数据没有被添加到新列表中,继续按顺序将这些数据添加到新列表的尾部。

     实现归并排序函数merge_sort(array)时,递归调用merge(left_array, right_array)函数。在merge(left_array, right_array)函数对两个列表进行合并时,这两个列表必须都是有序的,而对待排序列表进行拆分时,无法保证两个子表一定是有序的,只有当被拆分的子表里只有一个元素时,这个子列表才一定是有序的。所以归并排序中递归地将待排序列表进行拆分,直到拆分成只有一个元素的列表,然后调用merge(left_array, right_array)函数进行合并,这样依次递归合并,最终实现归并排序。

    四、归并排序的时间复杂度和稳定性

    1. 时间复杂度

    在归并排序中,不管待排序列表的初始状态如何,都不影响排序的时间复杂度。归并排序一直对待排序列表进行拆分,需要进行logn次拆分,在每一次递归合并中,需要进行n次比较和添加。时间复杂度为 T(n)=nlogn ,再乘每次操作的步骤数(常数,不影响大O记法),所以归并排序的时间复杂度为 O(nlogn) 。

    对归并排序改进,可以在归并时先判断左表最大值与右表最小值的关系。如果左表的最大值小于等于右表的最小值,则说明待排序列表本身就是一段有序序列,不需要再归并,在待排序列表本身就有序的情况下,时间复杂度可以降至 O(n)。

    2. 稳定性

    在归并排序合并的过程中,如果有相等的数据,会先添加左表的数据到新列表中,再添加右表的数据,这不会改变相等数据的相对位置。所以归并排序是一种稳定的排序算法。

     

     

    展开全文
  • python实现归并排序

    2019-03-06 19:39:49
    python实现归并排序 今天用python实现了排序算法之一的归并排序,归并排序主要采用了分而治之的思想。下面是我的全部代码,采用python3实现,在网上看了很多归并排序的代码,代码不同,思想相同,我的代码也会有一些...

    python实现归并排序

    今天用python实现了排序算法之一的归并排序,归并排序主要采用了分而治之的思想。下面是我的全部代码,采用python3实现,在网上看了很多归并排序的代码,代码不同,思想相同,我的代码也会有一些不方便的地方,大家一起学习交流

    import random
    import math
    
    list_number=10        #列表元素的个数
    max_number=99999        #哨兵
    
    def merge(list,p,q,r):    #合并
        n1=q-p+1
        n2=r-q
        list1=[]
        list2=[]
        for i in range(n1):
            list1.append(list[p+i])
        for j in range(n2):
            list2.append(list[q+j+1])
        list1.append(max_number)
        list2.append(max_number)
        i=0
        j=0
        for k in range(p,r+1):
            if(list1[i]<=list2[j]):
                list[k]=list1[i]
                i=i+1
            else:
                list[k]=list2[j]
                j=j+1
                
    def merge_sort(list,p,r):  #分而治之
        if(p<r):
            q=math.floor((p+r)/2)
            merge_sort(list,p,q)
            merge_sort(list,q+1,r)
            merge(list,p,q,r)
    
    list=[]
    for n in range(list_number):         #生成随机数初始化列表
        list.append(random.randint(1,1000))
    
    merge_sort(list,0,len(list)-1)
    
    for x in range(list_number):#打印看结果
        print(list[x],end=' ')
    
    展开全文
  • python 实现归并排序

    2021-02-26 22:26:49
    #python 实现归并排序 #分而治之的思想 时间复杂度 O(nlogn) def merge_sort(li): # 作用 将传递进来的列表拆分到最小单元(函数的出口) if len(li) == 1: return li mid = len(li) // 2 left = li[:mid] ...

    归并排序–分而治之

    思想:分而治之,数组从中间划分,一分为二,递归的解决左右子集
    核心:合并有序的数组
    时间复杂度 o(nlogn)o(nlogn),以2为底
    时间复杂度分析:长度为n的数组,二分需要log(n)log(n)次
    合并有序数组,需进行规模为n的操作,所以需要nlognn*logn规模的运算

    缺点:需要额外的辅助空间 O(n)O(n)

    要求:十五分钟以内写出归并排序

    #python 实现归并排序
    #分而治之的思想 时间复杂度 O(nlogn)
    
    
    def merge_sort(li):
        # 作用 将传递进来的列表拆分到最小单元(函数的出口)
        if len(li) == 1:
            return li
    
        mid = len(li) // 2
        left = li[:mid]
        right = li[mid:]
        left_li = merge_sort(left)  # 判断 left列表是否为最小单元
        right_li = merge_sort(right)    # 判断 right列表是否为最小单元
        return marge(left_li, right_li)  # 合并
        # print(left_li,right_li)
                                               
    def marge(left_li, right_li):
        reslut = []
        while len(left_li) > 0 and len(right_li) > 0:
            if left_li[0] > right_li[0]:
                reslut.append(right_li.pop(0))
            else:
                reslut.append(left_li.pop(0))
    
        if left_li:
            reslut.extend(left_li)
        if right_li:
            reslut.extend(right_li)
    
        return reslut
    
    
    s = merge_sort([1,5,3,2,6,8,4])
    print(s)
    
    展开全文
  • 主要为大家详细介绍了Python实现归并排序算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Python 实现归并排序

    2018-12-06 18:35:28
    归并排序的算法过程运用的是分治法的思想,先将数组不断划分为2个,然后依次向上合并,用Python写起来简单很多。 需要注意的是归并排序需要借助额外的空间。 # merge sort # 归并排序 def merge_sort(lst): if...

    归并排序的算法过程运用的是分治法的思想,先将数组不断划分为2个,然后依次向上合并,用Python写起来简单很多。

    需要注意的是归并排序需要借助额外的空间。

    # merge sort
    # 归并排序
    
    
    def merge_sort(lst):
        if len(lst) <= 1:
            return lst
        middle = int(len(lst)/2)
        left = merge_sort(lst[:middle])
        right = merge_sort(lst[middle:])
        merged = []
        while left and right:
            merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
        merged.extend(right if right else left)
        return merged
    
    
    data_lst = [6, 202, 100, 301, 38, 8, 1]
    print(merge_sort(data_lst))

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,301
精华内容 520
关键字:

python实现归并排序

python 订阅