programming

插入排序算法详解：渐进构建有序序列的优雅策略

插入排序是一种简单直观的排序算法，它的工作方式类似于我们整理扑克牌的过程：逐个取牌并将其插入到手中已排序的牌的正确位置。

1. 算法原理

1.1 基本思想

插入排序的核心思想是”插入”：

  1. 将数组分为已排序和未排序两部分
  2. 逐个取出未排序部分的元素
  3. 在已排序部分找到合适的位置插入
  4. 重复此过程直到所有元素都被插入

1.2 算法步骤详解

1
2
3
4
5
6
7
原始数组: [5, 2, 4, 6, 1, 3]

第1步: [5] | 2, 4, 6, 1, 3  → [2, 5] | 4, 6, 1, 3
第2步: [2, 5] | 4, 6, 1, 3  → [2, 4, 5] | 6, 1, 3
第3步: [2, 4, 5] | 6, 1, 3  → [2, 4, 5, 6] | 1, 3
第4步: [2, 4, 5, 6] | 1, 3  → [1, 2, 4, 5, 6] | 3
第5步: [1, 2, 4, 5, 6] | 3  → [1, 2, 3, 4, 5, 6]

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 基础插入排序实现
void insertion_sort_basic(int arr[], int n) {
    printf("开始插入排序...\n");
    
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 待插入元素
        int j = i - 1;     // 已排序部分的最后一个元素
        
        printf("第%d步: 插入元素 %d\n", i, key);
        
        // 向右移动大于key的元素
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;  // 插入key到正确位置
        
        printf("结果: ");
        for (int k = 0; k < n; k++) {
            if (k <= i) {
                printf("[%d] ", arr[k]);  // 已排序部分
            } else {
                printf("%d ", arr[k]);    // 未排序部分
            }
        }
        printf("\n");
    }
}

// 测试基础插入排序
void test_basic_insertion_sort() {
    printf("=== 基础插入排序测试 ===\n");
    
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    insertion_sort_basic(arr, n);
    printf("\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
// 插入排序统计结构
typedef struct {
    int comparisons;     // 比较次数
    int movements;       // 移动次数
    double time_taken;   // 执行时间
} InsertionSortStats;

// 带统计的插入排序
void insertion_sort_with_stats(int arr[], int n, InsertionSortStats* stats) {
    clock_t start = clock();
    stats->comparisons = 0;
    stats->movements = 0;
    
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0) {
            stats->comparisons++;
            if (arr[j] > key) {
                arr[j + 1] = arr[j];
                stats->movements++;
                j--;
            } else {
                break;
            }
        }
        
        if (j + 1 != i) {
            arr[j + 1] = key;
            stats->movements++;
        }
    }
    
    clock_t end = clock();
    stats->time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
}

// 测试不同数据分布的性能
void test_insertion_sort_performance() {
    printf("=== 插入排序性能测试 ===\n");
    
    const int size = 1000;
    int* random_arr = (int*)malloc(size * sizeof(int));
    int* sorted_arr = (int*)malloc(size * sizeof(int));
    int* reverse_arr = (int*)malloc(size * sizeof(int));
    
    // 生成不同类型的测试数据
    srand(time(NULL));
    
    for (int i = 0; i < size; i++) {
        random_arr[i] = rand() % 1000;
        sorted_arr[i] = i;
        reverse_arr[i] = size - i;
    }
    
    InsertionSortStats stats;
    int* temp = (int*)malloc(size * sizeof(int));
    
    printf("数组大小: %d\n", size);
    printf("%-15s %-10s %-10s %-15s\n", "数据类型", "比较次数", "移动次数", "执行时间");
    printf("-------------------------------------------------------\n");
    
    // 测试随机数组
    memcpy(temp, random_arr, size * sizeof(int));
    insertion_sort_with_stats(temp, size, &stats);
    printf("%-15s %-10d %-10d %-15.6f\n", "随机数组", 
           stats.comparisons, stats.movements, stats.time_taken);
    
    // 测试已排序数组
    memcpy(temp, sorted_arr, size * sizeof(int));
    insertion_sort_with_stats(temp, size, &stats);
    printf("%-15s %-10d %-10d %-15.6f\n", "已排序数组", 
           stats.comparisons, stats.movements, stats.time_taken);
    
    // 测试逆序数组
    memcpy(temp, reverse_arr, size * sizeof(int));
    insertion_sort_with_stats(temp, size, &stats);
    printf("%-15s %-10d %-10d %-15.6f\n", "逆序数组", 
           stats.comparisons, stats.movements, stats.time_taken);
    
    free(random_arr);
    free(sorted_arr);
    free(reverse_arr);
    free(temp);
    printf("\n");
}

2.3 优化版本

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
// 二分查找插入排序
void binary_insertion_sort(int arr[], int n) {
    printf("开始二分插入排序...\n");
    
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        
        // 使用二分查找找到插入位置
        int left = 0, right = i;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        // 移动元素
        for (int j = i; j > left; j--) {
            arr[j] = arr[j - 1];
        }
        
        arr[left] = key;
        
        printf("第%d步插入%d到位置%d: ", i, key, left);
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}

// 递归插入排序
void insertion_sort_recursive(int arr[], int n) {
    if (n <= 1) return;
    
    // 先排序前n-1个元素
    insertion_sort_recursive(arr, n - 1);
    
    // 将第n个元素插入到正确位置
    int key = arr[n - 1];
    int j = n - 2;
    
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    
    arr[j + 1] = key;
}

// 测试优化版本
void test_optimized_insertion_sort() {
    printf("=== 优化版本测试 ===\n");
    
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("二分插入排序:\n");
    printf("原始数组: ");
    for (int i = 0; i < n1; i++) {
        printf("%d ", arr1[i]);
    }
    printf("\n");
    
    binary_insertion_sort(arr1, n1);
    printf("\n");
    
    int arr2[] = {12, 11, 13, 5, 6};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    
    printf("递归版本:\n");
    printf("排序前: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\n");
    
    insertion_sort_recursive(arr2, n2);
    
    printf("排序后: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\n\n");
}

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
void analyze_time_complexity() {
    printf("=== 时间复杂度分析 ===\n");
    
    printf("插入排序的时间复杂度:\n");
    printf("- 最好情况: O(n) - 数组已经有序\n");
    printf("- 平均情况: O(n²) - 随机分布的数据\n");
    printf("- 最坏情况: O(n²) - 数组完全逆序\n\n");
    
    printf("详细分析:\n");
    printf("- 外层循环: n-1次\n");
    printf("- 内层循环平均: n/2次比较和移动\n");
    printf("- 总操作数: (n-1) × n/2 ≈ n²/2\n\n");
    
    // 实际测试验证
    int sizes[] = {100, 200, 400};
    printf("实际测试验证:\n");
    printf("%-10s %-15s %-15s %-15s\n", "数组大小", "最好情况", "平均情况", "最坏情况");
    printf("--------------------------------------------------------\n");
    
    for (int s = 0; s < 3; s++) {
        int size = sizes[s];
        
        int* best_case = (int*)malloc(size * sizeof(int));
        int* worst_case = (int*)malloc(size * sizeof(int));
        int* average_case = (int*)malloc(size * sizeof(int));
        
        // 最好情况：已排序
        for (int i = 0; i < size; i++) {
            best_case[i] = i;
        }
        
        // 最坏情况：逆序
        for (int i = 0; i < size; i++) {
            worst_case[i] = size - i;
        }
        
        // 平均情况：随机
        srand(42);
        for (int i = 0; i < size; i++) {
            average_case[i] = rand() % size;
        }
        
        InsertionSortStats stats;
        
        insertion_sort_with_stats(best_case, size, &stats);
        int best_ops = stats.comparisons + stats.movements;
        
        insertion_sort_with_stats(worst_case, size, &stats);
        int worst_ops = stats.comparisons + stats.movements;
        
        insertion_sort_with_stats(average_case, size, &stats);
        int avg_ops = stats.comparisons + stats.movements;
        
        printf("%-10d %-15d %-15d %-15d\n", size, best_ops, avg_ops, worst_ops);
        
        free(best_case);
        free(worst_case);
        free(average_case);
    }
    printf("\n");
}

3.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
typedef struct {
    int value;
    char id;
} StableElement;

void print_stable_elements(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 insertion_sort_stability_test() {
    printf("=== 稳定性测试 ===\n");
    
    StableElement arr[] = {
        {5, 'A'}, {2, 'B'}, {5, 'C'}, {1, 'D'}, {5, 'E'}
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    print_stable_elements(arr, n, "原始数组");
    
    // 插入排序（稳定版本）
    for (int i = 1; i < n; i++) {
        StableElement key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j].value > key.value) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
    
    print_stable_elements(arr, n, "排序后  ");
    
    printf("\n分析:\n");
    printf("- 插入排序是稳定的排序算法\n");
    printf("- 相等元素的相对位置保持不变\n");
    printf("- 使用 > 而不是 >= 确保稳定性\n\n");
}

4. 优缺点与应用场景

4.1 优点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void insertion_sort_advantages() {
    printf("=== 插入排序的优点 ===\n");
    
    printf("1. 算法简单易懂\n");
    printf("   - 实现代码简洁清晰\n");
    printf("   - 逻辑直观，易于理解\n\n");
    
    printf("2. 自适应性强\n");
    printf("   - 对部分有序数据效率高\n");
    printf("   - 最好情况下时间复杂度为O(n)\n\n");
    
    printf("3. 稳定排序\n");
    printf("   - 保持相等元素的相对位置\n");
    printf("   - 适合多关键字排序\n\n");
    
    printf("4. 原地排序\n");
    printf("   - 空间复杂度O(1)\n");
    printf("   - 内存使用效率高\n\n");
    
    printf("5. 在线算法\n");
    printf("   - 可以实时处理新到达的数据\n");
    printf("   - 适合数据流排序\n\n");
}

4.2 缺点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insertion_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("   - CPU缓存利用率不高\n\n");
}

4.3 适用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void insertion_sort_use_cases() {
    printf("=== 适用场景 ===\n");
    
    printf("1. 小数据集排序 (n < 50)\n");
    printf("   - 常数因子小，实际运行速度快\n");
    printf("   - 代码简洁，调试容易\n\n");
    
    printf("2. 部分有序数据\n");
    printf("   - 利用自适应性，效率高\n");
    printf("   - 接近O(n)的性能\n\n");
    
    printf("3. 在线排序\n");
    printf("   - 数据流实时排序\n");
    printf("   - 增量数据处理\n\n");
    
    printf("4. 混合排序算法的组成部分\n");
    printf("   - Timsort中的运行合并\n");
    printf("   - 快速排序的小数组优化\n\n");
    
    printf("5. 教学和学习\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
20
21
22
23
24
25
26
27
28
29
30
31
int main() {
    printf("========================================\n");
    printf("       插入排序算法完整演示\n");
    printf("========================================\n\n");
    
    // 基础功能测试
    test_basic_insertion_sort();
    
    // 性能统计测试
    test_insertion_sort_performance();
    
    // 优化版本测试
    test_optimized_insertion_sort();
    
    // 时间复杂度分析
    analyze_time_complexity();
    
    // 稳定性测试
    insertion_sort_stability_test();
    
    // 优缺点分析
    insertion_sort_advantages();
    insertion_sort_disadvantages();
    insertion_sort_use_cases();
    
    printf("========================================\n");
    printf("            测试完成\n");
    printf("========================================\n");
    
    return 0;
}

6. 总结

插入排序是一种具有重要理论和实践价值的排序算法：

关键特点

  • 时间复杂度: 最好O(n), 平均O(n²), 最坏O(n²)
  • 空间复杂度: O(1)
  • 稳定性: 稳定
  • 自适应性: 强（对部分有序数据效率高）

核心价值

  1. 教学价值: 理解排序算法的经典入门
  2. 实用价值: 小数据集和部分有序数据的最佳选择
  3. 理论价值: 在线算法和自适应算法的典型代表

使用建议

  • 数据规模小于50时优先考虑
  • 数据基本有序时效果显著
  • 作为复杂排序算法的辅助组件
  • 实时数据流处理的理想选择

插入排序虽然算法简单，但其自适应特性和稳定性使其在特定场景下仍具有不可替代的优势，是每个程序员都应该深入理解的基础算法。

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