小小千想和您聊一聊

当前位置: 首页> 技术分享> Python实现归并排序算法

Python实现归并排序算法

Python实现归并排序算法

归并排序1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

分治法的基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

归并排序的基本思想

排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

动画

(请在发表文章时插入 ms.webp 这张图片)

代码实现

```python def merge(left, right): '''合并和排序''' i = 0 j = 0 result = [] lengthleft = len(left) lengthright = len(right)

while i < length_left and j < length_right:
    # 逐个比较两个列表的元素
    # 小的添加进新列表,大的留下继续比较
    if left[i] <= right[j]:
        result.append(left[i])
        i += 1
    else:
        result.append(right[j])
        j += 1

# 最后加上未比较的元素
result.extend(left[i:])
result.extend(right[j:])
return result

def merge_sort(lists): '''归并排序入口,拆分列表''' # 递归退出条件判断 length = len(lists) if length <= 1: return lists

# 递归拆分,取整,兼容py3
mid = length // 2
left = merge_sort(lists[:mid])
right = merge_sort(lists[mid:])

# 合并排序(归并排序)
return merge(left, right)

numbers = [4, 0, 7, 9, 2, 8, 1, 3, 6, 5] assert merge_sort(numbers) == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ```

上一篇:Python实现快速排序算法

下一篇:SEM广告投放时应该注意什么

QQ技术交流群

千锋Python官方①群
790693323

加入群聊

用户登录

手机号:

密码:

图形验证码:

点击切换

用户注册

手机号:

登录密码:

图形验证码:

点击切换

短信验证码:

获取验证码

忘记密码

1安全验证

2重置密码

手机号:

图形验证码:

短信验证码:

获取验证码

忘记密码

1安全验证

2重置密码

新密码:

确认新密码:

获取课程

添加小千老师微信,获取课程信息

如何获取课程?

一、需拥有此本教材

如没有,可点击下方入口购买当当购买入口京东购买入口

二、添加小千老师,发送拥有凭证,解锁课程资源

1.购买该教材的订单信息
2.拥有的实体书信息等

更换手机号

新手机号:

图形验证码:

短信验证码:

获取验证码