插入排序

插入排序的时间复杂度为O(n^2)，适用于小规模数据的排序。

它的空间复杂度为O(1)，不需要额外的空间。

插入排序是稳定的排序算法，相同元素的相对位置保持不变。

最好情况下时间复杂度为O(n)，最坏和平均情况下时间复杂度为O(n^2)。


// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i]; // 待插入的元素
        j = i - 1;

        // 依次将元素与已排序序列中的元素比较，找到合适的位置插入
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 插入元素到合适位置
    }
}

完整示例


#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i]; // 待插入的元素
        j = i - 1;

        // 依次将元素与已排序序列中的元素比较，找到合适的位置插入
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 插入元素到合适位置
    }
}

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

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

    printf("原始数组：\n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("排序后的数组：\n");
    printArray(arr, n);

    return 0;
}