C语言插入排序（附带源码和解析）

插入排序是一种简单直观的排序算法，它的工作原理类似于我们打扑克牌时整理手中的牌。在这个过程中，我们会将每一张新拿到的牌插入到已经排好序的牌中的适当位置。插入排序就是采用了这种思想，通过构建有序序列，对未排序数据进行一个个插入操作，从而达到排序的目的。

插入排序的基本原理

插入排序的核心思想是将一个新元素插入到已经排好序的有序表中，从而得到一个新的、元素数量加一的有序表。具体来说，插入排序的过程如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤 2~5。

让我们通过一个具体的例子来理解这个过程。假设我们有一个数组 [5, 2, 4, 6, 1, 3]，我们要对它进行升序排序。

// 初始状态
[5, 2, 4, 6, 1, 3]

// 第一步，5 已经排序
[5 | 2, 4, 6, 1, 3]

// 第二步，将 2 插入到已排序序列中
[2, 5 | 4, 6, 1, 3]

// 第三步，将 4 插入到已排序序列中
[2, 4, 5 | 6, 1, 3]

// 第四步，6 已经在正确的位置
[2, 4, 5, 6 | 1, 3]

// 第五步，将 1 插入到已排序序列中
[1, 2, 4, 5, 6 | 3]

// 最后一步，将 3 插入到已排序序列中
[1, 2, 3, 4, 5, 6]

在这个过程中，竖线左边的元素始终保持有序，而我们每次都将右边的一个元素插入到左边合适的位置。

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) {
    int i;
    for (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;
}

运行结果：

原始数组:
64 34 25 12 22 11 90
排序后的数组:
11 12 22 25 34 64 90

这段代码中，insertionSort 函数实现了插入排序的核心逻辑。它使用两个循环：外层循环遍历未排序部分的每个元素，内层循环将当前元素插入到已排序部分的正确位置。

插入排序的性能以及优缺点

插入排序的时间复杂度取决于输入数组的初始顺序：

• 最好情况：当数组已经是升序排列时，算法只需要进行 n-1 次比较和 0 次交换。时间复杂度为 O(n)。
• 最坏情况：当数组是降序排列时，每个元素都需要和已排序的所有元素比较，并移动到数组的首位。时间复杂度为 O(n^2)。
• 平均情况：在随机顺序的数组中，插入排序的平均时间复杂度也是 O(n^2)。

插入排序有以下优点：

• 简单直观，易于实现；
• 对于小规模数据或基本有序的数据效率较高；
• 是稳定排序算法，不会改变相同元素的相对位置；
• 可以用作其他复杂排序算法的子过程。

但插入排序也有一些缺点：

• 对于大规模乱序数组效率低下；
• 平均时间复杂度较高，不适合对大数据量进行排序。

结语

插入排序是一种简单但在某些情况下非常有效的排序算法，尽管它的平均时间复杂度为 O(n^2)，但对于小规模数据或基本有序的数据，它可能会比一些更复杂的排序算法表现得更好。

你可能还想关注其它 9 种排序算法：

1. C语言冒泡排序（附带源码和解析）
2. C语言快速排序（附带源码和解析）
3. C语言选择排序（附带源码和解析）
4. C语言希尔排序（附带源码和解析）
5. C语言归并排序（附带源码和解析）
6. C语言堆排序（附带源码和解析）
7. C语言计数排序（附带源码和解析）
8. C语言桶排序（附带源码和解析）
9. C语言基数排序（附带源码和解析）

声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。