python实现归并排序算法

时间:2022-01-30 21:02:42

摘要:

本文主要介绍的是python实现归并排序算法,本文首先会介绍归并排序的原理,并以一张思维导图来加深读者对该算法过程的理解,紧接着进行代码的实现。最后介绍该算法的时间复杂度。

一.原理:

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

2.在将这两个子序列按照第一步继续二分下去;

3.直到所有子序列的长度都为1,也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

 

下面的这张图片可以很清晰的解释该原理:

python实现归并排序算法

二.代码如下:

def merge(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 merge_sort(lists):
   if len(lists) <= 1:
       return lists
   middle = len(lists)//2
   left = merge_sort(lists[:middle])
   right = merge_sort(lists[middle:])
   return merge(left, right)


if __name__ == '__main__':
   a = [14, 2, 34, 43, 21, 19]
   print (merge_sort(a))

 时间复杂度:

  • 最优时间复杂度:O(nlongn)

    最坏时间复杂度 :O(nlongn)

    稳定性:稳定

     

参考链接:https://blog.csdn.net/su_bao/article/details/81053871