求解 算法 二分归并排序

Question

二分归并排序
MergeSort(A,p,r)输入:数组A(p..r
输出:按递增顺序排序的数组A
1.ifp<r
2.then q←L(p+ /2」
3. MergeSort (A, q)
4. MergeSort (A,q 1,r)
5. Merge (A,p ,r)
MergeSort有递归调用,也调用Merge过程

Answer 1

🕒上午好，题主！目前：🟢[在线]
📢参考GPT-4o mini 模型、由清水白石008整理提供！
📣今日金句：“生活中最重要的不是你所处的位置，而是你所朝的方向。” — 奥利弗·温德尔·霍姆斯

二分归并排序（Merge Sort）是一种有效的排序算法，采用分治法（Divide and Conquer）策略。它的基本思想是将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并在一起。以下是二分归并排序的详细实现，包括伪代码和 Python 示例代码。

伪代码

MergeSort(A, p, r)
输入: 数组 A 和索引 p, r
输出: 按递增顺序排序的数组 A

1. if p < r then
2.     q ← (p + r) / 2  // 找到中间索引
3.     MergeSort(A, p, q)  // 递归排序左半部分
4.     MergeSort(A, q + 1, r)  // 递归排序右半部分
5.     Merge(A, p, q, r)  // 合并已排序的两部分

Merge(A, p, q, r)
输入: 数组 A 和索引 p, q, r
输出: 合并 A[p..q] 和 A[q+1..r]

1. n1 ← q - p + 1  // 左半部分的大小
2. n2 ← r - q  // 右半部分的大小
3. 创建临时数组 L[1..n1 + 1] 和 R[1..n2 + 1]
4. for i ← 1 to n1 do
5.     L[i] ← A[p + i - 1]  // 复制左半部分
6. for j ← 1 to n2 do
7.     R[j] ← A[q + j]  // 复制右半部分
8. L[n1 + 1] ← ∞  // 哨兵
9. R[n2 + 1] ← ∞  // 哨兵
10. i ← 1
11. j ← 1
12. for k ← p to r do
13.     if L[i] ≤ R[j] then
14.         A[k] ← L[i]
15.         i ← i + 1
16.     else
17.         A[k] ← R[j]
18.         j ← j + 1

Python 实现

以下是上述伪代码的 Python 实现：

def merge_sort(arr, p, r):
    if p < r:
        q = (p + r) // 2  # 找到中间索引
        merge_sort(arr, p, q)  # 递归排序左半部分
        merge_sort(arr, q + 1, r)  # 递归排序右半部分
        merge(arr, p, q, r)  # 合并已排序的两部分

def merge(arr, p, q, r):
    n1 = q - p + 1  # 左半部分的大小
    n2 = r - q  # 右半部分的大小

    # 创建临时数组
    L = arr[p:q + 1]  # 左半部分
    R = arr[q + 1:r + 1]  # 右半部分

    # 添加哨兵
    L.append(float('inf'))  # 哨兵
    R.append(float('inf'))  # 哨兵

    i = 0  # L 的索引
    j = 0  # R 的索引

    # 合并过程
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1

# 示例使用
if __name__ == "__main__":
    A = [38, 27, 43, 3, 9, 82, 10]
    print("原始数组:", A)
    merge_sort(A, 0, len(A) - 1)
    print("排序后的数组:", A)

代码说明

1. merge_sort 函数：实现了归并排序的递归部分。它将数组分成两半，递归地对每一半进行排序，然后调用 merge 函数合并已排序的部分。
2. merge 函数：负责合并两个已排序的子数组。它使用临时数组 L 和 R 来存储左半部分和右半部分的元素，并使用哨兵（无穷大）来简化合并过程。
3. 主程序：创建一个示例数组，调用 merge_sort 函数进行排序，并打印排序前后的数组。

时间复杂度

• 时间复杂度：O(n log n)，其中 n 是数组的大小。
• 空间复杂度：O(n)，需要额外的空间来存储临时数组。

希望这个实现和解释能帮助您理解二分归并排序的原理和实现！如果您有其他问题，请随时问我。