在 Python 中尝试混合排序算法（冒泡 + 合并排序）-解网

问：

因此，我的任务是在 python 中创建一个混合排序函数，该函数将利用冒泡和合并排序。这个想法很简单;只要超过值 T（阈值），合并排序就应该递归运行，而当值小于或等于 T 时，就会调用冒泡排序。这略微优化了原始的合并排序功能。

这是我写的代码：

def bubbleSort(arr, l, h):
    isSwapped = False
    size = h - l
    for i in range(size-1):
        for j in range(0, size-i-1):
            if arr[j] > arr[j + 1]:
                isSwapped = True
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if not isSwapped:
            return


def merge(arr, l, m, r):
    size1 = m - l + 1
    size2 = r - m

    l_arr = [0] * size1
    r_arr = [0] * size2

    for i in range(0, size1):
        l_arr[i] = arr[l + i]
    for j in range(0, size2):
        r_arr[j] = arr[m + 1 + j]

    # merge
    i = 0
    j = 0
    k = l

    while i < size1 and j < size2:
        if l_arr[i] <= r_arr[j]:
            arr[k] = l_arr[i]
            i += 1
        else:
            arr[k] = r_arr[j]
            j += 1
        k += 1

    while i < size1:
        arr[k] = l_arr[i]
        i += 1
        k += 1
    while j < size2:
        arr[k] = r_arr[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = l + (r - l) // 2
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)
    else:
        return


def hybridMergeSort(arr, l, r):
    T = 16
    while l < r:
        if len(arr) <= T:
            bubbleSort(arr, l, r)
            break
        else:
            m = len(arr) // 2
            hybridMergeSort(arr, l, m)
            hybridMergeSort(arr, m + 1, r)
            merge(arr, l, m, r)

类似的逻辑也适用于混合快速排序算法。我不知道问题出在哪里。它始终返回错误：RecursionError： maximum recursion depth exceeded。使用 mergeSort（）函数本身时，不会返回相同的错误。顺便说一句，我正在尝试将它们用于长度为 1000 的随机数组。我觉得递归的数量应该是一样的吗？

我错过了什么吗？

python-3.x mergesort 冒泡排序

欢迎来到 StackOverflow！您应该展示一个最小的可重现示例以及您从中获得的完整错误测量。在这种情况下，python 会告诉你，达到递归限制的递归调用是。这允许发现（edit：或至少一个）错误：未更改，并且未更改，因此下一个递归调用将具有与当前递归调用完全相同的参数，因此递归永远不会停止。hybridMergeSort(arr, l, m)lm = len(arr) // 2

1赞 Talaal Bajwa 9/6/2023

@He3lixxx对于不完整的信息，我深表歉意。我弄清楚了为什么会出现递归错误，并修复了它，但问题是现在该函数根本无法正确对数组进行排序。

0赞 Karl Knechtel 9/6/2023

欢迎来到 Stack Overflow。请阅读如何提问。我们在这里没有找到适合您的错误;我们需要一个特定的问题 - 这将是您尽最大努力理解和定位特定问题的结果，并在最小的可重复示例中展示它。

0赞 rcgldr 9/8/2023

更新问题，使其显示您的修复。应该是。len(arr)(r - l + 1)

答：

0赞 chqrlie 9/24/2023 #1

代码中存在多个问题：

在：bubbleSort

您在内部循环中使用了错误的索引：您应该将索引范围移动。l
您应该重置为内循环之前，以尽快停止外循环。isSwappedFalse

由于和都包含，因此切片中的元素数为，因此范围相差 1。lhh - l + 1

def bubbleSort(arr, l, h):
    for i in range(h - l):
        isSwapped = False
        for j in range(l, h-i-1):
            if arr[j] > arr[j + 1]:
               isSwapped = True
               arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if not isSwapped:
           return

在：hybridMerge

while l < r:不正确：它导致了无限循环，因为在循环体中既没有也没有修改。只需写lr
```
  if l < r:
```
测试不正确：应测试切片的长度是否小于或等于，即：如果小于：if len(arr) <= TTh - lT
```
  if r - l < T
```
同样，中点必须从和计算，而不是从数组的长度计算。这就是无限递归的原因。mhl
```
  m = l + (r - l) // 2
```

这是一个修改后的版本：

def bubbleSort(arr, l, h):
    for i in range(h - l):
        isSwapped = False
        for j in range(l, h-i-1):
            if arr[j] > arr[j + 1]:
                isSwapped = True
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            if not isSwapped:
                return

def merge(arr, l, m, r):
    size1 = m - l + 1
    size2 = r - m

    l_arr = arr[l : m+1]
    r_arr = arr[m+1 : r]

    # merge
    i = 0
    j = 0
    k = l

    while i < size1 and j < size2:
        if l_arr[i] <= r_arr[j]:
            arr[k] = l_arr[i]
            i += 1
        else:
            arr[k] = r_arr[j]
            j += 1
        k += 1

    while i < size1:
        arr[k] = l_arr[i]
        i += 1
        k += 1

    while j < size2:
        arr[k] = r_arr[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = l + (r - l) // 2
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)
    else:
        return


def hybridMergeSort(arr, l, r):
    T = 16
    if r - l < T:
        if l < r:
            bubbleSort(arr, l, r)
    else:
        m = l + (r - l) // 2
        hybridMergeSort(arr, l, m)
        hybridMergeSort(arr, m + 1, r)
        merge(arr, l, m, r)

上一个：外部合并排序的正确 SplitSize （Chunk）应该是什么？

下一个：通过在 c 中修改合并排序来对数组的偶数索引进行排序

在 Python 中尝试混合排序算法（冒泡 + 合并排序）

Trying a Hybrid Sort Algorithm (Bubble + Merge Sort) in Python

评论