插入排序算法

for(i=1;i<len;i++)
{
    t = a[i];
    j = i;
    while(j>0 && t<a[j-1])
    {
        a[j] = a[j-1];
        j--;
    }
    a[j] = t;
}

1. 外层循环 for(i=1; i<len; i++) 从数组的第二个元素开始遍历到数组的最后一个元素。i 表示当前处理的元素索引。
2. t = a[i]; 将当前元素存储在临时变量 t 中。
3. j = i; 初始化 j 为当前元素的索引。 这一行代码用于初始化变量 j，使其指向当前待插入的元素的索引。这样可以在接下来的 while 循环中逐步向前移动 j，以找到合适的位置插入当前元素 t。
4. 内层 while 循环的条件是 j > 0 && t < a[j-1]，即当前元素 t 需要插入到前面已经排序的部分。只要 j 大于 0 且 t 小于前一个元素 a[j-1]，就执行循环体：
   • a[j] = a[j-1]; 将前一个元素 a[j-1] 向后移动一位，使得 a[j] 位置腾出来。
   • j--; 将 j 向前移动一位。
5. 当找到 t 应该插入的位置后，退出 while 循环，将 t 插入到 a[j] 位置，即 a[j] = t;。

这种方法称为插入排序，因为它在每次迭代时都将当前元素插入到前面已排序的子数组中的适当位置。插入排序的平均和最坏时间复杂度为 O(n^2)，但对于小数组或几乎有序的数组，它是非常高效的

插入排序的工作原理

1. 初始化：假设第一个元素（索引为 0 的元素）已经排好序，因此从第二个元素（索引为 1）开始处理。
2. 遍历未排序部分：从左到右遍历数组中的未排序部分。
3. 插入当前元素：将当前处理的元素插入到已排序部分的正确位置。

具体步骤

以一个数组 [12, 11, 13, 5, 6] 为例：

1. 初始数组是 [12, 11, 13, 5, 6]。
2. 认为第一个元素 12 已经排好序，从第二个元素 11 开始：
   • i = 1，t = a[1] = 11，j = 1
   • 比较 t 与 a[j-1] 即 11 与 12，由于 11 < 12：
     • 将 12 向后移一位，数组变为 [12, 12, 13, 5, 6]
     • j 减 1，j = 0
   • 将 11 放到 a[0]，数组变为 [11, 12, 13, 5, 6]
3. 处理下一个元素 13：
   • i = 2，t = a[2] = 13，j = 2
   • 比较 13 与 12，由于 13 > 12，不需要移动，数组保持不变。
4. 处理下一个元素 5：
   • i = 3，t = a[3] = 5，j = 3
   • 比较 5 与 13，由于 5 < 13：
     • 将 13 向后移一位，数组变为 [11, 12, 13, 13, 6]
     • j 减 1，j = 2
   • 比较 5 与 12，由于 5 < 12：
     • 将 12 向后移一位，数组变为 [11, 12, 12, 13, 6]
     • j 减 1，j = 1
   • 比较 5 与 11，由于 5 < 11：
     • 将 11 向后移一位，数组变为 [11, 11, 12, 13, 6]
     • j 减 1，j = 0
   • 将 5 放到 a[0]，数组变为 [5, 11, 12, 13, 6]
5. 处理最后一个元素 6：
   • i = 4，t = a[4] = 6，j = 4
   • 比较 6 与 13，由于 6 < 13：
     • 将 13 向后移一位，数组变为 [5, 11, 12, 13, 13]
     • j 减 1，j = 3
   • 比较 6 与 12，由于 6 < 12：
     • 将 12 向后移一位，数组变为 [5, 11, 12, 12, 13]
     • j 减 1，j = 2
   • 比较 6 与 11，由于 6 < 11：
     • 将 11 向后移一位，数组变为 [5, 11, 11, 12, 13]
     • j 减 1，j = 1
   • 将 6 放到 a[1]，数组变为 [5, 6, 11, 12, 13]

插入排序的核心思想是在每一步中，将当前元素插入到它在已排序部分的正确位置。已排序部分随着每次迭代逐渐增大。

使用 j 的优势

• 灵活性：j 可以在 while 循环中自由移动，而不影响 i 的值。这样可以在内层循环中处理元素移动和插入操作。
• 代码清晰度：将 j 和 i 分开，使代码逻辑更清晰，内层 while 循环专注于找到插入位置，外层 for 循环专注于遍历所有元素。

如果我们直接使用 t < a[i-1] 而不引入 j，代码逻辑会出现问题，因为 i 是外层循环控制变量，不能在内层循环中灵活移动，否则会破坏外层循环的遍历顺序。i 的值在 while 循环中被改变，会导致外层 for 循环无法正确遍历所有元素，最终结果是错误的。因此，引入 j 作为辅助变量是必要的，可以确保外层循环的正确性和内层循环的灵活性。