插入排序（Insertion Sort）

1. 算法简介

插入排序是一种简单直观的排序算法，其工作原理类似于整理扑克牌：每次将一张牌插入到已经排好序的牌中的适当位置。

• 分类：内部排序、比较排序、稳定排序
• 适用场景：数据量较小（例如 n < 1000）或数据基本有序的情况

2. 算法原理与步骤

以升序排序为例：

1. 初始状态：将第一个元素视为已排序区间 [0, 0]，剩余元素为未排序区间 [1, n-1]。
2. 第 i 轮（i 从 1 到 n-1）：
   • 取出未排序区间的第一个元素 key = arr[i]。
   • 在已排序区间从右向左依次比较，如果 arr[j] > key，则将 arr[j] 向右移动一位。
   • 找到合适的位置 j+1 后，将 key 插入。
3. 重复步骤2，直到所有元素都在已排序区间内。

3. 代码实现

 int arr[5] = {6, 3, 8, 2, 5}; // 假设5个数据
 for (int i = 1; i < 5; i++) {
     int key = arr[i];
     int j = i - 1;
     while (j >= 0 && arr[j] > key) {
         arr[j + 1] = arr[j];
         j--;
     }
     arr[j + 1] = key;
 }
 for (int i = 0; i < 5 - 1; i++) {
     cout << arr[i] << " ";
 }