考研数据结构——C语言实现插入排序
插入排序是一种简单直观的比较排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place（原地排序），不需要额外的存储空间。插入排序对于小数据集或基本有序的数据集来说非常高效。
插入排序的步骤：
-
将数组分为已排序和未排序两部分：初始时，已排序部分只包含第一个元素（或者为空），未排序部分包含其余元素。
-
从未排序部分取出元素：每次从未排序部分取出第一个元素。
-
在已排序部分找到插入位置：将取出的元素与已排序部分的元素进行比较，从后向前扫描。
-
插入元素：找到合适的位置后，将取出的元素插入到该位置。
-
重复以上步骤：直到未排序部分为空，此时整个数组已经排序完成。
插入排序的特点：
-
稳定性：插入排序是稳定的排序算法，即相等的元素在排序后仍然保持其原始顺序。
-
时间复杂度：
- 最好情况：当数组已经是有序的，时间复杂度为O(n)。
- 平均情况：时间复杂度为O(n^2)。
- 最坏情况：当数组是逆序的，时间复杂度为O(n^2)。
-
空间复杂度：插入排序是原地排序，不需要额外的存储空间，空间复杂度为O(1)。
-
适用场景：对于小数据集或基本有序的数据集，插入排序是一个不错的选择。对于大数据集，插入排序可能不是最优的选择。
插入排序虽然在最坏情况下的时间复杂度较高，但由于其简单和稳定的特性，它在实际应用中仍然有其价值。
#include <stdio.h>
#include <stdlib.h>
int main() {
int a[] = { 12,4,132,55,46,232,789,1,0,98,523,666 };
int n = sizeof(a) / sizeof(a[0]);
int i, j, k;
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j >0 ; j--) {
if (a[j] < a[j - 1]) {
k = a[j - 1];
a[j - 1] = a[j];
a[j] = k;
}
else
break;
}
}
for (i = 0; i < n; i++) {
printf("%d", a[i]);
printf(" ");
}
return 0;
}结果如下：
