programming

归并排序算法实现：稳定高效的分治排序策略

归并排序是建立在归并操作上的一种有效的排序算法，采用分治法的经典应用。该算法由约翰·冯·诺伊曼在1945年发明，是一种稳定的排序算法。

1. 算法原理

1.1 基本思想

归并排序采用”分治法”策略：

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

1.2 算法步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
原始数组: [38, 27, 43, 3, 9, 82, 10]

分解阶段:
[38, 27, 43, 3, 9, 82, 10]
    ↓
[38, 27, 43, 3] [9, 82, 10]
    ↓              ↓
[38, 27] [43, 3]  [9, 82] [10]
    ↓       ↓        ↓      ↓
[38] [27] [43] [3] [9] [82] [10]

合并阶段:
[27, 38] [3, 43]  [9, 82] [10]
    ↓              ↓
[3, 27, 38, 43]  [9, 10, 82]
    ↓
[3, 9, 10, 27, 38, 43, 82]

2. C语言实现

2.1 基础版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 合并两个已排序的子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 创建临时数组
    int* left_arr = (int*)malloc(n1 * sizeof(int));
    int* right_arr = (int*)malloc(n2 * sizeof(int));
    
    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        left_arr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        right_arr[j] = arr[mid + 1 + j];
    }
    
    printf("  合并 [");
    for (int i = 0; i < n1; i++) {
        printf("%d%s", left_arr[i], i == n1-1 ? "" : ",");
    }
    printf("] 和 [");
    for (int i = 0; i < n2; i++) {
        printf("%d%s", right_arr[i], i == n2-1 ? "" : ",");
    }
    printf("]\n");
    
    // 合并临时数组回到原数组
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (left_arr[i] <= right_arr[j]) {
            arr[k] = left_arr[i];
            i++;
        } else {
            arr[k] = right_arr[j];
            j++;
        }
        k++;
    }
    
    // 复制剩余元素
    while (i < n1) {
        arr[k] = left_arr[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = right_arr[j];
        j++;
        k++;
    }
    
    printf("  结果: [");
    for (int i = left; i <= right; i++) {
        printf("%d%s", arr[i], i == right ? "" : ",");
    }
    printf("]\n\n");
    
    free(left_arr);
    free(right_arr);
}

// 归并排序主函数
void merge_sort_basic(int arr[], int left, int right, int depth) {
    if (left < right) {
        printf("第%d层: 分解 [%d,%d]\n", depth, left, right);
        
        int mid = left + (right - left) / 2;
        
        merge_sort_basic(arr, left, mid, depth + 1);
        merge_sort_basic(arr, mid + 1, right, depth + 1);
        
        printf("第%d层: 合并 [%d,%d,%d]\n", depth, left, mid, right);
        merge(arr, left, mid, right);
    }
}

// 测试基础归并排序
void test_basic_merge_sort() {
    printf("=== 基础归并排序测试 ===\n");
    
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    merge_sort_basic(arr, 0, n - 1, 0);
    
    printf("最终结果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

2.2 优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
// 优化的合并函数（减少数组复制）
void merge_optimized(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    
    // 合并到临时数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    // 复制剩余元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    
    // 复制回原数组
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

// 优化的归并排序
void merge_sort_optimized(int arr[], int temp[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        merge_sort_optimized(arr, temp, left, mid);
        merge_sort_optimized(arr, temp, mid + 1, right);
        
        merge_optimized(arr, temp, left, mid, right);
    }
}

// 小数组优化版本
void insertion_sort_range(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

void merge_sort_hybrid(int arr[], int temp[], int left, int right) {
    if (left < right) {
        // 小数组使用插入排序
        if (right - left < 10) {
            insertion_sort_range(arr, left, right);
            return;
        }
        
        int mid = left + (right - left) / 2;
        
        merge_sort_hybrid(arr, temp, left, mid);
        merge_sort_hybrid(arr, temp, mid + 1, right);
        
        // 如果已经有序，跳过合并
        if (arr[mid] <= arr[mid + 1]) {
            return;
        }
        
        merge_optimized(arr, temp, left, mid, right);
    }
}

// 迭代版本
void merge_sort_iterative(int arr[], int n) {
    int* temp = (int*)malloc(n * sizeof(int));
    
    // 自底向上的合并
    for (int curr_size = 1; curr_size < n; curr_size *= 2) {
        for (int left = 0; left < n - curr_size; left += 2 * curr_size) {
            int mid = left + curr_size - 1;
            int right = (left + 2 * curr_size - 1 < n - 1) ? 
                       left + 2 * curr_size - 1 : n - 1;
            
            merge_optimized(arr, temp, left, mid, right);
        }
        
        printf("大小为 %d 的子数组合并后: ", curr_size);
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
    
    free(temp);
}

// 测试优化版本
void test_optimized_merge_sort() {
    printf("=== 优化版本测试 ===\n");
    
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int arr2[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    
    int* temp = (int*)malloc(n * sizeof(int));
    
    printf("优化归并排序:\n");
    printf("排序前: ");
    for (int i = 0; i < n; i++) printf("%d ", arr1[i]);
    printf("\n");
    
    merge_sort_optimized(arr1, temp, 0, n - 1);
    
    printf("排序后: ");
    for (int i = 0; i < n; i++) printf("%d ", arr1[i]);
    printf("\n\n");
    
    printf("迭代归并排序:\n");
    printf("排序前: ");
    for (int i = 0; i < n; i++) printf("%d ", arr2[i]);
    printf("\n");
    
    merge_sort_iterative(arr2, n);
    
    printf("最终结果: ");
    for (int i = 0; i < n; i++) printf("%d ", arr2[i]);
    printf("\n\n");
    
    free(temp);
}

3. 算法分析

3.1 时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
typedef struct {
    int comparisons;
    int movements;
    double time_taken;
} MergeSortStats;

MergeSortStats stats;

void merge_with_stats(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    
    while (i <= mid && j <= right) {
        stats.comparisons++;
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
        stats.movements++;
    }
    
    while (i <= mid) {
        temp[k++] = arr[i++];
        stats.movements++;
    }
    while (j <= right) {
        temp[k++] = arr[j++];
        stats.movements++;
    }
    
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
        stats.movements++;
    }
}

void merge_sort_with_stats(int arr[], int temp[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        merge_sort_with_stats(arr, temp, left, mid);
        merge_sort_with_stats(arr, temp, mid + 1, right);
        
        merge_with_stats(arr, temp, left, mid, right);
    }
}

void analyze_time_complexity() {
    printf("=== 时间复杂度分析 ===\n");
    
    printf("归并排序的时间复杂度:\n");
    printf("- 最好情况: O(n log n)\n");
    printf("- 平均情况: O(n log n)\n");
    printf("- 最坏情况: O(n log n)\n");
    printf("- 时间复杂度稳定，不受数据分布影响\n\n");
    
    int sizes[] = {100, 500, 1000};
    printf("实际测试验证:\n");
    printf("%-10s %-15s %-15s %-15s\n", "数组大小", "比较次数", "移动次数", "理论复杂度");
    printf("-------------------------------------------------------\n");
    
    for (int s = 0; s < 3; s++) {
        int size = sizes[s];
        int* arr = (int*)malloc(size * sizeof(int));
        int* temp = (int*)malloc(size * sizeof(int));
        
        // 生成随机数据
        srand(42);
        for (int i = 0; i < size; i++) {
            arr[i] = rand() % 1000;
        }
        
        memset(&stats, 0, sizeof(stats));
        merge_sort_with_stats(arr, temp, 0, size - 1);
        
        double theoretical = size * log2(size);
        
        printf("%-10d %-15d %-15d %-15.0f\n", 
               size, stats.comparisons, stats.movements, theoretical);
        
        free(arr);
        free(temp);
    }
    printf("\n");
}

3.2 稳定性验证

``c
typedef struct {
int value;
char id;
} StableElement;

void print_stable_array(StableElement arr[], int n, const char* title) {
printf(“%s: “, title);
for (int i = 0; i < n; i++) {
printf(“(%d,%c) “, arr[i].value, arr[i].id);
}
printf(“\n”);
}

void merge_stable(StableElement arr[], StableElement temp[], int left, int mid, int right) {
int i = left, j = mid + 1, k = left;

while (i <= mid && j <= right) {
    if (arr[i].value <= arr[j].value) {
        temp[k++] = arr[i++];
    } else {
        temp[k++] = arr[j++];
    }
}

while (i <= mid) {
    temp[k++] = arr[i++];
}
while (j <= right) {
    temp[k++] = arr[j++];
}

for (i = left; i <= right; i++) {
    arr[i] = temp[i];
}

}

void merge_sort_stable(StableElement arr[], StableElement temp[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort_stable(arr, temp, left, mid);
merge_sort_stable(arr, temp, mid + 1, right);
merge_stable(arr, temp, left, mid, right);
}
}

void test_stability() {
printf(“=== 稳定性测试 ===\n”);

StableElement arr[] = {
    {5, 'A'}, {2, 'B'}, {5, 'C'}, {1, 'D'}, {5, 'E'}, {2, 'F'}
};
int n = sizeof(arr) / sizeof(arr[0]);

StableElement* temp = (StableElement*)malloc(n * sizeof(StableElement));

print_stable_array(arr, n, "排序前");
merge_sort_stable(arr, temp, 0, n - 1);
print_stable_array(arr, n, "排序后");

printf("\n分析: 归并排序是稳定的，相等元素的相对位置保持不变\n\n");

free(temp);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

## 4. 优缺点与应用

### 4.1 优点

```c
void merge_sort_advantages() {
    printf("=== 归并排序的优点 ===\n");
    
    printf("1. 时间复杂度稳定\n");
    printf("   - 始终为O(n log n)\n");
    printf("   - 不受数据分布影响\n\n");
    
    printf("2. 稳定排序\n");
    printf("   - 保持相等元素的相对位置\n");
    printf("   - 适合多关键字排序\n\n");
    
    printf("3. 可预测性强\n");
    printf("   - 性能可预测\n");
    printf("   - 适合实时系统\n\n");
    
    printf("4. 易于并行化\n");
    printf("   - 子问题独立\n");
    printf("   - 适合多线程实现\n\n");
}

4.2 缺点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void merge_sort_disadvantages() {
    printf("=== 归并排序的缺点 ===\n");
    
    printf("1. 空间复杂度高\n");
    printf("   - 需要O(n)额外空间\n");
    printf("   - 不是原地排序\n\n");
    
    printf("2. 内存访问模式\n");
    printf("   - 大量内存复制操作\n");
    printf("   - 缓存性能可能不佳\n\n");
    
    printf("3. 小数组开销\n");
    printf("   - 递归开销相对较大\n");
    printf("   - 需要优化处理\n\n");
}

4.3 应用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void merge_sort_applications() {
    printf("=== 应用场景 ===\n");
    
    printf("1. 需要稳定排序的场合\n");
    printf("   - 多关键字排序\n");
    printf("   - 保持原有顺序\n\n");
    
    printf("2. 大数据集排序\n");
    printf("   - 外部排序\n");
    printf("   - 文件排序\n\n");
    
    printf("3. 实时系统\n");
    printf("   - 性能可预测\n");
    printf("   - 最坏情况可控\n\n");
    
    printf("4. 并行计算\n");
    printf("   - 多核处理器\n");
    printf("   - 分布式系统\n\n");
}

5. 主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main() {
    printf("========================================\n");
    printf("       归并排序算法完整演示\n");
    printf("========================================\n\n");
    
    test_basic_merge_sort();
    test_optimized_merge_sort();
    analyze_time_complexity();
    test_stability();
    merge_sort_advantages();
    merge_sort_disadvantages();
    merge_sort_applications();
    
    printf("========================================\n");
    printf("            测试完成\n");
    printf("========================================\n");
    
    return 0;
}

6. 总结

归并排序是一种优秀的排序算法，具有以下特点：

核心优势

  • 稳定性: 保持相等元素的相对位置
  • 可预测性: 时间复杂度始终为O(n log n)
  • 适应性: 适合各种数据分布
  • 并行性: 易于并行化实现

应用价值

归并排序在需要稳定排序和可预测性能的场景中具有重要价值，是外部排序和大数据处理的理想选择。虽然空间复杂度较高，但其稳定的性能表现使其在实际应用中仍有重要地位。—
title: “归并排序算法实现：稳定高效的分治排序策略”
date: 2009-09-21
author: “C语言技术研究团队”
categories: programming
tags: [归并排序, 分治算法]
description: “深入学习归并排序算法的核心原理和实现技巧，探讨分治思想在排序中的应用，包含详细的C语言实现和性能优化策略。”
excerpt: “归并排序是一种稳定的O(n log n)排序算法，采用分治策略，在处理大数据集和需要稳定性的场景中表现优异。”
layout: post
comment: true

归并排序是建立在归并操作上的一种有效的排序算法，采用分治法的经典应用。该算法由约翰·冯·诺伊曼在1945年发明，是一种稳定的排序算法。

1. 算法原理

1.1 基本思想

归并排序采用”分治法”策略：

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

1.2 算法步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
原始数组: [38, 27, 43, 3, 9, 82, 10]

分解阶段:
[38, 27, 43, 3, 9, 82, 10]
    ↓
[38, 27, 43, 3] [9, 82, 10]
    ↓              ↓
[38, 27] [43, 3]  [9, 82] [10]
    ↓       ↓        ↓      ↓
[38] [27] [43] [3] [9] [82] [10]

合并阶段:
[27, 38] [3, 43]  [9, 82] [10]
    ↓              ↓
[3, 27, 38, 43]  [9, 10, 82]
    ↓
[3, 9, 10, 27, 38, 43, 82]

2. C语言实现

2.1 基础版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 合并两个已排序的子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 创建临时数组
    int* left_arr = (int*)malloc(n1 * sizeof(int));
    int* right_arr = (int*)malloc(n2 * sizeof(int));
    
    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        left_arr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        right_arr[j] = arr[mid + 1 + j];
    }
    
    printf("  合并 [");
    for (int i = 0; i < n1; i++) {
        printf("%d%s", left_arr[i], i == n1-1 ? "" : ",");
    }
    printf("] 和 [");
    for (int i = 0; i < n2; i++) {
        printf("%d%s", right_arr[i], i == n2-1 ? "" : ",");
    }
    printf("]\n");
    
    // 合并临时数组回到原数组
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (left_arr[i] <= right_arr[j]) {
            arr[k] = left_arr[i];
            i++;
        } else {
            arr[k] = right_arr[j];
            j++;
        }
        k++;
    }
    
    // 复制剩余元素
    while (i < n1) {
        arr[k] = left_arr[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = right_arr[j];
        j++;
        k++;
    }
    
    printf("  结果: [");
    for (int i = left; i <= right; i++) {
        printf("%d%s", arr[i], i == right ? "" : ",");
    }
    printf("]\n\n");
    
    free(left_arr);
    free(right_arr);
}

// 归并排序主函数
void merge_sort_basic(int arr[], int left, int right, int depth) {
    if (left < right) {
        printf("第%d层: 分解 [%d,%d]\n", depth, left, right);
        
        int mid = left + (right - left) / 2;
        
        merge_sort_basic(arr, left, mid, depth + 1);
        merge_sort_basic(arr, mid + 1, right, depth + 1);
        
        printf("第%d层: 合并 [%d,%d,%d]\n", depth, left, mid, right);
        merge(arr, left, mid, right);
    }
}

// 测试基础归并排序
void test_basic_merge_sort() {
    printf("=== 基础归并排序测试 ===\n");
    
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    merge_sort_basic(arr, 0, n - 1, 0);
    
    printf("最终结果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

2.2 优化版本

``c
// 优化的合并函数（减少数组复制）
void merge_optimized(int arr[], int temp[], int left, int mid, int right) {
int i = left, j = mid + 1, k = left;

// 合并到临时数组
while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++];
    } else {
        temp[k++] = arr[j++];
    }
}

// 复制剩余元素
while (i <= mid) {
    temp[k++] = arr[i++];
}
while (j <= right) {
    temp[k++] = arr[j++];
}

// 复制回原数组
for (i = left; i <= right; i++) {
    arr[i] = temp[i];
}

}

// 优化的归并排序
void merge_sort_optimized(int arr[], int temp[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;

    merge_sort_optimized(arr, temp, left, mid);
    merge_sort_optimized(arr, temp, mid + 1, right);
    
    merge_optimized(arr, temp, left, mid, right);
}

}

// 小数组优化版本
void insertion_sort_range(int arr[], int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;

    while (j >= left && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    
    arr[j + 1] = key;
}

}

void merge_sort_hybrid(int arr[], int temp[], int left, int right) {
if (left < right) {
// 小数组使用插入排序
if (right - left < 10) {
insertion_sort_range(arr, left, right);
return;
}

    int mid = left + (right - left) / 2;
    
    merge_sort_hybrid(arr, temp, left, mid);
    merge_sort_hybrid(arr, temp, mid + 1, right);
    
    // 如果已经有序，跳过合并
    if (arr[mid] <= arr[mid + 1]) {
        return;
    }
    
    merge_optimized(arr, temp, left, mid, right);
}

}

// 迭代版本
void merge_sort_iterative(int arr[], int n) {
int* temp = (int*)malloc(n * sizeof(int));

// 自底向上的合并
for (int curr_size = 1; curr_size < n; curr_size *= 2) {
    for (int left = 0; left < n - curr_size; left += 2 * curr_size) {
        int mid = left + curr_size - 1;
        int right = (left + 2 * curr_size - 1 < n - 1) ? 
                   left + 2 * curr_size - 1 : n - 1;
        
        merge_optimized(arr, temp, left, mid, right);
    }
    
    printf("大小为 %d 的子数组合并后: ", curr_size);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

free(temp);

}

// 测试优化版本
void test_optimized_merge_sort() {
printf(“=== 优化版本测试 ===\n”);

int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr1) / sizeof(arr1[0]);

int* temp = (int*)malloc(n * sizeof(int));

printf("优化归并排序:\n");
printf("排序前: ");
for (int i = 0; i < n; i++) printf("%d ", arr1[i]);
printf("\n");

merge_sort_optimized(arr1, temp, 0, n - 1);

printf("排序后: ");
for (int i = 0; i < n; i++) printf("%d ", arr1[i]);
printf("\n\n");

printf("迭代归并排序:\n");
printf("排序前: ");
for (int i = 0; i < n; i++) printf("%d ", arr2[i]);
printf("\n");

merge_sort_iterative(arr2, n);

printf("最终结果: ");
for (int i = 0; i < n; i++) printf("%d ", arr2[i]);
printf("\n\n");

free(temp);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

## 3. 算法分析

### 3.1 时间复杂度

```c
typedef struct {
    int comparisons;
    int movements;
    double time_taken;
} MergeSortStats;

MergeSortStats stats;

void merge_with_stats(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    
    while (i <= mid && j <= right) {
        stats.comparisons++;
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
        stats.movements++;
    }
    
    while (i <= mid) {
        temp[k++] = arr[i++];
        stats.movements++;
    }
    while (j <= right) {
        temp[k++] = arr[j++];
        stats.movements++;
    }
    
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
        stats.movements++;
    }
}

void merge_sort_with_stats(int arr[], int temp[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        merge_sort_with_stats(arr, temp, left, mid);
        merge_sort_with_stats(arr, temp, mid + 1, right);
        
        merge_with_stats(arr, temp, left, mid, right);
    }
}

void analyze_time_complexity() {
    printf("=== 时间复杂度分析 ===\n");
    
    printf("归并排序的时间复杂度:\n");
    printf("- 最好情况: O(n log n)\n");
    printf("- 平均情况: O(n log n)\n");
    printf("- 最坏情况: O(n log n)\n");
    printf("- 时间复杂度稳定，不受数据分布影响\n\n");
    
    int sizes[] = {100, 500, 1000};
    printf("实际测试验证:\n");
    printf("%-10s %-15s %-15s %-15s\n", "数组大小", "比较次数", "移动次数", "理论复杂度");
    printf("-------------------------------------------------------\n");
    
    for (int s = 0; s < 3; s++) {
        int size = sizes[s];
        int* arr = (int*)malloc(size * sizeof(int));
        int* temp = (int*)malloc(size * sizeof(int));
        
        // 生成随机数据
        srand(42);
        for (int i = 0; i < size; i++) {
            arr[i] = rand() % 1000;
        }
        
        memset(&stats, 0, sizeof(stats));
        merge_sort_with_stats(arr, temp, 0, size - 1);
        
        double theoretical = size * log2(size);
        
        printf("%-10d %-15d %-15d %-15.0f\n", 
               size, stats.comparisons, stats.movements, theoretical);
        
        free(arr);
        free(temp);
    }
    printf("\n");
}

3.2 稳定性验证

``c
typedef struct {
int value;
char id;
} StableElement;

void print_stable_array(StableElement arr[], int n, const char* title) {
printf(“%s: “, title);
for (int i = 0; i < n; i++) {
printf(“(%d,%c) “, arr[i].value, arr[i].id);
}
printf(“\n”);
}

void merge_stable(StableElement arr[], StableElement temp[], int left, int mid, int right) {
int i = left, j = mid + 1, k = left;

while (i <= mid && j <= right) {
    if (arr[i].value <= arr[j].value) {
        temp[k++] = arr[i++];
    } else {
        temp[k++] = arr[j++];
    }
}

while (i <= mid) {
    temp[k++] = arr[i++];
}
while (j <= right) {
    temp[k++] = arr[j++];
}

for (i = left; i <= right; i++) {
    arr[i] = temp[i];
}

}

void merge_sort_stable(StableElement arr[], StableElement temp[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort_stable(arr, temp, left, mid);
merge_sort_stable(arr, temp, mid + 1, right);
merge_stable(arr, temp, left, mid, right);
}
}

void test_stability() {
printf(“=== 稳定性测试 ===\n”);

StableElement arr[] = {
    {5, 'A'}, {2, 'B'}, {5, 'C'}, {1, 'D'}, {5, 'E'}, {2, 'F'}
};
int n = sizeof(arr) / sizeof(arr[0]);

StableElement* temp = (StableElement*)malloc(n * sizeof(StableElement));

print_stable_array(arr, n, "排序前");
merge_sort_stable(arr, temp, 0, n - 1);
print_stable_array(arr, n, "排序后");

printf("\n分析: 归并排序是稳定的，相等元素的相对位置保持不变\n\n");

free(temp);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

## 4. 优缺点与应用

### 4.1 优点

```c
void merge_sort_advantages() {
    printf("=== 归并排序的优点 ===\n");
    
    printf("1. 时间复杂度稳定\n");
    printf("   - 始终为O(n log n)\n");
    printf("   - 不受数据分布影响\n\n");
    
    printf("2. 稳定排序\n");
    printf("   - 保持相等元素的相对位置\n");
    printf("   - 适合多关键字排序\n\n");
    
    printf("3. 可预测性强\n");
    printf("   - 性能可预测\n");
    printf("   - 适合实时系统\n\n");
    
    printf("4. 易于并行化\n");
    printf("   - 子问题独立\n");
    printf("   - 适合多线程实现\n\n");
}

4.2 缺点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void merge_sort_disadvantages() {
    printf("=== 归并排序的缺点 ===\n");
    
    printf("1. 空间复杂度高\n");
    printf("   - 需要O(n)额外空间\n");
    printf("   - 不是原地排序\n\n");
    
    printf("2. 内存访问模式\n");
    printf("   - 大量内存复制操作\n");
    printf("   - 缓存性能可能不佳\n\n");
    
    printf("3. 小数组开销\n");
    printf("   - 递归开销相对较大\n");
    printf("   - 需要优化处理\n\n");
}

4.3 应用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void merge_sort_applications() {
    printf("=== 应用场景 ===\n");
    
    printf("1. 需要稳定排序的场合\n");
    printf("   - 多关键字排序\n");
    printf("   - 保持原有顺序\n\n");
    
    printf("2. 大数据集排序\n");
    printf("   - 外部排序\n");
    printf("   - 文件排序\n\n");
    
    printf("3. 实时系统\n");
    printf("   - 性能可预测\n");
    printf("   - 最坏情况可控\n\n");
    
    printf("4. 并行计算\n");
    printf("   - 多核处理器\n");
    printf("   - 分布式系统\n\n");
}

5. 主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main() {
    printf("========================================\n");
    printf("       归并排序算法完整演示\n");
    printf("========================================\n\n");
    
    test_basic_merge_sort();
    test_optimized_merge_sort();
    analyze_time_complexity();
    test_stability();
    merge_sort_advantages();
    merge_sort_disadvantages();
    merge_sort_applications();
    
    printf("========================================\n");
    printf("            测试完成\n");
    printf("========================================\n");
    
    return 0;
}

6. 总结

归并排序是一种优秀的排序算法，具有以下特点：

核心优势

  • 稳定性: 保持相等元素的相对位置
  • 可预测性: 时间复杂度始终为O(n log n)
  • 适应性: 适合各种数据分布
  • 并行性: 易于并行化实现

应用价值

归并排序在需要稳定排序和可预测性能的场景中具有重要价值，是外部排序和大数据处理的理想选择。虽然空间复杂度较高，但其稳定的性能表现使其在实际应用中仍有重要地位。

版权所有，如有侵权请联系我