英文:
Why does insertion sort work only if we use while as an inner loop and doesn’t work for ” for loop”?
问题
我试图尝试一个插入排序算法的问题。然而,我有以下问题。
我想了解为什么大多数在线解决方案使用嵌套的while循环而不是嵌套的for循环?我认为这可能与时间复杂度有关,然而,两者的时间复杂度都是O(n^2)。
下面我附上了两种不同的解决方案。
public class InsertionSort {
// 我的方法
/*使用插入排序对数组进行排序的函数*/
// 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;
// }
// }
// }
// }
// }
// 在线解决方案
void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* 将arr[0..i-1]中大于key的元素向前移动一个位置,直到其当前位置的前一个位置 */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
英文:
I was trying to attempt a insertion algorithm question. However, I had the following question.
I wanted to nderstand why most solutions online use a nested while loop instead of a nested for loop? I thought it might have to do something with time complexity, however, both have a O(n^2) complexity.
Below I have attached the two different solutions
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;
}
}
答案1
得分: 2
通常在开发算法时,您会根据以下情况选择循环结构:
- 如果迭代次数已知,请使用 for 循环。
- 如果迭代次数不已知,请使用 while 循环。
在 Java 和其他编程语言中,您可以使用这两种循环结构来实现相同的功能。无论迭代次数是否已知,都没有关系。然而,从逻辑/可读性的角度来看,以下方式更合理:
- ... 对于已知起始值到已知限制的范围,执行 ...
- ... 当条件为真时,执行 ...
在伪代码中,伪代码是一种在不涉及实现细节的情况下描述算法的方式,通常就是这样写的(或类似写法):
对于 i 从 0 到 n,执行
...
当条件成立时,执行
...
当您查看 sort
算法时,会看到两个循环:外部的 for 循环和内部的 while 循环。
- 外部循环是一个 for 循环,因为
i
和n
是已知的。值n
是已知的,因为它由数组的大小给出,在这个算法中是一个常数。 - 内部循环是一个 while 循环,因为不知道条件何时失败,这取决于数组访问。您不知道这些值;如果知道的话,就可以通过硬编码一些交换来对数组进行排序。
英文:
Usually, when developing algorithms, you choose a loop based on this:
- If the number of iterations is known, use a for-loop.
- If the number of iterations is not known, use a while-loop.
In Java, and other languages, you can implement the same thing using both loops. It doesn't matter if the number of iterations is known. However, it makes sense, it's more readable/logical:
- ... for a known starting value to a known limit do ...
- ... while a condition is true do ...
In pseudocode, which is a way to describe an algorithm independently of implementation-details, it's often done just like that (or similar):
for i = 0 to n do
...
while condition do
...
When you look at sort
, you can see two loops: the outer for-loop and the inner while-loop.
- The outer loop is a for-loop because
i
andn
are known. Valuen
is known because it's given by the size of the array, which is a constant in this algorithm. - The inner loop is a while-loop because it's not known when the condition will fail, as it depends on an array-access. You don't know the values; if you would, then you could sort the array by hardcoding some swaps.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论