算法——排序——归并排序

╰半夏微凉° 2022-07-27 10:56 244阅读 0赞

</pre>描述：<p></p><p><span style="white-space:pre"></span>1.先将它分成两半，分别排序，然后将结果归并</p><p><span style="white-space:pre"></span>2.O(nlogn)(最好与最坏都一样)</p><p><span style="white-space:pre"></span>3.稳定的排序</p><p>Code:</p><p>自顶向下（体现分治法的思想）</p><p></p><pre code_snippet_id="1643953" snippet_file_name="blog_20160412_2_2719246" name="code" class="python">class Sort:
        arrTemp = None
    
        @classmethod
        def sort(cls,arr):
            arrTemp = [0 for i in range(0, len(arr))]
            cls.sortMerge(arr, 0, len(arr) - 1)
    
        @classmethod
        def sortMerge(cls, arr, lo, hi):
            if hi <= lo :
                return
            mid = lo + (hi - lo)/2
            cls.sortMerge(arr, lo, mid)
            cls.sortMerge(arr, mid + 1, hi)
            cls.merge(arr, lo, mid, hi)
    
        @classmethod
        def merge(cls, arr, lo, mid, hi):
            i = lo
            j = mid + 1
            arrTemp = arr[:]
            k = lo
            while k <= hi:
                if arrTemp[j] < arrTemp[i]:
                    arr[k] = arrTemp[j]
                    j += 1
                    k += 1
                else:
                    arr[k] = arrTemp[i]
                    i += 1
                    k += 1
                while i > mid and k <= hi:
                    arr[k] = arrTemp[j]
                    k += 1
                    j += 1
                while j > hi and k <= hi:
                    arr[k] = arrTemp[i]
                    i += 1
                    k += 1

自底向上（适合于链表）

class Sort:
        arrTemp = None
    
        @classmethod
        def sort(cls, arr):
            n = len(arr)
            arrTemp = [0 for i in range(0, n)]
            size = 1
            while size < n:
                lo = 0
                while lo < n - size:
                    cls.merge(arr, lo, lo+size - 1, min(lo+size+size-1, n - 1))
                    lo += size + size
    
                size = size + size
            return
    
        @classmethod
        def merge(cls, arr, lo, mid, hi):
            i = lo
            j = mid + 1
            arrTemp = arr[:]
            k = lo
            while k <= hi:
                if arrTemp[j] < arrTemp[i]:
                    arr[k] = arrTemp[j]
                    j += 1
                    k += 1
                else:
                    arr[k] = arrTemp[i]
                    i += 1
                    k += 1
                while i > mid and k <= hi:
                    arr[k] = arrTemp[j]
                    k += 1
                    j += 1
                while j > hi and k <= hi:
                    arr[k] = arrTemp[i]
                    i += 1
                    k += 1

发表评论取消回复

表情：

评论列表（有 0 条评论，244人围观）

还没有评论，来说两句吧...

相关阅读

相关【排序算法】- 归并排序

文章目录 1 归并排序介绍: 2 归并排序思想示意图1-基本思想: 3 归并排序思想示意图2-合并相邻有序子序列: 4 归并排序的应用实例:

系统管理员/ 2022年12月20日 06:12/ 0 赞/ 38 阅读

相关排序算法——归并排序

排序算法——归并排序 > 归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每

客官°小女子只卖身不卖艺/ 2022年12月19日 06:06/ 0 赞/ 44 阅读

相关排序算法——归并排序

引言归并排序可以使用递归或迭代的方式来实现，时间复杂度是都是 O(N \ logN)。归并排序的核心是将待排序数组分组，可以整体二分，也可以设置步长迭代切分。归并排

小鱼儿/ 2022年11月18日 01:41/ 0 赞/ 256 阅读

相关排序算法-归并排序

归并排序也是一个比较快速的排序算法，其思想是运用分治的思想，先对要排序的数进行分，每次从中间分成两部分，然后知道分成最小，然后在把他们合起来，边合起来边排序，最后有序，每次分的

妖狐艹你老母/ 2022年08月01日 03:14/ 0 赞/ 280 阅读

相关排序算法——归并排序

前言将待排序序列R\[0...n-1\]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4

亦凉/ 2022年06月12日 00:49/ 0 赞/ 283 阅读

相关【算法】排序算法——归并排序

【[fishing-pan][]：[https://blog.csdn.net/u013921430][https_blog.csdn.net_u013921430]

╰+哭是因爲堅強的太久メ/ 2022年05月25日 06:09/ 0 赞/ 440 阅读

相关排序算法——归并排序

原文写的很好，很好，转载下。转载：[https://blog.csdn.net/morewindows/article/details/6678165/][https_bl

野性酷女/ 2022年05月07日 18:40/ 0 赞/ 267 阅读

相关排序算法——归并排序

原文写的很好，很好，转载下。转载：[https://blog.csdn.net/morewindows/article/details/6678165/][https_bl

古城微笑少年丶/ 2022年05月07日 04:53/ 0 赞/ 309 阅读

相关排序算法：归并排序

一、前言归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 --------

清疚/ 2022年04月04日 15:09/ 0 赞/ 412 阅读

相关排序算法--------归并排序

归并排序 1.简介 2.图解 3.算法思想 4.Java递归实现 5.算法分析： 6.总结 7.归并排序优化 1.简介

逃离我推掉我的手/ 2022年03月20日 15:54/ 0 赞/ 358 阅读