排序算法入门：直接插入排序详解

概述

在排序算法的大家庭中，直接插入排序是一种兼具直观性和实用性的基础算法。它的核心思想源于日常生活中整理数据的习惯 —— 就像我们玩扑克牌时，会把新摸到的牌按顺序插入到手中已排好的牌堆里，这种 “边插入边排序” 的逻辑正是直接插入排序的精髓。

算法核心思想

直接插入排序的核心逻辑可以概括为：将数组分为 “已排序区” 和 “未排序区”，每次从 “未排序区” 取第一个元素，插入到 “已排序区” 的合适位置，使 “已排序区” 始终保持有序。随着插入操作的重复，“已排序区” 从数组头部开始逐渐扩大，最终覆盖整个数组，完成排序。

算法步骤详解

我们以该数组为例

1. 初始化数组
   数组的首个元素我们认为其为天然有序的，即其已经处于“已排序区”，其余元素均在“未排序区”

2. 取未排序元素
   遍历到新元素时，将其从数组中“取出”，作为待排元素

3. 寻找插入位置
   将待排元素与已排序区的元素做比较

4. 移动与插入
   将已排序区比待排元素大的元素向后移动，腾出位置

5. 重复操作
   重复2-4，直到数组有序。此处我再用一次排序举例帮助你理解，后续的排序你自己能够轻易完成。
   
   
   
   

代码实现

void InsertionSort(int arr[], int n)
{
	for (int i = 1; i < n; i++)
	{
		if (arr[i - 1] > arr[i])
		{
			int tmp = arr[i];
			int j = i - 1;
			while (arr[j] > tmp && j >= 0)
			{
				arr[j + 1] = arr[j];
				j--;
			}
			arr[j + 1] = tmp;
		}
	}
}

代码细节

while (arr[j] > tmp && j >= 0)
// 而不是while (arr[j] > arr[j+1] && j >= 0)

我直接说如果是后者会发生什么
在插入25时，如果是arr[j] > arr[j+1]，会导致元素移动提前结束
对比
这个问题聪明如你不一定能遇到，我写出来是因为我犯蠢写出来了，记录下来警示自己。

arr[j + 1] = tmp;
// 是arr[j + 1]而不是arr[j]

这个问题我也遇到过，上面的例图中我没有加上j，下面我以第一次插入为例，看一遍你就能理解

加上循环就很很好理解吧

分析

最坏情况：完全逆序，时间复杂度O(n^2)
最优情况：已经有序，时间复杂度O(n)

优点：

• 实现简单
• 稳定性好
• 高效处理接近有序数据

缺点：

• 不适合大规模数据

总结

直接插入排序以其简单直观的逻辑和对接近有序数据的高效处理，成为排序算法中的基础经典算法。虽然它在大规模数据排序中表现不佳，但在小规模场景或作为优化手段时依然具有重要价值，是理解 “插入式” 排序思想的最佳入门案例。