programming

插入排序算法：渐进构建有序序列

算法原理

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序。

基本思想

  1. 从第二个元素开始：假设第一个元素已排序
  2. 选择待插入元素：取出下一个未排序元素
  3. 向前扫描：在已排序序列中从后向前扫描
  4. 找到插入位置：找到合适位置并插入
  5. 重复过程：直到所有元素都被插入

C语言实现

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

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将大于key的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // 插入key到正确位置
        arr[j + 1] = key;
    }
}

// 二分插入排序（减少比较次数）
void binary_insertion_sort(int arr[], int 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;
    }
}

int main() {
    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");
    
    insertion_sort(arr, n);
    
    printf("排序后: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

复杂度分析

  • 时间复杂度：
    • 最好情况：O(n) - 数组已排序
    • 平均情况：O(n²)
    • 最坏情况：O(n²) - 数组逆序
  • 空间复杂度：O(1)
  • 稳定性：稳定

优缺点

优点

  1. 实现简单
  2. 稳定排序
  3. 自适应，对于近似有序的数据效率很高
  4. 原地排序
  5. 在线算法，可以实时处理数据

缺点

  1. 对于大规模数据效率不高
  2. 比较次数较多

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