python排序算法之归并排序
作者:i阿极 发布时间:2021-03-24 06:05:39
一、前言
相关知识来自《python算法设计与分析》。初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序3种。相比起初级排序算法,高级排序算法往往有更加复杂的逻辑,但也会有更高的时间或空间效率。其中有些高级排序算法是由一些初级排序算法优化而来的。
二、算法描述
本节中的第一种高级排序算法是归并排序。“归并”一词,意为“合并”。顾名思义,归并排序算法就是一个先把数列拆分为子数列,对子数列进行排序后,再把有序的子数列合并为完整的有序数列的算法。它实际上采用了分治的思想。
归并排序的平均时间复杂度是O(nlgn),最好情况下的时间复杂度是O(nlgn),最坏情况下的时间复杂度也是O(nlgn)。它的空间复杂度是O(1)。另外,归并排序还是一个稳定的排序算法。
以升序排序为例,归并算法的流程如图2-21所示。
原始数组是一个有8个数的无序数组。一次操作后,把8个数的数组分成两个4个数组成的无序数组。接下来的每次操作都是把无序数组不停分成两半,直到每个最小的数组里都只有一个元素为止。当数组里只有一个元素时,这个数组必定是有序的。然后,程序开始把小的有序数组每两个合并成为大的有序数组。先是从两个1个数的数组合并成2个数的数组,再到4个数然后8个数。这时,所有的有序数组全部合并完成,最后产生的最长的有序数组就排序完成了。
三、代码实现
归并排序代码:
#归并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
if(len(num)<=1):#递归边界条件
return num#到达边界时返回当前的子数组
mid = int(len(num)/2) #求出数组的中位数
llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#调用函数分别为左右数组排序
result = []
i,j = 0,0
while i < len(llist) and j < len(rlist): #while循环用于合并两个有序数组
if rlist[j]<llist[i]:
result.append(rlist[j])
j += 1
else:
result.append(llist[i])
i += 1
result += llist[i:]+rlist[j:] #把数组未添加的部分加到结果数组末尾
return result#返回已排序的数组
print(MergeSort(nums))
运行程序,输出结果为:
[1,2,3,4,5,6,7,8]
在MergeSort()函数中,首先进行的是边界条件判断。当传入函数的数组长度只有1时,每一个数独立存在于一个数组中,因此数组已经被分到最小。这时候,递归分解数组的任务已经完成,只需要把分解后的数组返回到上一层递归就可以了。
如果未排序数组的长度仍然大于1,那么使用变量mid来存储数组最中间的下标,把未排序数组分成左右两个子数组。然后,新建两个数组,用于存储排好序的左右子数组。这里使用了递归的思想。我们只把MergeSort()函数视为一个为列表排序的函数,尽管在MergeSort()函数内部,也可以调用函数本身对两个子数组进行排序。
随后,使用while循环合并两个已经有序的数组。由于不能确定两个数组中元素的相对大小,所以我们采用i和j两个变量分别标记在左子数组和右子数组中等待加入的元素的位置。当while循环结束时,可能一个子数组的末尾还剩余一些最大的元素没有被添加到result列表中,所以result+=llist[i:]+rlist[j:]语句是为了防止漏掉这些元素。数组合并完成后,函数输出有序数组。
来源:https://blog.csdn.net/AOAIYI/article/details/128657679
猜你喜欢
- myisam_max_[extra]_sort_file_size足够大delay_key_write减少io,提高写入性能bulk_ins
- 各大云计算提供商(亚马逊、谷歌和微软)目前都使用了键/值存储方式。然而,在San Francisco召开的MSDN开发者大会上,微软宣布他们
- PDO::inTransactionPDO::inTransaction — 检查是否在一个事务内(PHP 5 >= 5.3.3, B
- fsockopen函数能够运用,首先要开启php.ini中的allow_url_open=on;fsockopen是对socket客户端代码
- 这个效果本身难度不大,主要在程序结构和扩展中下了些功夫,务求用起来更方便,能用在更多的地方。程序特点 1,同一个提示框用在多个触发元素时,只
- 线程Threading用于提供线程相关的操作。线程是应用程序中工作的最小单元,它被包含在进程之中,是进程中的实际运作单位。一条线程指的是进程
- 在这个教材中,我们假定你已经安装了Scrapy。假如你没有安装,你可以参考这个安装指南。我们将会用开放目录项目(dmoz)作为我
- 需要在两个文件中实现:首先,在talker.asp(在线名单)中做如下处理:<%p1=trim(application("v
- 总结了部分所学、所听、所看、所问的一些CSS写作经验,书写高效的CSS - 漫谈CSS的渲染效率,它们与渲染效率及所占用
- 代码如下:--相信大家肯定经常会把数据导入到数据库中,但是可能会有些记录行的所有列的数据是null,这为null的数据是我们不需要 --现在
- 目录1.事件循环2.协程和异步编程2.1 基本使用2.2 await2.3 Task对象1.事件循环可以理解成为一个死循环,去检查任务列表中
- 打开php.ini,首先找到file_uploads = on ;是否允许通过HTTP上传文件的开关。默认为ON即是开upload_tmp_
- PNG格式以支持透明和无损,且相对大小适中,已成为现在网页中图片运用的主流。有些时候我们在制作网页时使用PNG格式图片,用IE浏览器查看却无
- 以前写过一个标签效果,外观虽然好看,但代码不太规范,实现的方法比较繁冗。需要注意的是标签的背景图,两种状态,激活的标签背景为蓝色,反之为灰色
- 本文实例讲述了PHP实现ASCII码与字符串相互转换的方法。分享给大家供大家参考,具体如下:<?phpclass ascii { &n
- 前一段时间,一个流行的东方系列mv 《bad apple》 带来一股奇怪的风潮: 各种技术狂人纷纷把这段mv在一些匪夷
- 概要本文分步介绍了如何在运行 SQL Server 的计算机之间移动 Microsoft SQL Server 用户数据库和大多数常见的 S
- MongoDB安装模块pip install pymongo连接数据库import pymongoclient = pymongo.Mong
- 框架概念框架和web服务器关系·静态资源:不是经常变化的资源、往往是固定不变的资源·动态资源:经常变化的资源·模板文件:提供了一个显示的模板
- 相信没有人不知道 Firebug 是什么东西,但有时候我们糟糕的代码不想让同行轻松的使用 F12 就能一览无遗。那么怎么办呢?这里有个猥琐的