文档章节

人工智能你必须掌握的32个算法(二)归并排序算法

木头释然
 木头释然
发布于 07/16 08:38
字数 584
阅读 33
收藏 0

    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

    归并排序通过将已有序的子序列合并,得到完全有序的序列。那么我们如何将一个无序的序列拆分成有序子序列呢?

    归并排序的核心是分治,对于一个无序序列A,假设将序列A拆分成两个序列A1、A2,我们无法保证A1、A2有序,然后我们继续将A1、A2序列继续分解成A11、A12、A21、A22,直至每个序列中只有一个元素,如此即可保证每个子序列有序了。该步骤即“”。

    

     好了,我们已经得到N个(数据长度个)有序子序列了,下面该进行到“”的步骤了。对于每两个有序子序列,我们将起两两合并。

    对于任意两个需要合并的子序列,将先用每个序列第一个元素进行比较,将较小元素放入新序列,然后将已放入新序列的子序列第二个元素和另一个序列第一个元素进行比较,直至两个序列所有数全部加入新序列为止。

代码实现:

def sort(oldArray):
    if len(oldArray) == 1:
        return oldArray
    midd = len(oldArray)//2
    oldArray1 = sort(oldArray[:midd])
    oldArray2 = sort(oldArray[midd:])
    return merge(oldArray1, oldArray2)


def merge(oldArray1, oldArray2):
    newArray = []
    i = 0
    j = 0
    while i < len(oldArray1) and j < len(oldArray2):
        if oldArray1[i] <= oldArray2[j]:
            newArray.append(oldArray1[i])
            i += 1
        else:
            newArray.append(oldArray2[j])
            j += 1
    newArray += oldArray1[i:]  # 将两个数组剩余元素加入新数组
    newArray += oldArray2[j:]
    return newArray

print(sort([12, 67, 5, 62, 94, 22, 56]))

 

© 著作权归作者所有

共有 人打赏支持
木头释然
粉丝 17
博文 9
码字总数 5035
作品 0
西青
其他
深扒 | 想从事人工智能的你必须知道…

2016年是中国人工智能元年。2017年7月,国务院发布《新一代人工智能发展规划》, 2018年3月,人工智能再次被写进政府工作报告,国务院总理李克强在报告中提出,要加强新一代人工智能研发应用...

菜鸟学python
06/25
0
0
应届生都年薪30w了,做AI工程师到底有哪些要求?

行业背景和就业前景我就不再赘述了, 什么AI算法工程师年薪百万,应届毕业生年薪都有30w... 什么2017年AI人才缺口就已经过百万,今年将达500w... 什么AI企业从巨头到start-up投资都拿到手软....

b6ecl1k7bs8o
05/10
0
0
阿里云大学云学院 “人工智能” 专业重磅预售

阿里云认证专家带你探索人工智能,掌握人工智能核心技术 学习链接:点击这里 (阿里云认证资深专家,手把手带你6个月入门人工智能) 阿里云云学院人工智能专业,由阿里云认证专家亲自辅导,并...

mcy0425
06/27
0
0
论答CEO王枫:AI教育系统已经像阿尔法狗一样强大

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/McIl9G4065Q/article/details/82321982 关注网易智能,聚焦AI大事件,读懂下一个大时代! 出品 | 网易智能(公...

网易智能
08/31
0
0
AI概念上市公司近三成无起色 人工智能估值泡沫究竟有多大?

  人工智能是近两年最大热点之一,AI项目花开遍地,但凡大牛领军团队,估值都相当可观。用一位投资人的话讲,“基本上第一轮不下手,第二轮就投不起了。”   据不完全统计,A股目前有49家...

人工智能机器人联盟
01/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

谈谈如何学Linux和它在如今社会的影响

昨天,还在农耕脑力社会,今天已经人工智能技术、大数据、信息技术的科技社会了,高速开展并迅速浸透到当今科技社会的各个方面,Linux日益成为人们信息时代的到来,更加考验我们对信息的处理程...

linuxCool
29分钟前
1
0
SpringBoot内置定时任务

springBoot内置定时任务 应用场景 业务监控,定时发送邮件,定时删除缓存等等。 Spring Boot 内置定时 pom 包配置 <dependencies> <dependency> <groupId>org.springframework.b......

Grittan
34分钟前
14
1
在 Linux 中基于密钥认证的 SSH的配置方法

什么是基于 SSH 密钥的认证? 众所周知,Secure Shell,又称 SSH,是允许你通过无安全网络(例如 Internet)和远程系统之间安全访问/通信的加密网络协议。无论何时使用 SSH 在无安全网络上发...

linuxprobe16
51分钟前
1
0
sed命令

10月17日任务 9.4/9.5 sed 1.sed(上)(下) 1.sed 匹配功能 #sed -n ‘/root/’ p test.txt 将带有root的内容打印出来 同时支持 . * 还有 + 不过需要脱译,或者在前面选项加r。 支持{ } 支...

hhpuppy
今天
1
0
day120-20181018-英语流利阅读-待学习

千禧一代注意了:一大波公司正向你的钱包袭来 Daniel 2018-10-18 1.今日导读 这几年,你有没有发现,不管是在微信公众号还是在抖音,有越来越多的商家和品牌开始玩起了网络用语和表情包,从卖...

飞鱼说编程
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部