Блог

Я хочу использовать этот код для сортировки вставки, но он выдает несортированный вывод:

 function insertionSort(arr) {
    //insert each element in the right place in the sorted section
    for (let i=1;i<arr.length;i  ) {
        var currentValue = arr[i];
        for (var j=i-1; j>=0; j--) {
            if (arr[j]>currentValue) {
            arr[j 1]=arr[j];
            }
        }
        arr[j 1] = currentValue;
    }
    return arr;
}
  

Правильный код:

 function insertionSort(arr) {
    for (let i=1; i<arr.length; i  ) {
        let currentValue = arr[i];
        for (var j=i-1; j>=0amp;amp;arr[j]>currentValue; j--) {
            arr[j 1]=arr[j];
        }
        arr[j 1]=currentValue;
    }
    return arr;
}
  

Я просто не могу понять разницу в логике в этих двух кодах.

В правильном коде j-- for() цикл перестает уменьшаться. В вашем неправильном цикле j-- продолжается уменьшение до j = -1 . Поэтому, когда вы делаете:

 arr[j 1] = currentValue;
  

В правильном коде это было бы последнее значение j , когда if условие больше не выполняется.

В вашем коде это всегда будет:

 arr[0] = currentValue;
  

потому что значение j всегда -1 равно .

Вы можете исправить это с помощью break :

 if (arr[j]>currentValue) {
    arr[j 1]=arr[j];
}
else {
    break;
}
  

В первой реализации второй цикл for всегда выполняется до конца (пока «j» не равно 0). Поскольку затем вы используете ссылку на «j» после цикла для записи «currentValue» обратно, программа использует неправильный индекс. Во второй реализации цикл останавливается, когда следующая младшая запись в массиве не меньше, поэтому «j» остается с правильным индексом при обращении после цикла.

Как правило, не рекомендуется использовать итератор вне цикла именно по этой причине.