文档章节

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

木头释然
 木头释然
发布于 07/16 08:38
字数 584
阅读 20
收藏 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
西青
其他
深扒 | 想从事人工智能的你必须知道…

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
AI概念上市公司近三成无起色 人工智能估值泡沫究竟有多大?

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

人工智能机器人联盟
01/05
0
0
别再提程序员应届年薪20万了,人工智能已经年薪60万了!

对人工智能而言,2017是不平凡的一年: AlphaGo再胜人类 腾讯宣布进军AI 百度无人驾驶汽车上五环 AI教育要从娃娃抓起 寒武纪成全球AI芯片首个独角兽 阿里巴巴成立达摩院 类人机器人Sophia首获...

ufv59to8
04/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

HTTPS is easy

HTTPS is easy https://www.troyhunt.com/https-is-easy/ HTTPS is easy! In fact, it's so easy I decided to create 4 short videos around 5 minutes each to show people how to enable ......

openthings
28分钟前
0
0
bugList 2

用户端: 1. 上传文件时,当选择:彩色-A3-双面时,第二个图片有bug 应改为 和第一个图片的类型相同 2. 确认打印时,三个下拉选目前有bug 应改为:根据后台配置的商家,group by计算出不同城...

勇恒
31分钟前
2
0
keras cnn 网咯 mnist 分类

搭建貌似比tf是简单很多。。。。。 from keras.datasets import mnistfrom keras.utils import np_utilsfrom keras.models import Sequentialfrom keras.layers import Dense, Activat......

阿豪boy
33分钟前
0
0
解决 /var/run/nginx.pid failed

nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory) sudo nginx -c /etc/nginx/nginx.conf nginx -s reload...

驛路梨花醉美
35分钟前
0
0
nginx负载均衡-ssl原理-生成ssl密钥对-nginx配置ssl

nginx负载均衡: 1.创建配置文件 vim /usr/local/nginx/conf/vhost/load.conf #添加以下内容: upstream qq_com #名字自定义,借助此模块定义多个IP,后面...

ZHENG-JY
35分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部