学习算法-合并排序

作者 : IT 大叔 本文共1929个字,预计阅读时间需要5分钟 发布时间: 2020-10-9

以前,我们看过并实现了插入排序

但是,它的最坏情况是O(n²),这真的很慢,不是吗?我答应过您要使用更复杂,更快速的算法来对称为“合并排序数组进行排序

分而治之

那么当涉及到元素列表时,如何节省时间进行排序呢?答案是分而治之。我假设您现在必须已经了解二进制搜索,在这里您已经开始学习算法,或者可以回过头来学习二进制搜索。让我为您提供整个计划的全景。首先,我们将有大小的数组ñ,我们将它称为一个。其次,我们将分成两半(直到不可分割),这将是两个数组Left和Right。接下来,将对两个数组进行排序。最后,我们将按排序顺序它们合并回数组A中

学习算法-合并排序插图

递归

不幸的是,要使用Merge Sort,我们需要知道这个众所周知的令人困惑的概念,即所谓的递归。简而言之,递归是一个调用自身的函数。让我们看一下下面的代码。

def call_me(arg):
    call_me(arg)
    print(arg)
call_me("I am calling me")

学习算法-合并排序插图(2)
函数call_me(arg)调用自身,然后输出arg。在这种情况下会发生什么?它会称自己像一个黑洞一样无限地打印“我在呼唤我”。这将导致错误的恶名,堆栈溢出,实际上是函数调用被堆栈起来,而程序用完了存储这些调用的内存空间,因此引发了错误。因此,我们需要做的就是让递归在某个时刻结束,为此,我们需要一个条件来结束递归,我们将其称为基本案例。 让我以一个基本案例停止这种递归。call_me函数使用另一个参数i,每次执行时将其加1,如果i变为5,则将返回该函数。
学习算法-合并排序插图(4)

def call_me(arg, i):
    if i == 5:  # if i == 5, return
        return

    i += 1
    call_me(arg, i)  # otherwise keep executing with incremented i
    print(arg)
call_me("I am calling me", 0)

学习算法-合并排序插图(6)

合并排序

复制数组A的一半

我认为我们现在已经准备好破解。我们具有以下未排序的数组A。

A = [4, 7, 20, 3, 9, 13, 5, 11]

正如我在计划阶段前面提到的那样,我们将分别复制左半部分(L)和右半部分(R)的数组。

def merge_sort(A):
    mid = len(A) // 2
    # copy slicing from the 0 to mid from array A
    L = A[:mid]
    # copy slicing from mid to the end from array A
    R = A[mid:] 

学习算法-合并排序插图(8)
我们将递归地将数组减半,直到不可分割。如前所述,我们需要一个基本情况来停止递归,直到没有任何排序且数组是不可分割的,直到数组A的长度变为1

 def merge_sort(A):
    if len(A) > 1:
        ... previous code
        # recursively halve arrays
        merge_sort(L)
        merge_sort(R)

        # indices for array A, L, R 
        # for short term, i = j = k = 0 works as well.
        i = 0
        j = 0
        k = 0

学习算法-合并排序插图(10)
由于上面的代码,数组将如下所示。请注意,减半过程的每个级别同时发生,因此在这种情况下,我们采取了4个步骤将数组长度减半为8。

合并和排序

现在,是时候合并并排序回数组A,对元素进行排序了,我们需要比较哪个应该首先出现。第一个是较小的,然后是较大的。合并和排序的实现将像这样,一旦将元素放回数组A中,索引将移至下一个元素。

# while indices are within a range of array L and R
# note that indices i for L, j for R, k for A
while i < len(L) and j < len(R):
    if L[i] < R[j]:
        A[k] = L[i]
        i += 1
    else:
        A[k] = R[j]
        j += 1
    k += 1

剩下的最后一件事是,插入一个尚未从L或R移动到数组A的元素。当L和R的长度不同时,换句话说,当A的长度为像7的奇数

... previous code
while i < len(L):
    A[k] = L[i]
    i += 1
    k += 1
while j < len(R):
    A[k] = R[j]
    j += 1
    k += 1

合并过程如下所示。
学习算法-合并排序插图(12)

时空复杂度分析

合并排序的时间复杂度

看来,该算法的时间复杂度为O(n log n),原因是分而治之(相减的数组)。但是合并和排序阶段呢?它遍历每个数组进行排序和合并,即O(n)。当存在最坏情况时,其他情况都无关紧要,因此时间复杂度为O(n)

合并排序的空间复杂度

合并排序使用多少个内存空间?很多!它会复制数组的每一半,这意味着多余的空间,具体取决于元素的数量。因此,合并排序的空间复杂度为O(n)。与插入排序相比,它将是合并排序O(n)>插入排序O(1)。
到最后已经很漫长的旅程,希望您现在对这个概念有一个很好的了解。

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 学习算法-合并排序

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论