插入排序实现差异

Question

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

方法1：

 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--; 
     } 

     } 

方法2：

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循环结束。所以这只是节省一些时间。