Как понять изменение значения ключа в сортировке вставки?

Question

Я знаю, что такое вставка, но я не понимаю код. И я искал это все объяснения о сортировке, но не код. Мне будет легче, если вы ответите на вопрос шаг за шагом с примерами! Спасибо! Используйте этот код для примера. Я оставил свои вопросы в комментариях, чтобы прояснить ситуацию.

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;

       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
 /* if arr[j] > key, at here arr[j+1] has the number in arr[j] which is i
  * or key right? But now only arr[j+1] changed. There are only two same
  * numbers which is the bigger number, arr[j] is not changed to the smaller
  * number which arr[j+1] was.
  */
           j = j-1;
       }
       arr[j+1] = key;    
 /* so at here arr[j+1] now has the value of key which is arr[i], so the 
  * sorted arr[j+1] ended up unchanged? I know this step is supposed to 
  * change key to use it to compare numbers after.
  */
   }
}

Answer 1

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

• Переменная внешнего цикла i, представляет начало несортированных данных в массиве. Будет увеличен с 1 в n сквозь for loop
• key представляет первый элемент из несортированной области, которую мы пытаемся поместить в правильное место после while loop отделки
• j представляет последний индекс в отсортированном регионе. Это будет уменьшено до 0 через while loop

Основная идея состоит в том, чтобы вставить следующий элемент в несортированную часть, сдвигая вправо требуемые элементы от отсортированной части до конечной позиции этого нового элемента.

Теперь на ваши вопросы

если arr[j] > key, здесь arr[j+1] имеет номер в arr [j]

ДА

что я или ключ верно?

NO. arr[j+1] == keyтолько во время первой итерации, а не после

Но теперь изменился только arr[j+1].

Да и Нет. За одну итерацию цикла только arr[j+1] изменилось, но в следующей итерации, когда j = j -1, предыдущий элемент меняется или скорее is shifted right

Есть только два одинаковых числа, которые являются большим числом, arr[j] не изменяется на меньшее число, которое было arr[j+1].

В данной итерации arr[j] не меняется, но это не значит, что arr[j] не изменяется в следующей итерации. Например, скажем, j = 10 текущая итерация так a[10] не изменяется в этой итерации цикла while, но может измениться в следующей итерации, когда j = 9 а также a[10] = a[9]

поэтому здесь arr[j+1] теперь имеет значение ключа arr[i]

Нет, arr[i] потенциально перезаписывается первой итерацией цикла while и, следовательно, резервируется в key

так что отсортированный arr[j+1] остался без изменений? Я знаю, что этот шаг должен изменить ключ, чтобы использовать его для сравнения чисел после.

Это неверно на основе вышеуказанного ответа

Answer 2

То, что вы называете ключом, является временной переменной, хранящей значение i-го элемента. Я загружаю изображение, которое может помочь вам лучше понять его.

рассмотрим массив A[]={7,4,5,2}

Смотрите, вы инициализировали переменную i с 1, поэтому key = arr [i] = arr 1= 4, другими словами, key теперь равно 4. А также j=i-1, который будет равен 0. Так что переходим к следующему утверждению while(j>=0 &&arr[j]>key) это проверяет, положит ли j сначала положительно, а затем проверяет, больше ли значение, сохраненное в j-й позиции в массиве (в данном случае arr[0]=7), чем значение ключа, тогда цикл инициируется, и теперь внутри тела цикла arr[j+1]=arr[j] в этом выражении элементу arr [j + 1], который равен arr 1, присваивается значение arr [0], равное 7. После этот переход к следующему утверждению j затем уменьшается на 1, так что теперь j равно -1. Из-за чего цикл while прервется, поскольку первое условие теперь ложно. Теперь, выходя из цикла, мы видим, что arr [j + 1], который будет равен arr [0], теперь присваивается "ключевое" значение, равное 4. Точно так же каждый раз, когда есть условие, где значение предыдущего элемента (чья позиция определяется по i) больше, чем значение текущего элемента (положение которого определяется по j) в массиве, в котором он поменяется местами. Если когда-либо условие для цикла (arr[j] > key) не выполняется, то выражение arr[j+1]=key ничего не будет значить, потому что j + 1 будет тогда равно i. И значение не изменится.