HB3-归并排序¶

代码实现¶

C
/**
 * 归并排序主函数（递归实现）
 * 采用分治策略：分解 -> 解决 -> 合并
 * @param A[] 待排序数组
 * @param low 起始索引
 * @param high 结束索引
 */
void MergeSort(int A[], int low, int high) {
    // 递归终止条件：当子数组只有一个元素或为空时
    if (low < high) {
        int mid = (low + high) / 2;  // 分解：找到中点

        // 分治：递归排序左半部分
        MergeSort(A, low, mid);

        // 分治：递归排序右半部分
        MergeSort(A, mid + 1, high);

        // 合并：将两个有序子数组合并成一个有序数组
        Merge(A, low, mid, high);
    }
}

/**
 * 合并两个有序子数组
 * @param A[] 原数组
 * @param low 左子数组起始位置
 * @param mid 左子数组结束位置
 * @param high 右子数组结束位置
 */
void Merge(int A[], int low, int mid, int high) {
    int i, j, k;
    int *temp = (int*)malloc((high - low + 1) * sizeof(int));  // 临时数组

    // 初始化左右子数组的起始指针
    i = low;        // 左子数组指针
    j = mid + 1;    // 右子数组指针
    k = 0;          // 临时数组指针

    // 比较合并：将两个有序子数组合并到临时数组
    while (i <= mid && j <= high) {
        // 将较小的元素放入临时数组
        if (A[i] <= A[j]) {
            temp[k++] = A[i++];
        } else {
            temp[k++] = A[j++];
        }
    }

    // 处理左子数组剩余元素
    while (i <= mid) {
        temp[k++] = A[i++];
    }

    // 处理右子数组剩余元素
    while (j <= high) {
        temp[k++] = A[j++];
    }

    // 将临时数组内容复制回原数组
    for (i = 0; i < k; i++) {
        A[low + i] = temp[i];
    }

    free(temp);  // 释放临时数组空间
}

非递归实现（迭代版本）¶

C
/**
 * 归并排序（非递归实现）
 * 自底向上进行合并
 * @param A[] 待排序数组
 * @param n   数组长度
 */
void MergeSortIterative(int A[], int n) {
    int *temp = (int*)malloc(n * sizeof(int));
    int size;  // 当前子数组大小

    // 从大小为1的子数组开始，逐步扩大
    for (size = 1; size < n; size *= 2) {
        int low;

        // 对每个大小为size的子数组对进行合并
        for (low = 0; low < n - size; low += 2 * size) {
            int mid = low + size - 1;           // 左子数组结束位置
            int high = low + 2 * size - 1;      // 右子数组结束位置

            // 确保右边界不越界
            if (high >= n) {
                high = n - 1;
            }

            // 合并两个子数组
            MergeIterative(A, temp, low, mid, high);
        }
    }

    free(temp);
}

/**
 * 迭代版本的合并函数
 */
void MergeIterative(int A[], int temp[], int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;

    // 合并过程
    while (i <= mid && j <= high) {
        if (A[i] <= A[j]) {
            temp[k++] = A[i++];
        } else {
            temp[k++] = A[j++];
        }
    }

    // 处理剩余元素
    while (i <= mid) temp[k++] = A[i++];
    while (j <= high) temp[k++] = A[j++];

    // 复制回原数组
    for (i = low; i <= high; i++) {
        A[i] = temp[i];
    }
}

算法执行过程图解¶

Text Only

初始数组: [49] [38] [65] [97] [76] [13] [27] [50]
          A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

分解过程:
[49] [38] [65] [97] [76] [13] [27] [50]
 ↓
[49] [38] [65] [97] | [76] [13] [27] [50]
 ↓
[49] [38] | [65] [97] | [76] [13] | [27] [50]
 ↓
[49]|[38] | [65]|[97] | [76]|[13] | [27]|[50]

合并过程:
[38] [49] | [65] [97] | [13] [76] | [27] [50]
 ↓
[38] [49] [65] [97] | [13] [27] [50] [76]
 ↓
[13] [27] [38] [49] [50] [65] [76] [97]

递归调用树图示¶

Text Only

                    MergeSort(0,7)
                   /              \
          MergeSort(0,3)      MergeSort(4,7)
           /        \            /        \
    MergeSort(0,1) MergeSort(2,3) MergeSort(4,5) MergeSort(6,7)
      /    \         /    \        /    \         /    \
  M(0,0) M(1,1)  M(2,2) M(3,3)  M(4,4) M(5,5)  M(6,6) M(7,7)
     \    /         \    /        \    /         \    /
   Merge(0,0,1)   Merge(2,2,3)  Merge(4,4,5)   Merge(6,6,7)
        \             /              \             /
      Merge(0,1,3)              Merge(4,5,7)
              \                    /
              Merge(0,3,7)

复杂度分析¶

时间复杂度：O(n log n)¶

详细分析：

分解阶段：
每次将数组分成两半
分解的深度为 log n 层
合并阶段：
每一层需要合并所有元素
每层合并操作的时间复杂度为 O(n)
共有 log n 层

总时间复杂度：

Text Only
1 2	`T(n) = 2T(n/2) + O(n) 根据主定理：T(n) = O(n log n)`

无论最好、最坏、平均情况：
时间复杂度都为 O(n log n)
这是归并排序的重要特性

空间复杂度：O(n)¶

详细分析：

递归调用栈：
递归深度为 log n
空间复杂度为 O(log n)
临时数组：
每次合并需要 O(n) 的临时空间
虽然可以复用，但在递归过程中需要额外空间
总体空间复杂度：O(n)

关键知识点延伸¶

1. 算法思想：分治法¶

归并排序是分治法的经典应用： - 分解（Divide）：将问题分解为规模更小的子问题 - 解决（Conquer）：递归地解决子问题 - 合并（Combine）：将子问题的解合并为原问题的解

2. 稳定性分析¶

稳定排序：相等元素的相对位置不会改变
在合并过程中，当A[i] == A[j]时，优先选择左子数组的元素
因此相等元素的相对顺序得以保持

3. 与快速排序的比较¶

特性	归并排序	快速排序
时间复杂度	O(n log n)稳定	平均O(n log n)，最坏O(n²)
空间复杂度	O(n)	O(log n)
稳定性	稳定	不稳定
实现难度	中等	简单
缓存性能	一般	较好

4. 优化策略¶

4.1 小数组优化¶

C
#define INSERT_SORT_THRESHOLD 10

void MergeSortOptimized(int A[], int low, int high) {
    if (high - low + 1 < INSERT_SORT_THRESHOLD) {
        // 对小数组使用插入排序
        InsertSort(A + low, high - low + 1);
        return;
    }

    if (low < high) {
        int mid = (low + high) / 2;
        MergeSortOptimized(A, low, mid);
        MergeSortOptimized(A, mid + 1, high);
        Merge(A, low, mid, high);
    }
}

4.2 预分配临时数组¶

C
// 全局临时数组，避免重复分配
static int *temp_array = NULL;
static int temp_size = 0;

void MergeSortWithPrealloc(int A[], int n) {
    if (temp_size < n) {
        temp_array = (int*)realloc(temp_array, n * sizeof(int));
        temp_size = n;
    }
    MergeSortRecursive(A, 0, n - 1);
}

5. 应用场景¶

外部排序：适合处理大量数据的排序
链表排序：归并排序特别适合链表结构
稳定性要求：需要保持相等元素相对顺序的场景
时间复杂度要求严格：需要保证O(n log n)时间复杂度

6. 链表归并排序¶

C
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

/**
 * 链表归并排序
 */
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;

    // 找到链表中点
    ListNode *slow = head, *fast = head, *prev = NULL;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = NULL;  // 断开链表

    // 递归排序两部分
    ListNode *l1 = sortList(head);
    ListNode *l2 = sortList(slow);

    // 合并两个有序链表
    return mergeLists(l1, l2);
}

7. 多路归并¶

C
/**
 * 三路归并排序
 */
void MergeSort3Way(int A[], int low, int high) {
    if (high - low < 2) return;

    int mid1 = low + (high - low) / 3;
    int mid2 = low + 2 * (high - low) / 3;

    MergeSort3Way(A, low, mid1);
    MergeSort3Way(A, mid1 + 1, mid2);
    MergeSort3Way(A, mid2 + 1, high);

    Merge3Way(A, low, mid1, mid2, high);
}

算法特点总结¶

时间复杂度稳定：无论什么情况都是O(n log n)
稳定排序：保持相等元素的相对位置
分治思想：典型的分治算法应用
适合大数据：可以很容易地改造成外部排序
可并行化：分解过程可以并行执行

记忆要点¶

"分而治之"：先分解再合并
递归结构：左半部分 + 右半部分 + 合并
合并关键：使用双指针技术合并两个有序数组
空间代价：需要额外的O(n)空间
稳定保证：相等时优先选择左边元素