java - 插入排序实现的区别

Question

我已经以两种不同的方式看到了插入排序的实现，如下所示，

方法一：

        for (int out = 1; out < numbers.length; out++) {

        int temp = numbers[out];
        int in = out - 1;
        while (in >= 0 && numbers[in] > temp) {

            numbers[in + 1] = numbers[in];
            numbers[in] = temp;
            in--;
        }

        }

方法二：

int S[] = { 20, 25, 10};
    int N = S.length;

    for (int i = 1; i < N; i++) {
        int j = i - 1;
        int temp = S[i];

        while (j >= 0 && S[j] > temp) {
        S[j + 1] = S[j];
        j--;
        }

        S[j + 1] = temp;
    }

但我不明白为什么交换在第二种方法中的while循环之外的原因？有没有理由让它在while循环之外？

Answer 1

这两个版本在功能上是等效的。后者只是避免做一些不必要的工作。

在第一个版本中，以下分配

numbers[in] = temp;

如果循环继续，将在循环的下一次迭代中撤消。temp第二个版本注意到了这个事实，并且在循环完成之前不会恢复恢复。

Answer 2

基本上两者是相同的，但在第一个中，您只需将临时编号立即写入您复制到元素 [in + 1] 的编号。在第二个中，你等到你的 while 循环完成。所以它只是节省了一些时间。