我试了一下第二层for循环改为j = i - 1； j >= 0; j-- 然后执行if（arr[i]<arr[j]）就交换为什么不能排序呢

来源：2-5 插入排序法 - Insertion Sort

huaju

2017-03-29

代码如下

for(int i = 1; i < n; i++)
    for(int j = i - 1; j >= 0; j --)
        if(arr[i] < arr[j])
            swap(arr[i], arr[j]);

写回答

1回答

liuyubobobo

2017-03-29

已采纳

以3 2 1为例，走一遍程序你就理解了：）

首先，i = 1时，j = 0，arr[i] = arr[1] = 2 < arr[j] = arr[0] = 3 交换arr[0]和arr[1]，此时数组变成2 3 1

当数组为2 3 1以后，此时开始i=2的第二重循环

首先，j = 1，arr[i] = arr[2] = 1 < arr[j] = arr[1] = 3 交换arr[2]和arr[1]，此时数组变成2 1 3

然后，j = 0，arr[i] = arr[2] = 3 > arr[j] = arr[0] = 0，不作任何交换。排序结束。

最终，我们获得的数组是2 1 3。

关键在于，当arr[i]和arr[j]交换以后，i位置的元素发生了改变：）

很多时候，当不知道程序为什么出错的时候，找一个小的测试用例，仔细跟一下程序，看看程序到底发生了什么，数据在现有的逻辑下是怎么一步步改变的，是非常有意义的。调程序一定要耐心，不能想当然。这可是计算机专业的硬本领：）

huaju

谢谢老师！！

2017-03-30

共1条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 2

回答 3

回答 2

回答 1