插入排序的原理详解与 C 语言实现

插入排序是一种简单且直观的排序算法，适用于少量数据的排序。其主要思想是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间），因此在对数据集进行操作时，空间复杂度较低。

插入排序的工作原理

1. 初始化：从数组的第二个元素开始，认为第一个元素是已排序部分。
2. 逐个插入：取出未排序部分的第一个元素，称为“待插入元素”，在已排序部分中从后向前扫描，找到合适的位置将其插入。
3. 移动元素：在扫描过程中，每个比待插入元素大的已排序元素都向后移动一位，直到找到比待插入元素小的元素，待插入元素插入到该位置之后。

复杂度分析

• 时间复杂度：插入排序的最坏和平均情况时间复杂度都是O(n^2)，其中n是数据的个数。在最好的情况下（即数组已经有序），时间复杂度为O(n)。
• 空间复杂度：插入排序是就地排序算法（in-place），其空间复杂度为O(1)。
• 稳定性：插入排序是稳定的排序算法，保证相同元素的相对顺序不变。

C语言实现插入排序

#include <stdio.h>

// 插入排序函数
void insertionSort(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 = j - 1;
        }
        // 将key插入到正确的位置
        arr[j + 1] = key;
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    // 示例数组
    int arr[] = {12, 11, 13, 5, 6};
    // 数组的大小
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前的数组:\n");
    printArray(arr, n);
    
    // 调用插入排序函数
    insertionSort(arr, n);
    
    printf("排序后的数组:\n");
    printArray(arr, n);
    
    return 0;
}