插入排序實現差異

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循環結束。所以這只是節省一些時間。