插入排序解释

Question

我想了解插入排序的代码，但我真的很困惑，我不明白代码中的 i、j、index 是做什么的。有人可以帮助我了解更多

Procedure InsertionSort(numbers : Array of Integer; size : Integer);
Var i, j, index : Integer


    Begin
     For i := 2 to size-1 do
      Begin
       index := numbers[i];
       j := i;
       While ((j > 1) AND (numbers[j-1] > index)) do
        Begin
         numbers[j] := numbers[j-1];
         j := j - 1;
        End;
       numbers[j] := index;
      End;

    End.

Answer 1

Imo，名称 index 可能有点误导。在这种情况下，我会称它为 currentValue 或类似的名称。也就是说：

想象一个 数字 -> [5, 3, 7, 2, 9, 1, 8, 4]

算法从 2 开始，所以：

i == 2; currentValue := numbers[i] (== 7)

现在算法将位于索引 (j) < i 中的所有值移动只要 j > 1 值 < 7 向上一个位置：

numbers[1] == 3 < 7 -> numbers[2] = 3
numbers[0] == 5 < 7 -> numbers[1] = 5

最后把currentValue写成numbers[0]。所以第一次通过后的结果是

[7, 5, 3, 2, 9, 1, 8, 4]

第二遍（2比之前的任何东西都小，所以没有任何反应）：

[7, 5, 3, 2, 9, 1, 8, 4]

第三遍（9是numbers[0]到numbers[4]中最大的元素）：

[9, 7, 5, 3, 2, 1, 8, 4]

等等...

插入排序解释

Insertion sort explanation

pascal

freepascal