文档章节

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

木头释然
 木头释然
发布于 07/16 08:38
字数 584
阅读 51
收藏 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]))

 

© 著作权归作者所有

共有 人打赏支持
木头释然
粉丝 16
博文 9
码字总数 5035
作品 0
西青
其他
私信 提问
应届生都年薪30w了,做AI工程师到底有哪些要求?

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

b6ecl1k7bs8o
05/10
0
0
深扒 | 想从事人工智能的你必须知道…

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

菜鸟学python
06/25
0
0
阿里云大学云学院 “人工智能” 专业重磅预售

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

mcy0425
06/27
0
0
算法工程师成长计划

算法工程师成长计划 近年来,算法行业异常火爆,算法工程师年薪一般20万~100 万。越来越多的人学习算法,甚至很多非专业的人也参加培训或者自学,想转到算法行业。尽管如此,算法工程师仍然...

rainchxy
2017/10/23
0
0
算法与数据结构(一):导论篇-算法的重要性

算法与数据结构 算法相当的重要 & 算法无处不在 思考:编译器是如何理解你所写的程序的。 编译器的存在涉及着各种算法。搜索引擎:搜索算法加排序算法 遍历1亿的数据。Google定位信息。 推荐...

天涯明月笙
2017/09/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

EOS docker开发环境

使用eos docker镜像是部署本地EOS开发环境的最轻松愉快的方法。使用官方提供的eos docker镜像,你可以快速建立一个eos开发环境,可以迅速启动开发节点和钱包服务器、创建账户、编写智能合约....

汇智网教程
今天
15
0
《唐史原来超有趣》的读后感优秀范文3700字

《唐史原来超有趣》的读后感优秀范文3700字: 作者:花若离。我今天分享的内容《唐史原来超有趣》这本书的读后感,我将这本书看了一遍之后就束之高阁了,不过里面的内容一直在在脑海中回放,...

原创小博客
今天
19
0
IC-CAD Methodology知识图谱

CAD (Computer Aided Design),计算机辅助设计,指利用计算机及其图形设备帮助设计人员进行设计工作,这个定义同样可以用来近似描述IC公司CAD工程师这个岗位的工作。 早期IC公司的CAD岗位最初...

李艳青1987
今天
21
0
CompletableFuture get方法一直阻塞或抛出TimeoutException

问题描述 最近刚刚上线的服务突然抛出大量的TimeoutException,查询后发现是使用了CompletableFuture,并且在执行future.get(5, TimeUnit.SECONDS);时抛出了TimeoutException异常,导致接口响...

xiaolyuh
今天
11
0
dubbo 搭建与使用

官网:http://dubbo.apache.org/en-us/ 一,安装监控中心(可以不安装) admin管理控制台,monitor监控中心 下载 bubbo ops 这个是新版的,需要node.js环境,我没有就用老版的了...

小兵胖胖
今天
22
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部