重庆专业的网站建设,辽阳建设银行网站,怎么做子网站,网站设计是什么意思0、前言
评判一个算法的好坏的标准#xff1a;
时间复杂度
空间复杂度
1、归并排序算法是什么#xff1f;
冒泡排序(Bubble Sort)是一种建立在归并操作上面的一种有效的排序算法#xff0c;由John von neumann于1945年发明。采用分治法#xff08;Divide and Conquer#…0、前言
评判一个算法的好坏的标准
时间复杂度
空间复杂度
1、归并排序算法是什么
冒泡排序(Bubble Sort)是一种建立在归并操作上面的一种有效的排序算法由John von neumann于1945年发明。采用分治法Divide and Conquer的经典应用将规模较大的排序问题化归到较小的规模上解决。
基本实现包含下面的两种方法
自上而下的递归
自下而上的迭代
将已经有的有序子序列合并得到完全有序的子序列。就是先得到每个子序列有序然后在使得两个子序列合并成为一个有序的。如果是把两个有序表合并成为一个有序表成为二路归并。
归并排序的性能不受到输入数据的影响这一个和选择排序是一样的但是性能比选择排序要好性能始终是O(n log n。但是性能的优越必定是额外的内存空间作为巨大代价的
2、算法过程图解3、代码实现
代码如下示例01Merge_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)
算法稳定性稳定的排序
总结
到此这篇关于python基本算法之实现归并排序(Merge sort)的文章就介绍到这了,更多相关python归并排序(Merge sort)内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们
本文标题: python基本算法之实现归并排序(Merge sort)
本文地址: http://www.cppcns.com/jiaoben/python/340861.html
