<分区>
我试图尝试一道插入算法题。但是,我有以下问题。
我想知道为什么大多数在线解决方案都使用嵌套 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;
}
}