更多课程 选择中心


Python培训

400-111-8989

Python归并排序简介

  • 发布:Python培训
  • 来源: 叶藏手札
  • 时间:2019-12-09 11:42

一、Pythond归并排序

归并排序(Merge Sort)也称为合并排序,是1945年由约翰·冯·诺伊曼首次提出的一种创建在归并操作上的有效的排序算法,效率为O(nlogn)。该算法是遵循分而治之(Divide and Conquer)的方法,且各层分治递归可以同时进行。算法的基本思想是:将待排序数组分成两个子数组,使用归并排序递归地对两个子数组进行排序,将两个有序的子数组合并成一个大的有序的数组,通过递归,层层合并,即为归并。归并排序的执行过程如下图所示:

python归并排序

算法的基本过程包括两个过程:拆分与合并。

归并排序拆分阶段:

将待排序数组分成长度大约相等的两个子数组,每个子数组继续分成长度大约相等的两个子数组,递归实现,直到子数组只有一个元素为止(只有一个元素的数组是有序数组)。

归并排序合并阶段:

设定两个指针,最初位置分别为两个已经排序子数组的起始位置。

比较两个指针所指向的元素,选择相对小的元素放入到合并数组,并移动指针到下一位置。

重复上述步骤直到某一指针到达子数组尾部。

将另一子数组剩下的所有元素直接复制到合并数组尾部。

归并算法的整个过程如下图所示:

python归并排序

二、python归并排序算法代码实现:

# 归并排序

2def merge_sort(data_list):

3 length = len(data_list)

4 if length == 0 or length == 1:

5 return data_list

6 # 拆分为2个子数组

7 middle = length//2

8 left = data_list[:middle]

9 right = data_list[middle:]

10 # 递归使用归并排序子数组

11 new_left = merge_sort(left)

12 new_right = merge_sort(right)

13 # 合并2个已排序子数组

14 sort_list = merge(new_left,new_right)

15 return sort_list

16

17# 合并函数

18def merge(left,right):

19 sort_list = []

20 while len(left) != 0 and len(right) != 0:

21 if left[0] < right[0]:

22 sort_list.append(left[0])

23 left.remove(left[0])

24 else:

25 sort_list.append(right[0])

26 right.remove(right[0])

27

28 if len(left) == 0:

29 sort_list += right

30 else:

31 sort_list += left

32

33 return sort_list

测试结果:

python归并排序

免责声明:内容和图片源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

预约申请免费试听课

填写下面表单即可预约申请免费试听! 怕学不会?助教全程陪读,随时解惑!担心就业?一地学习,可全国推荐就业!

上一篇:Python正则表达式及应用
下一篇:Python面向对象编程基础知识

2021年Python全套免费视频教程在哪里?

人工智能与语音遥控的区别?

Python和C语言的区别?

Python数据分析的几种方法及原理?

  • 扫码领取资料

    回复关键字:视频资料

    免费领取 达内课程视频学习资料

Copyright © 2023 Tedu.cn All Rights Reserved 京ICP备08000853号-56 京公网安备 11010802029508号 达内时代科技集团有限公司 版权所有

选择城市和中心
黑龙江省

吉林省

河北省

湖南省

贵州省

云南省

广西省

海南省