阅读量:0
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; }- 外层循环
for(i=1; i<len; i++)从数组的第二个元素开始遍历到数组的最后一个元素。i表示当前处理的元素索引。 t = a[i];将当前元素存储在临时变量t中。j = i;初始化j为当前元素的索引。 这一行代码用于初始化变量j，使其指向当前待插入的元素的索引。这样可以在接下来的while循环中逐步向前移动j，以找到合适的位置插入当前元素t。- 内层
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向前移动一位。
- 当找到
t应该插入的位置后，退出while循环，将t插入到a[j]位置，即a[j] = t;。
这种方法称为插入排序，因为它在每次迭代时都将当前元素插入到前面已排序的子数组中的适当位置。插入排序的平均和最坏时间复杂度为 O(n^2)，但对于小数组或几乎有序的数组，它是非常高效的
插入排序的工作原理
- 初始化：假设第一个元素（索引为 0 的元素）已经排好序，因此从第二个元素（索引为 1）开始处理。
- 遍历未排序部分：从左到右遍历数组中的未排序部分。
- 插入当前元素：将当前处理的元素插入到已排序部分的正确位置。
具体步骤
以一个数组
[12, 11, 13, 5, 6]为例：
- 初始数组是
[12, 11, 13, 5, 6]。- 认为第一个元素 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]- 处理下一个元素 13：
i = 2，t = a[2] = 13，j = 2- 比较 13 与 12，由于 13 > 12，不需要移动，数组保持不变。
- 处理下一个元素 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]- 处理最后一个元素 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 作为辅助变量是必要的，可以确保外层循环的正确性和内层循环的灵活性。
