Python 中的合并排序

Vaibhhav Khetarpal 2023年1月30日 2022年5月17日
  1. 在 Python 中使用递归实现归并排序
  2. 在 Python 中使用迭代合并排序
Python 中的合并排序

合并排序是一种流行的排序算法,用于对任何给定数据结构的元素进行排序。本教程讨论了归并排序算法以及如何在 Python 中实现它。

合并排序是分治法的一个主要例子,用于对大型数据集进行排序。该算法首先将给定的数据结构分成两部分,然后在两半上重复相同的过程。最后,它将两半重新组合在一起以有效地获得排序值。因此,我们称其为分而治之方法的主要例子。

这个算法最好的部分是它在所有三种可能的情况下(平均情况、最佳情况和最坏情况)都具有一致的时间复杂度 O(nlogn)。由于这个事实,它通常被认为是有效的,并且是大型数据集的首选。

我们现在将看到如何使用 Python 编程语言实现归并排序算法。

在 Python 中使用递归实现归并排序

归并排序是在 Python 中借助递归函数简单实现的。

以下代码使用递归在 Python 中实现归并排序。

def m(left, right):
    if not len(left) or not len(right):
        return left or right
 
    result = []
    i, j = 0, 0
    while (len(result) < len(left) + len(right)):
        if left[i] < right[j]:
            result.append(left[i])
            i+= 1
        else:
            result.append(right[j])
            j+= 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break
 
    return result
 
def msort(list):
    if len(list) < 2:
        return list
 
    middle = int(len(list)/2)
    left = msort(list[:middle])
    right = msort(list[middle:])
 
    return m(left, right)
     
lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst);
print("\n")
print("Sorted List:")
print(msort(lst))

上面的代码提供了以下输出:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

代码说明:

  • 只要没有获得两个相邻的值,在每次递归调用中,给定的列表都会分成两半,
  • 创建并使用 m() 函数来合并最初在第一步中划分的两半。
  • msort() 函数执行程序中给定列表的大部分划分和排序部分。

在 Python 中使用迭代合并排序

迭代归并排序算法与一般的递归方法略有不同,前者使用自下而上的方法,而后者使用自上而下的方法。但是,两种方法的时间复杂度和最终答案完全相同。

此外,递归归并排序方法使用显式辅助堆栈,而在迭代归并排序算法实现中则不需要它。

以下代码使用迭代归并排序算法在 Python 中实现归并排序。

def msort(a):
    width = 1   
    n = len(a)                                         
    while (width < n):
        l=0;
        while (l < n):
            r = min(l+(width*2-1), n-1)
            m = (l+r)//2
            if (width>n//2):       
                m = r-(n%width)  
            mer(a, l, m, r)
            l += width*2
        width *= 2
    return a

def mer(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]
 
    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1
 
    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1
 
    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1

a = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(a)
msort(a)
print("Sorted List:")
print(a)

上面的代码提供了以下输出:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

归并排序的缺点

尽管归并排序真的很流行并且被认为是高效的,但它在各种情况下都有一些缺点,下面会提到。

  • 在处理较小的数据结构集时,它可能比其他可用的排序算法相对慢。
  • 实现此算法需要额外的内存空间。
  • 该算法将始终贯穿整个过程,即使给定的数据结构已经排序。
Vaibhhav Khetarpal avatar Vaibhhav Khetarpal avatar

Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.

LinkedIn

相关文章 - Python Sorting