考研数据结构——C语言实现插入排序

插入排序是一种简单直观的比较排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place（原地排序），不需要额外的存储空间。插入排序对于小数据集或基本有序的数据集来说非常高效。

插入排序的步骤：

1. 将数组分为已排序和未排序两部分：初始时，已排序部分只包含第一个元素（或者为空），未排序部分包含其余元素。

2. 从未排序部分取出元素：每次从未排序部分取出第一个元素。

3. 在已排序部分找到插入位置：将取出的元素与已排序部分的元素进行比较，从后向前扫描。

4. 插入元素：找到合适的位置后，将取出的元素插入到该位置。

5. 重复以上步骤：直到未排序部分为空，此时整个数组已经排序完成。

插入排序的特点：

1. 稳定性：插入排序是稳定的排序算法，即相等的元素在排序后仍然保持其原始顺序。

2. 时间复杂度：

   • 最好情况：当数组已经是有序的，时间复杂度为O(n)。
   • 平均情况：时间复杂度为O(n^2)。
   • 最坏情况：当数组是逆序的，时间复杂度为O(n^2)。

3. 空间复杂度：插入排序是原地排序，不需要额外的存储空间，空间复杂度为O(1)。

4. 适用场景：对于小数据集或基本有序的数据集，插入排序是一个不错的选择。对于大数据集，插入排序可能不是最优的选择。

插入排序虽然在最坏情况下的时间复杂度较高，但由于其简单和稳定的特性，它在实际应用中仍然有其价值。

#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;
}

结果如下：