开发者社区> 白头雁> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

线性排序算法-归并排序(3)

简介: 分治是优化算法中的重要思想。 归并排序的主要技巧,如何处理两个分别已经排好序的数组? 采用额外空间O(n),交替遍历两个数组,时间复杂度为O(n) 将原数组不断向下拆分 举例说明,16个整形数组向下拆分 16-->(8,8)-->(4,4)-->(2...
+关注继续查看

分治是优化算法中的重要思想。

归并排序的主要技巧,如何处理两个分别已经排好序的数组?

采用额外空间O(n),交替遍历两个数组,时间复杂度为O(n)

将原数组不断向下拆分

举例说明,16个整形数组向下拆分
16-->(8,8)-->(4,4)-->(2,2)(2,2)(2,2)(2,2)->(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)

(1,1)采用归并,生成排好序的(2)
(2,2)采用归并,生成拍好序的(4)
(4,4)-->(8)
(8,8)-->16

    def __Merge(self,a,l,mid,r):
        #排序对象a[l,mid) [mid,r)
        b=[a[i] for i in range(l,r)]
        i = 0
        j = mid-l
        for k in range(l,r):
            if  i == mid-l:
                a[k] = b[j]
                j = j+1
            elif j == r-l :
                a[k] = b[i]
                i = i+1
            elif b[i] > b[j]:
                a[k] = b[j]
                j = j+1            
            else:
                a[k] = b[i]
                i = i+1

循环调用

    def MergeSort2(self,a):
        sz = 1
        total = len(a)
        while(sz< total):
            i = 0
            while(i<total-sz-1):
                self.__Merge(a,i,i+sz,min(i+sz+sz,total))
                i = i+sz+sz
            sz = sz+sz

递归调用

    def __MergeSort(self,a,l,r):
        #排序对象 a[l,r)        
        if (l+1) >= r:
            return        
        """
        ## 在小数组情况下,用插入排序,实验优化效果不好
        if (l+6)<=r:
            self.InsertionSortPart(a,l,r)
            return
        """
        mid = l+(r-l)//2
        self.__MergeSort(a,l,mid)
        self.__MergeSort(a,mid,r)
        self.__Merge(a,l,mid,r)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
线性排序算法-堆排序 (2)
堆是什么鬼? 在学数据结构的时候,链表、堆栈、树三种数据结构印象最深刻。当时理解有误区,堆栈被当成一种结构,可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。
668 0
线性排序算法(1)
排序 选择排序(适用于线性排序) 思路,2层遍历 第一步:选择最小的元素,与第一个元素交换。 第二步:从第二个元素到最后一个元素,选择最小元素,与第二元素交换 完成前两步,第1第2元素已经排好序。
682 0
排序算法(四):归并排序
归并排序是通过分治的方式,将待排序集合拆分为多个子集合,对子集合排序后,合并子集合成为较大的子集合,不断合并最终完成整个集合的排序。 以下所讲归并都是指二路归并: 之前的冒泡、选择和插入排序都是维持一个待排序集合和一个已排序集合,在每次的迭代过程中从待排序集合中移动一个元素到已排序集合中,通过不断的迭代来完成排序,所以需要进行的迭代次数一般都是 级别。
612 0
归并排序算法
算法导论第二章
0 0
【算法】归并排序
【算法】归并排序
0 0
排序算法:归并排序
这篇文章本该发表于2018年4月份末,在 排序算法:快速排序 之后,但是不知道什么原因,这篇文章忘了在CSDN上发表,今天在看博客的时候突然发现,因此补上。
0 0
排序算法---归并排序
排序算法---归并排序
0 0
归并排序算法模板
归并排序算法模板
0 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载