Mergesort 实现出错

Question

输出不符合预期

import random

def mergeSort(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)
            merge(a, l, m, r)
            l += width * 2

        width *= 2
    return a


def merge(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 = 0
    j = 0
    k = 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


def create_random_list(n):
    L = []
    for _ in range(n):
        L.append(random.randint(1,n))
    return L

a = create_random_list(100)
print("Given array is ")
print(a)

mergeSort(a)

print("Sorted array is ")
print(a)```

output

给定的数组是 [54, 17, 12, 61, 54, 13, 42, 82, 14, 65, 72, 11, 38, 76, 75, 56, 30, 1, 48, 52, 49, 88, 62, 94, 37 , 98, 99, 79, 2, 77, 16, 67, 94, 14, 11, 24, 25, 20, 55, 92, 83, 85, 99, 50, 93, 49, 91, 73, 24, 84 , 68, 21, 100, 4, 54, 65, 43, 74, 43, 60, 9, 27, 68, 15, 71, 39, 19, 69, 87, 56, 63, 56, 56, 70, 1 , 51, 4, 87, 84, 7, 92, 30, 97, 74, 34, 45, 89, 33, 13, 41, 14, 92, 46, 8, 28, 72, 72, 37, 34, 64 ]

排序数组为 [1, 1, 2, 4, 4, 7, 8, 9, 11, 11, 12, 13, 13, 14, 14, 14, 15, 16, 17, 19, 20, 21, 24, 24, 25 , 27, 28, 30, 30, 33, 34, 37, 38, 39, 41, 42, 43, 43, 45, 46, 48, 49, 49, 50, 51, 52, 54, 54, 54, 55 , 56, 56, 56, 56, 60, 61, 62, 63, 65, 65, 67, 68, 68, 69, 70, 71, 72, 72, 73, 74, 74, 75, 76, 77, 79 , 82, 83, 84, 84, 85, 87, 87, 88, 89, 91, 92, 92, 92, 93, 94, 94, 97, 34, 37, 64, 72, 98, 99, 99, 100 ]

Answer 1

你的代码太复杂了。简化方法如下：

merge 函数的参数应该是 l，第一个切片开始的索引，m 第二个切片的索引，r超过第二个切片末尾的索引。
这样切片宽度更容易计算。
提取要合并的切片变得微不足道
并且确定数组的哪一部分调用 merge 也更简单：l 将是 width 的偶数倍，下一个 m奇数倍数。

这是修改后的版本：

import random

def mergeSort(a):

    width = 1
    n = len(a)

    while (width < n):
        l = 0
        while (l + width < n):
            r = min(l + width * 2, n)
            merge(a, l, l + width, r)
            l += width * 2

        width *= 2
    return a

def merge(a, l, m, r):
    n1 = m - l
    n2 = r - m
    L = a[l : m]
    R = a[m : r]

    i = 0
    j = 0
    k = 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


def create_random_list(n):
    L = []
    for _ in range(n):
        L.append(random.randint(1,n))
    return L

a = create_random_list(100)
print("Given array is ")
print(a)

mergeSort(a)

print("Sorted array is ")
print(a)

输出：

Given array is
[68, 78, 20, 77, 87, 68, 2, 80, 58, 49, 91, 45, 12, 38, 4, 90, 41, 
 29, 68, 10, 85, 64, 41, 71, 24, 77, 99, 96, 88, 14, 58, 51, 82, 63,
 25, 44, 23, 100, 25, 26, 49, 50, 83, 55, 8, 30, 37, 78, 12, 80, 86,
 88, 86, 9, 88, 62, 58, 100, 10, 69, 62, 46, 29, 75, 12, 22, 15, 15,
 22, 95, 48, 26, 66, 55, 14, 77, 8, 68, 73, 2, 50, 86, 91, 9, 70, 11,
 3, 50, 69, 53, 79, 47, 94, 79, 16, 81, 63, 79, 47, 75]
Sorted array is
[2, 2, 3, 4, 8, 8, 9, 9, 10, 10, 11, 12, 12, 12, 14, 14, 15, 15, 16,
 20, 22, 22, 23, 24, 25, 25, 26, 26, 29, 29, 30, 37, 38, 41, 41, 44,
 45, 46, 47, 47, 48, 49, 49, 50, 50, 50, 51, 53, 55, 55, 58, 58, 58,
 62, 62, 63, 63, 64, 66, 68, 68, 68, 68, 69, 69, 70, 71, 73, 75, 75,
 77, 77, 77, 78, 78, 79, 79, 79, 80, 80, 81, 82, 83, 85, 86, 86, 86,
 87, 88, 88, 88, 90, 91, 91, 94, 95, 96, 99, 100, 100]

Answer 2

如果有人对此感兴趣，请查看递归合并排序实现。你需要 Python 3.8+

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr) >> 1
        mergeSort(left := arr[:mid])
        mergeSort(right := arr[mid:])

        i = j = k = 0

        ll, lr = len(left), len(right)

        while i < ll and j < lr:
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < ll:
            arr[k] = left[i]
            k += 1
            i += 1

        while j < lr:
            arr[k] = right[j]
            k += 1
            j += 1

Mergesort 实现出错

Mergesort Implementation gone wrong

python

iteration

mergesort