算法 之 ‌分治算法（Divide and Conquer）

算法 之 ‌分治算法（Divide and Conquer）

1. 基础概念

1.1 定义

分治算法是一种递归解决问题的方法，将原问题划分为若干规模较小但结构相同的子问题，递归求解这些子问题，然后将子问题的解组合为原问题的解。

• Divide：将问题划分为若干子问题。
• Conquer：递归地解决每个子问题。
• Combine：将子问题的解合并成原问题的解。

1.2 特点

• 分治算法通常依赖递归实现。
• 具有天然的并行性，适合分布式或多线程环境。
• 常用于问题具有明显的分解结构时，如排序问题。

1.3 使用场景

• 排序算法：快速排序（Quick Sort）、归并排序（Merge Sort）。
• 搜索问题：二分查找（Binary Search）。
• 几何问题：最近点对问题（Closest Pair）。

2. 实现与操作

2.1 核心操作实现

以下是归并排序的C语言实现代码示例：

#include <stdio.h> #include <stdlib.h> // 合并两个子数组 void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int* L = (int*)malloc(n1 * sizeof(int)); int* R = (int*)malloc(n2 * sizeof(int)); for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; free(L); free(R); } // 递归实现归并排序 void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(arr, left, mid); // 排序左子数组 mergeSort(arr, mid + 1, right); // 排序右子数组 merge(arr, left, mid, right); // 合并两个已排序的子数组 } } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int size = sizeof(arr) / sizeof(arr[0]); printf("原数组: "); for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); mergeSort(arr, 0, size - 1); printf("排序后数组: "); for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); return 0; } </stdlib.h></stdio.h>

2.2 代码详解

该代码实现了归并排序算法，分为以下关键步骤：

1. 递归分解：使用`mergeSort`函数递归地将数组划分为左右两个子数组。
2. 合并子数组：使用`merge`函数将两个已排序的子数组合并为一个有序数组。
3. 递归终止条件：当子数组大小为1时停止递归。

3. 时间与空间复杂度分析

3.1 时间复杂度

归并排序的时间复杂度为 O(n log n)。

• 分解过程：每次将数组分成两半，需要 log n 次。
• 合并过程：每一层的合并操作需要 O(n) 时间。

3.2 空间复杂度

归并排序的空间复杂度为 O(n)，因为需要辅助数组来存储中间结果。

4. 优缺点与局限性

4.1 优点

• 具有稳定性（不会改变相同元素的顺序）。
• 时间复杂度较优，为 O(n log n)。
• 适用于大规模数据的排序。

4.2 缺点与局限性

• 需要额外的 O(n) 空间。
• 对于小规模数据，效率可能不如插入排序。

5. 常见应用场景

5.1 实际应用

归并排序在处理需要稳定排序且数据量较大的情况下非常有效，例如外部排序和大规模数据处理。

6. 代码编译与运行

6.1 编译命令

使用以下命令编译代码：

gcc merge_sort.c -o merge_sort

6.2 测试用例

测试用例：输入数组 [12, 11, 13, 5, 6, 7]。

运行结果：

原数组: 12 11 13 5 6 7
排序后数组: 5 6 7 11 12 13