栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

归并排序Python

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

归并排序Python

归并排序 归并排序采用的是分治法的思想来进行排序的。 基本思想:分治法 分:先递归分解数组,将数组分解成最小的一个个元素 治:分解后的数组依次进行排序,最后合并数组。 最后得到了排好序的数组。 此处借鉴一张网上的图

时间复杂度:O(nlogn) 注意:归并排序是稳定的排序 代码:
def merge(left_arr, right_arr):
    """合并操作:将两个有序数组合并为一个有序数组"""

    left_index, right_index = 0, 0  # left_index, right_index 分别表示左边列表和右边列表的索引号
    result = []

    # 当左边列表或者右边列表走到头了,循环结束
    while left_index < len(left_arr) and right_index < len(right_arr):
        if left_arr[left_index] < right_arr[right_index]:
            result.append(left_arr[left_index])
            left_index += 1
        else:
            result.append(right_arr[right_index])
            right_index += 1
    result += (left_arr[left_index:])   # 把多余一边的元素给加到 result 列表中
    result += (right_arr[right_index:])
    return result

# 归并排序
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    merge_arr = merge(left_arr, right_arr)
    return merge_arr

调用归并排序:

nums = [1,3,2,4,7,5,6,8,10,9]
print(merge_sort(nums))

输出结果:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/916288.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号