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


猜你喜欢
- 导语"? 花草树木 皆有呈名热爱自然,从认识自然开始 "现在的植物爱好者,遇到不认得的植物。怎么办呢?前几天去逛商场,一
- <?php header(“Content-Type:text/html;charset=utf-8″); if (isset($_G
- 一、前言作为一个数据库爱好者,自己动手写过简单的SQL解析器以及存储引擎,但感觉还是不够过瘾。<<事务处理-概念与技术>&
- 2020.2.20 更新日志:本文的初衷是因为安装anaconda的时候你并不知道会包含哪个版本的python,因此我制作了下表如果你使用的
- 本文为大家分享了vue $emit 和 $on 组件通信,供大家参考,具体内容如下<!DOCTYPE html> <htm
- 本文实例分析了GO语言文件的创建与打开用法。分享给大家供大家参考。具体分析如下:文件操作是个很重要的话题,使用也非常频繁,熟悉如何操作文件是
- 1.CNN概述CNN的整体思想,就是对图片进行下采样,让一个函数只学一个图的一部分,这样便得到少但是更有效的特征,最后通过全连接神经网络对结
- 本文实例讲述了python中的lambda表达式用法。分享给大家供大家参考,具体如下:这里来为大家介绍一下lambda函数。lambda 函
- 1、说明关键词传递以“形参变量名=实参”的形式参与实参关联,根据形参的名称进行参数传递,使实参和形参的顺序不一致。不用担心定义函数时参数的顺
- 如何完美的卸载掉Mysql?按以下几个步骤去执行。步骤一确认你的mysql服务是关闭的状态,不然卸载不干净。在我的电脑(计算机)-- 管理
- 支持CSS属性Safari和WebKit实施大子的CSS 2.1规格所界定的万维网联盟( W3C ) ,以及部分的CSS 3规格。 。这个C
- 1、performance schema:介绍 在MySQL5.7中,performance schema有很大改进
- 如何用ASP输出HTML文件?<!--#include file="top.inc"--><
- 签名import base64import jsonimport timefrom datetime import datetimeimpo
- 1.散点图代码# This import registers the 3D projection, but is otherwise unu
- 目录1.导入tf.keras2.构建简单模型2.1模型堆叠2.2网络配置3.训练和评估3.1设置训练流程3.2输入Numpy数据3.3tf.
- 字典概述字典是一个映射集合,他储存的是键值对,通过键来查找值,而不是索引字典定义通过大括号{}与键值对来表示一个字典 字典名=
- 简介scrapy-redis是一个基于redis的scrapy组件,用于快速实现scrapy项目的分布式部署和数据爬取,其运行原理如下图所示
- vue+element表格实现多层数据嵌套今天用element的表格渲染了商城的购物车列表,element的表格之前也用到过,它把所有的东西
- 一、用户相关SQL语句/*新建用户*/create user SA identified by 2013;说明:SA用户名,2013密码/*