算法介绍
一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序适用于小规模数据集或部分有序的数据，且实现简单，具有较低的常数因子。
不过对于大规模数据集，通常会选择更高效的排序算法，如快速排序或归并排序。
算法分析
核心思想
- 初始状态：将第一个元素看作一个已排序的子序列。
- 逐步插入：从第二个元素开始，依次将每个元素插入到已排序序列的适当位置。具体过程如下：
- 取出当前要插入的元素（称为"关键元素"）。
- 从后向前比较已排序部分的元素，找到第一个比关键元素大的位置。
- 将所有比关键元素大的元素向后移动一个位置，为关键元素腾出插入的位置。
- 将关键元素插入该位置。
- 重复这一过程，直到所有元素都被插入到已排序部分，排序完成。
图解运行过程
以数列 a[] = {40, 20, 30, 50, 10} 作为案例说明
分析：
第一轮（i = 1，当前元素为20）
- 已排序部分: {40}
- 未排序部分: {20, 30, 50, 10}
- 将20与已排序部分的元素（40）比较：
- 20 < 40，所以将40向后移动
- 将20插入到位置0
- 当前数组状态: {20, 40, 30, 50, 10}
第二轮（i = 2，当前元素为30）
- 已排序部分: {20, 40}
- 未排序部分: {30, 50, 10}
- 将30与已排序部分的元素比较：
- 30 < 40，因此40向后移动
- 30 > 20，所以插入于位置1
- 当前数组状态: {20, 30, 40, 50, 10}
第三轮（i = 3，当前元素为50）
- 已排序部分: {20, 30, 40}
- 未排序部分: {50, 10}
- 将50与已排序部分的元素比较：
- 50 > 40，所以插入于位置3
- 当前数组状态: {20, 30, 40, 50, 10}
第四轮（i = 4，当前元素为10）
- 已排序部分: {20, 30, 40, 50}
- 未排序部分: {10}
- 将10与已排序部分的元素比较：
- 10 < 50，因此50向后移动
- 10 < 40，因此40向后移动
- 10 < 30，因此30向后移动
- 10 < 20，因此20向后移动
- 将10插入到位置0
- 当前数组状态: {10, 20, 30, 40, 50}
算法稳定性和复杂度
稳定性
插入排序是一种稳定的排序算法。
在插入排序的过程中，当待插入元素与已有的元素相等时，插入排序会保持原有元素的相对位置。具体来说，待插入元素会被插入到第一个相等元素的右侧，而不会打乱已存在元素的前后顺序。
举个例子：
原始数组: [3a, 1, 4, 3b, 2]
经过插入排序的过程：
- 初始状态: [3a, 1, 4, 3b, 2]
- 排序过程中，3a 和 3b 的位置关系（相同值的前后相对关系）会被保留。
- 插入后的最终排序结果: [1, 2, 3a, 3b, 4]
空间复杂度
- 输入数据的存储空间:
排序时，插入排序会直接对输入数组进行操作，因此输入数据的存储空间不算在额外空间的复杂度中。通常我们假设输入数组的空间复杂度是
- 额外的辅助空间:
- 临时变量: 在插入排序中，通常会使用一个或多个临时变量来存储当前元素的值。例如，待插入的元素可以存储在一个变量中（例如 key），比较时可能还有一些索引变量（如循环计数器）。
- 常量级空间: 无论输入数据的规模有多大，插入排序所需的额外空间始终是常数级别的，因此与
n 无关。通常来说，我们只需要一些常量的额外空间，来存储几个变量。
由于插入排序在执行时只需要常数级别的额外空间，而不是依赖于输入的规模 n，所以我们说其空间复杂度为：O(1)
时间复杂度
最坏情况
最差情况发生在输入数组是逆序排列的情况下。此时，每次插入操作都需要将待插入的元素与已排序部分的每个元素进行比较，并且每个已排序元素都需后移以腾出位置。
基本操作：
元素的比较和移动。
- 对于第 i 个元素（其中1 =< i < n), 需要与之前的 i 个元素进行比较。
- 第1个元素不需要比较和移动。
- 第2个元素比较1次，移动1次。
- 第3个元素比较2次，移动2次。
- …
- 第i个元素比较i-1次，移动i-1次。
因此，对于n个元素的数组，总比较次数和总移动次数是：
总比较次数 = 1 + 2 + 3 + … + (n-1) = n(n-1)/2 总移动次数 = n(n-1)/2
操作次数：
总比较次数:
C ( n ) = 1 + 2 + 3 + … + ( n − 1 ) = n ( n − 1 ) 2 C(n) = 1 + 2 + 3 + … + (n-1) = \frac{n(n-1)}{2} C(n)=1+2+3+…+(n−1)=2n(n−1)
大O表示：
在最坏情况下，插入排序的时间复杂度为：T(n) = O( n 2 n^2 n2)
平均情况
平均情况通常考虑的是输入数组的顺序是随机的。这种情况下，每个待插入元素在已排序列表中的位置是随机的，大约一半的元素都已经在正确的位置上。
基本操作：
在平均情况下，每个元素大约需要比较一半的已排序部分的元素，并且平均移动一半的已排序部分的元素。
- 平均比较次数：对于每个元素，平均比较次数大约是n/2。
- 平均移动次数：与平均比较次数相同，也是n/2。
操作次数：
C ( n ) = ∑ i = 1 n − 1 i 2 = 1 2 ∑ i = 1 n − 1 i = 1 2 ⋅ ( n − 1 ) n 2 = ( n − 1 ) n 4 C(n)=\sum_{i=1}^{n-1}\frac{i}{2}=\frac{1}{2}\sum_{i=1}^{n-1}i=\frac{1}{2}\cdot\frac{(n-1)n}{2}=\frac{(n-1)n}{4} C(n)=i=1∑n−12i=21i=1∑n−1i=21⋅2(n−1)n=4(n−1)n
大O表示：
因此，在平均情况下，插入排序的时间复杂度仍然为：T(n) = O( n 2 n^2 n2)
代码实现
原汁原味地使用C语言徒手撸代码：
详细源码在我的 Github ，可以给个star ⭐️ ❤️
#include <stdio.h>/*** Insertion sort by C Lang.** params:* array -- the data need to sort* n -- the length of array*/
void insertSort(int arr[], int n)
{for (size_t i = 0; i < n; i++){// Current array elementint key = arr[i];int j = i - 1;// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current positionwhile (j >= 0 && arr[j] > key){// In the first loop: j + 1 equal to i, indicate that the sorted arr length increased by 1.arr[j + 1] = arr[j];j--;}// Put the key in the correct position of an sorted array.arr[j + 1] = key;}
}/*** show array*/
void printArray(int arr[], int n)
{for (size_t i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n\n");
}int main()
{int arr[] = {40, 20, 30, 50, 10};// calculate the length of a arrayint n = sizeof(arr) / sizeof(arr[0]);printf("before sort: \n");printArray(arr, n);insertSort(arr, n);printf("after sort: \n");printArray(arr, n);return 0;
}
