C语言插入排序详解（从零开始掌握经典排序算法）

插入排序的工作原理

假设我们有一个数组 [5, 2, 4, 6, 1, 3]，我们要将其按升序排列：

1. 从第二个元素（索引为1）开始，因为第一个元素可视为已排序。
2. 取出当前元素（比如2），与前面已排序的部分从右往左比较。
3. 如果前面的元素比它大，就将该元素向右移动一位。
4. 重复此过程，直到找到小于或等于当前元素的位置，然后插入。
5. 继续处理下一个元素，直到整个数组有序。

C语言实现插入排序

下面是一个完整的C语言排序教程代码示例，包含详细注释：

#include <stdio.h>// 插入排序函数void insertionSort(int arr[], int n) {    int i, key, j;    for (i = 1; i < n; i++) {        key = arr[i];  // 当前要插入的元素        j = i - 1;        // 将大于key的元素向右移动        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[] = {5, 2, 4, 6, 1, 3};    int n = sizeof(arr) / sizeof(arr[0]);    printf("排序前: ");    printArray(arr, n);    insertionSort(arr, n);    printf("排序后: ");    printArray(arr, n);    return 0;}  

算法复杂度分析

• 时间复杂度：
  • 最好情况（已排序）：O(n)
  • 平均和最坏情况：O(n²)
• 空间复杂度：O(1)，属于原地排序算法。

适合初学者的排序算法

对于初学者排序算法学习者来说，插入排序因其逻辑清晰、代码简洁而成为入门首选。虽然它在大数据量下效率不如快速排序或归并排序，但在小规模数据或部分有序的数据中表现良好，且稳定（相等元素的相对位置不会改变）。

总结

通过本教程，你已经掌握了C语言插入排序的基本原理、实现方式和适用场景。建议你动手编写并运行上述代码，加深理解。排序算法是编程基础的重要一环，打好这个基础，将为你后续学习更复杂的算法铺平道路！