线性排序算法-归并排序(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)
目录
相关文章
|
26天前
|
算法 C# 索引
C#线性查找算法
C#线性查找算法!
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
27 1
|
3月前
|
机器学习/深度学习 算法 Java
[算法与数据结构] 谈谈线性查找法~
该文章详细介绍了线性查找法的基本概念与实现方法,通过Java代码示例解释了如何在一个数组中查找特定元素,并分析了该算法的时间复杂度。
|
2月前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
2月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
76 0
|
2月前
|
人工智能 算法 BI
【算法】 线性DP(C/C++)
【算法】 线性DP(C/C++)
|
2月前
|
搜索推荐 Java Go
深入了解归并排序算法
深入了解归并排序算法
26 0
|
4月前
|
算法 搜索推荐 Java
算法实战:手写归并排序,让复杂排序变简单!
归并排序是一种基于“分治法”的经典算法,通过递归分割和合并数组,实现O(n log n)的高效排序。本文将通过Java手写代码,详细讲解归并排序的原理及实现,帮助你快速掌握这一实用算法。
45 0
|
4月前
|
算法 5G vr&ar
基于1bitDAC的MU-MIMO的非线性预编码算法matlab性能仿真
在现代无线通信中,1-bit DAC的非线性预编码技术应用于MU-MIMO系统,旨在降低成本与能耗。本文采用MATLAB 2022a版本,深入探讨此技术,并通过算法运行效果图展示性能。核心代码支持中文注释与操作指导。理论部分包括信号量化、符号最大化准则,并对比ZF、WF、MRT及ADMM等算法,揭示了在1-bit量化条件下如何优化预编码以提升系统性能。
|
4月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
47 0