为什么所有插入排序的解决方案都使用嵌套的 while 循环而不是嵌套的 for？

Question

我正在尝试一道插入算法题。但是，我有以下问题。

我想知道为什么大多数在线解决方案都使用嵌套 while 循环而不是嵌套 for 循环？我认为它可能必须做一些时间复杂度的事情，但是，两者都有 O(n^2) 复杂度。

下面我附上了两种不同的解决方案


public class InsertionSort { 
// MY method
    /*Function to sort array using insertion sort*/
    // void sort(int arr[]) 
    // { 
    //     int n = arr.length; 
    //     for (int i = 1; i < n; ++i) { 
    //         if(arr[i] < arr[i-1]){
    //             for(int j = 0; j < i; j++){
    //                 if(arr[i] < arr[j]){
    //                     int temp = arr[j];
    //                     arr[j] = arr[i];
    //                     arr[i] = temp;
    //                 }
    //             }
    //         }
    //     } 
    // } 

// Online Solution
  
    void sort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 1; i < n; ++i) { 
            int key = arr[i]; 
            int j = i - 1; 
  
            /* Move elements of arr[0..i-1], that are 
               greater than key, to one position ahead 
               of their current position */
            while (j >= 0 && arr[j] > key) { 
                arr[j + 1] = arr[j]; 
                j = j - 1; 
            } 
            arr[j + 1] = key; 
        } 
    }

Answer 1

通常在开发算法时，你会根据这个来选择循环：

如果迭代次数已知，使用for-loop.
如果迭代次数未知，请使用while-loop。

在 Java 和其他语言中，您可以使用两个循环实现相同的事情。迭代次数是否已知并不重要。不过，有道理，更readable/logical:

...对于一个已知的起始值到一个已知的极限做...
...while条件为真做...

在 pseudocode 中，这是一种独立于 implementation-details 描述算法的方式，通常是这样（或类似）的：

for i = 0 to n do
    ...

while condition do
    ...

当您查看 sort 时，您可以看到两个循环：外部 for-loop 和内部 while-loop。

外循环是 for-loop 因为 i 和 n 是已知的。值 n 是已知的，因为它由数组的大小给出，在该算法中这是一个常数。
内部循环是 while-loop，因为它不知道条件何时会失败，因为它取决于 array-access。你不知道价值观；如果你愿意，那么你可以通过硬编码一些交换来对数组进行排序。

为什么所有插入排序的解决方案都使用嵌套的 while 循环而不是嵌套的 for？

Why are all solutions for insertion sort using a nested while loop instead of a nested for?

java

algorithm

sorting

insertion-sort