python基本算法之实现归并排序(Merge sort)
作者:海歌同学 发布时间:2023-04-06 03:20:07
标签:python,归并,排序
0、前言
评判一个算法的好坏的标准:
时间复杂度
空间复杂度
1、归并排序算法是什么?
冒泡排序(Bubble Sort)是一种建立在归并操作上面的一种有效的排序算法,由John von neumann于1945年发明。采用分治法(Divide and Conquer)的经典应用!!将规模较大的排序问题化归到较小的规模上解决。
基本实现包含下面的两种方法:
自上而下的递归
自下而上的迭代
将已经有的有序子序列合并,得到完全有序的子序列。就是先得到每个子序列有序,然后在使得两个子序列合并成为一个有序的。如果是把两个有序表合并成为一个有序表,成为二路归并。
归并排序的性能不受到输入数据的影响,这一个和选择排序是一样的,但是性能比选择排序要好,性能始终是O(n log n)。但是性能的优越必定是额外的内存空间作为巨大代价的!
2、算法过程图解
3、代码实现
代码如下(示例01):
"""
Merge_Sort 归并排序
分治算法Divide and Conquer
时间复杂度:
"""
# 切割数组 的函数
def merge_sort(alist):
# 如果长度小于等于1 ,不能再分割了
if len(alist) <= 1:
return alist
# 根据列表长度确定拆分的中间位置
mid_index = len(alist)//2
# 使用切片实现对列表的切分
# left_list = alist[:mid_index]
# right_list = alist[mid_index:]
# 递归调用,无限切割下去
left_list = merge_sort(alist[:mid_index])
right_list = merge_sort(alist[mid_index:])
return merge(left_list, right_list)
# 排序的函数
def merge(left_list, right_list):
l_index,r_index = 0,0
merge_list = []
# 判断列表里面是否还有元素可以用
while l_index < len(left_list) and r_index < len(right_list):
# 哪边的元素小于另外一边的的元素就把哪边的元素加入进去,对应的索引加一
if left_list[l_index] < right_list[r_index]:
merge_list.append(left_list[l_index])
l_index += 1
else:
merge_list.append(right_list[r_index])
r_index += 1
# 下面的这两个就是,如果有一个列表全部添加了,另外一个列表直接添加到merge_list里面了
merge_list += left_list[l_index:]
merge_list += right_list[r_index:]
return merge_list
if __name__ == '__main__':
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(f'原列表的顺序:{alist}')
alist = merge_sort(alist)
print(f'选择排序之后的列表的顺序:{alist}')
里面的左右列表都是被划分到了只有一个元素的是去比较和添加的。大家可以把代码放置到编译器里面,debug运行,看一哈具体的过程,结合动态图片演示理解更好!
4、评判算法
最好时间复杂度:O(n log n)
最坏时间复杂度:O(n log n)
平均时间复杂度:O(n log n)
空间复杂度:O(n)
算法稳定性:稳定的排序
来源:https://blog.csdn.net/weixin_44824717/article/details/108329385
0
投稿
猜你喜欢
- 大家有没有这种感觉,一到国庆、春节这种长假,抢火车票就非常困难?各大互联网公司都推出抢票服务,只要加钱给服务费就可以增加抢到票的几率。有些火
- 概述OpenCV 是一个跨平台的计算机视觉库, 支持多语言, 功能强大. 今天小白就带大家一起携手走进 OpenCV 的世界.梯度运算梯度:
- 语法在python3中,内置函数中已经没有reduce了。要使用reduce,需要从functools模块里引入可以看到,reduce有三个
- 1. zip() 函数的介绍1.1 功能zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组
- 1 configparser安装pip3 install configparser2 configparser简介用来读取配置文件的pyth
- 概要:Oracle关系数据库系统以其卓越的性能获得了广泛的应用,而保证数据库的安全性是数据库管理工作的重要内容。本文是笔者在总结Oracle
- 今天一个朋友给个需求: 来来 {'isOK': 1, 'isRunning': None, 'isE
- 概述在view函数中,如果需要中断request,可以使用abort(500)或者直接raise exception。当然我们还需要返回一个
- Click 是用 Python 写的一个第三方模块,用于快速创建命令行。我们知道,Python 内置了一个 Argparse 的标准库用于创
- AddHeaderAddHeader 方法用指定的值添加 HTML 标题。该方法常常向响应添加新的 HTTP 标题。它并不替代现有的同名标题
- 无法打开用户默认数据库,登录失败,这也是SQL Server使用者熟悉的问题之一。在使用企业管理器、查询分析器、各类工具和应用软件的时候,只
- 在应用系统开发初期,由于开发数据库数据比较少,对于查询SQL语句,复杂视图的编写,刚开始不会体会出SQL语句各种写法的性能优劣,但是如果将应
- 在代码中添加以下两行可以解决:torch.backends.cudnn.enabled = Truetorch.backends.cudnn
- 前言:本文为 HITwh 网络空间安全专业网络空间安全设计与实践 I 的选题之一,主要实现了远程监控局域网内的主机桌面与网络情况、简单键鼠控
- 如何正确显示数据库里同时存在的GB码和BIG5码? Public Function CheckBIG(strS
- 简介模拟登录淘宝已经不是一件新鲜的事情了,过去我曾经使用get/post方式进行爬虫,同时也加入IP代理池进行跳过检验,但随着大型网站的升级
- 要求,输入一串数字,并以列表的形式打印出来。number = input('请输入一串数字:') print(number)
- python给数据加上高斯噪声一开始用MATLAB给数据加噪声很简单,就一句话:% 给数据加指定SNR的高斯噪声signal_noise =
- 1 Support Vector Machines1.1 Example Dataset 1%matplotlib inlineimport
- 相关的题外话:一、操作系统window系统内部都是unicode的。文件夹名,文件名等都是unicode的,任何语言系统下都能正常显示。二、