插入排序：为什么我们将 j 减一？

Question

为什么我们将 j 减一 (j--)？它实际上有什么作用？

void sort(int arr[])
{
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Answer 1

让我们考虑一个 12,45,51,23,19,8 的数组。 子数组 12,45,51 已经排序。 23 应放在 12 旁边。 要将 23 放在 12 旁边，我们需要移动 45,51 的位置

// In Case of i=3 
key=23
j=2

最后进入 while 循环第一时间

array=12,45,51,51,19,8
key=23
j=1

第二次进入最后的 while 循环内部

array=12,45,45,51,19,8
key=23
j=0

并结束 while 循环

arr[j + 1] = key; //this statement gets executed

之后数组=12,23,45,51,19,8。 因此 j-- 语句有助于更改数组中元素的位置