Why is there a difference between two similar implementations of a 'for' loop?

问题: I'm trying to write an insertion sort method, and I have managed to finish it, but I don't understand why my first version cannot work correctly. Here's my first attempt:...

问题:

I'm trying to write an insertion sort method, and I have managed to finish it, but I don't understand why my first version cannot work correctly.

Here's my first attempt:

public static void insertionSort(int[] list) {
    for (int i = 1; i < list.length; i++) {
        int current = list[i];
        for (int k = i - 1; k >= 0 && current < list[k]; k--) {
            list[i] = list[k];
            list[k] = current;
        }
    }
}

public static void main(String[] args) {
    int[] list = {8, 22, 90, 10};
    insertionSort(list);
}

My output for the above code is: 8, 10, 10, 22

But the answer would be correct if the inside for-loop, at line 5, is changed from: list[i] = list[k]; to: list[k + 1] = list[k];

To my understanding, k + 1 is equal to i, but it must be different in loop counting and I can't figure out how. I have tried many sets of input, and only values that lie between the range of the 2 first indexes (in this case 8 and 22) would be incorrect.


回答1:

k + 1 is equal to i, but only in the first iteration of the inner for loop. int k = i - 1 is only run once per iteration of the outer for loop.

In the second iteration of the inner for loop, k is decremented but i is not. Therefore, k + 1 and i are not interchangeable inside the inner for loop.

// second iteration of the outer for loop, second iteration of the inner for loop:
list[i] = list[k]; // means "list[2] = list[0]
// whereas
list[k + 1] = list[k]; // means "list[1] = list[0]"
  • 发表于 2019-01-03 22:45
  • 阅读 ( 181 )
  • 分类:网络文章

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除