归并排序 - 元素码农

发布时间: 2025-03-21 18:42

↑

# 归并排序

归并排序（Merge Sort）是一种稳定的分治排序算法。它的基本思想是将数组分成两个子数组，分别对子数组进行排序，然后将排序后的子数组合并成一个有序数组。

## 基本原理

1. 分解：将待排序数组递归地分成两个子数组
2. 排序：递归地对子数组进行排序
3. 合并：将两个已排序的子数组合并成一个有序数组

## 动画演示

```
初始数组：[ 8 3 2 9 7 1 5 4 ]

分解过程：
[ 8 3 2 9 | 7 1 5 4 ]
[ 8 3 | 2 9 | 7 1 | 5 4 ]
[ 8 | 3 | 2 | 9 | 7 | 1 | 5 | 4 ]

合并过程：
[ 3 8 | 2 9 | 1 7 | 4 5 ]  // 两两合并
[ 2 3 8 9 | 1 4 5 7 ]      // 四四合并
[ 1 2 3 4 5 7 8 9 ]        // 最终合并
```

## 代码实现

### 基本实现

```python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 分解
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 合并
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    # 比较左右数组元素并合并
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 添加剩余元素
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
sorted_arr = merge_sort(arr)
print("排序后:", sorted_arr)
```

### 原地排序版本

```python
def merge_sort_inplace(arr, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(arr)
    
    if end - start <= 1:
        return
    
    # 分解
    mid = (start + end) // 2
    merge_sort_inplace(arr, start, mid)
    merge_sort_inplace(arr, mid, end)
    
    # 合并
    merge_inplace(arr, start, mid, end)

def merge_inplace(arr, start, mid, end):
    # 创建临时数组
    left = arr[start:mid]
    right = arr[mid:end]
    
    i = j = 0
    k = start
    
    # 比较并合并回原数组
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1
    
    # 添加剩余元素
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1
    
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
merge_sort_inplace(arr)
print("排序后:", arr)
```

### 优化版本

```python
def merge_sort_optimized(arr):
    # 对小数组使用插入排序
    if len(arr) <= 10:
        return insertion_sort(arr)
    
    # 使用三数取中法选择分割点
    mid = len(arr) // 2
    if arr[0] > arr[mid]:
        arr[0], arr[mid] = arr[mid], arr[0]
    if arr[mid] > arr[-1]:
        arr[mid], arr[-1] = arr[-1], arr[mid]
    if arr[0] > arr[mid]:
        arr[0], arr[mid] = arr[mid], arr[0]
    
    # 分解和合并
    left = merge_sort_optimized(arr[:mid])
    right = merge_sort_optimized(arr[mid:])
    return merge_optimized(left, right)

def merge_optimized(left, right):
    # 优化特殊情况
    if not left or not right:
        return left or right
    if left[-1] <= right[0]:
        return left + right
    if right[-1] <= left[0]:
        return right + left
    
    # 常规合并
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
sorted_arr = merge_sort_optimized(arr)
print("排序后:", sorted_arr)
```

## 性能分析

### 时间复杂度

- 最好情况：O(n log n)
- 最坏情况：O(n log n)
- 平均情况：O(n log n)

### 空间复杂度

- 基本实现：O(n)
- 原地排序：O(n)

### 稳定性

- 稳定排序算法
- 相等元素的相对位置保持不变

## 优化策略

1. 小数组优化
   - 对小规模数组使用插入排序
   - 一般阈值设为10-15

2. 内存优化
   - 使用原地排序减少内存使用
   - 重用临时数组

3. 特殊情况处理
   - 检查数组是否已经有序
   - 处理重复元素

## 应用场景

1. 外部排序
2. 大数据排序
3. 并行计算
4. 稳定性要求高的场景

## 实际应用示例

### 1. 多路归并排序

```python
def k_way_merge_sort(arrays):
    """
    多路归并排序，用于合并多个已排序的数组
    """
    if not arrays:
        return []
    
    while len(arrays) > 1:
        merged = []
        # 两两合并数组
        for i in range(0, len(arrays), 2):
            if i + 1 < len(arrays):
                merged.append(merge(arrays[i], arrays[i + 1]))
            else:
                merged.append(arrays[i])
        arrays = merged
    
    return arrays[0] if arrays else []

# 使用示例
arrays = [
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9],
    [0, 10]
]
print("排序前的数组列表:", arrays)
sorted_arr = k_way_merge_sort(arrays)
print("合并后的有序数组:", sorted_arr)
```

### 2. 外部排序

```python
class ExternalSort:
    def __init__(self, chunk_size=1000):
        self.chunk_size = chunk_size
    
    def sort_large_file(self, input_file, output_file):
        # 分割大文件成小块并排序
        chunks = self.split_and_sort(input_file)
        # 合并排序后的小块
        self.merge_chunks(chunks, output_file)
    
    def split_and_sort(self, input_file):
        chunks = []
        current_chunk = []
        
        with open(input_file, 'r') as f:
            for line in f:
                num = int(line.strip())
                current_chunk.append(num)
                
                if len(current_chunk) >= self.chunk_size:
                    current_chunk.sort()
                    chunk_file = f'chunk_{len(chunks)}.txt'
                    self.write_chunk(current_chunk, chunk_file)
                    chunks.append(chunk_file)
                    current_chunk = []
        
        if current_chunk:
            current_chunk.sort()
            chunk_file = f'chunk_{len(chunks)}.txt'
            self.write_chunk(current_chunk, chunk_file)
            chunks.append(chunk_file)
        
        return chunks
    
    def write_chunk(self, data, filename):
        with open(filename, 'w') as f:
            for num in data:
                f.write(f"{num}\n")
    
    def merge_chunks(self, chunk_files, output_file):
        with open(output_file, 'w') as out:
            # 打开所有块文件
            files = [open(f, 'r') for f in chunk_files]
            # 从每个文件读取第一个数
            numbers = []
            for f in files:
                line = f.readline()
                if line:
                    numbers.append((int(line), f))
            
            # 创建最小堆
            import heapq
            heapq.heapify(numbers)
            
            # 合并过程
            while numbers:
                num, file = heapq.heappop(numbers)
                out.write(f"{num}\n")
                
                # 从该文件读取下一个数
                line = file.readline()
                if line:
                    heapq.heappush(numbers, (int(line), file))
            
            # 关闭所有文件
            for f in files:
                f.close()
            
            # 删除临时文件
            import os
            for chunk_file in chunk_files:
                os.remove(chunk_file)

# 使用示例
sorter = ExternalSort(chunk_size=1000)
sorter.sort_large_file('input.txt', 'output.txt')
```

## 总结

归并排序是一种重要的排序算法，它的主要特点是：

1. 稳定的排序算法
2. 时间复杂度稳定在O(n log n)
3. 适合外部排序
4. 易于并行化实现

虽然归并排序的空间复杂度较高，但它在某些特定场景下（如外部排序、并行计算）具有明显优势。通过合理的优化（如小数组优化、特殊情况处理等），可以进一步提高其性能。在处理大规模数据或需要稳定排序时，归并排序是一个很好的选择。