C语言插入排序之直接插入排序

概要

快速排序（Quick Sort）： 是一种非常高效的排序算法，基于分治法（Divide and Conquer）的思想。它的基本思想是通过一个"基准"元素（pivot）将数组分成两部分，其中一部分所有元素都比基准小，另一部分所有元素都比基准大，然后递归地对这两部分继续进行排序。

代码

#include <stdio.h>

// 直接插入排序函数
void insertionSort(int arr[], int n) {
    int i, j, key;

    // 从第二个元素开始（下标为 1）
    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--;                // 继续向前比较
        }

        // 将 key 插入到正确的位置
        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[] = {12, 11, 13, 5, 6}; // 测试数组
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度

    printf("排序前的数组: ");
    printArray(arr, n);

    insertionSort(arr, n); // 调用插入排序函数

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

    return 0;
}

输出

排序前的数组: 12 11 13 5 6 
排序后的数组: 5 6 11 12 13 

分析

针对数组【12, 11, 13, 5, 6】做直接插入排序解析，解析如下：

1、第 1 轮：

• 已排序部分：[12]

• 未排序部分：[11, 13, 5, 6]

• 操作：

  • 取出未排序部分的第一个元素 11。
  • 将 11 与已排序部分的 12 比较，11 < 12，因此将 12 向后移动。
  • 将 11 插入到正确的位置。

• 数组变化：

  • 排序前：[12, 11, 13, 5, 6]
  • 排序后：[11, 12, 13, 5, 6]

2、第 2 轮：

• 已排序部分：[11, 12]

• 未排序部分：[13, 5, 6]

• 操作：

  • 取出未排序部分的第一个元素 13。
  • 将 13 与已排序部分的 12 比较，13 > 12，因此不需要移动。
  • 将 13 插入到正确的位置。

• 数组变化：

  • 排序前：[11, 12, 13, 5, 6]
  • 排序后：[11, 12, 13, 5, 6]

3、继续排序，直到全部元素排好序。

最终排序结果：

[5, 6, 11, 12, 13]

优缺点

优点：

• 插入排序简单、稳定，适用于小规模数据或部分有序的情况。
• 对于小规模数据，常数因子较小，执行效率较高。
• 原地排序，节省内存空间。

缺点：

• 对于大规模数据，时间复杂度为 O(n²)，效率较低。
• 移动操作频繁，导致性能瓶颈。
• 不适用于需要高效排序的大规模数据集。

平均时间复杂度为O(n²)，最好的情况下是 O(n)，稳定排序