java - 有序数组插入

Question

这是 Robert Lafore 所著的《Java 中的数据结构和算法》第二版的成果。我们正在处理一个有序数组，试图在数组中插入一个项目。我通常喜欢在编码时理解代码，但这似乎让我无法理解。我明白前半部分在做什么——寻找将值放在哪里。

现在从 for(int k=nElems; k>j; k--) 开始的第二部分是我陷入困境的地方。 我认为这就是它想说的:将 k 设置为等于原始数组的大小并递减，直到其 k 的大小为 j。将数组位置 k 设置为 k-1(或者可能是 j-1？)然后...然后我陷入 a[j] = value;。

有人可以解释一下那里发生了什么吗？我认为数组一旦创建就是不可变的。人们会认为将创建一个全新的阵列。

public void insert(long value)    // put element into array
{
int j;

for(j=0; j<nElems; j++)         // find where it goes
if(a[j] > value) // (linear search)
    break;

for(int k=nElems; k>j; k--)     // move bigger ones up
    a[k] = a[k-1];
a[j] = value;                   // insert it
nElems++;                       // increment size
} 

Answer 1

int k=nElems

从最后开始。

k > j

虽然我们还没有达到目标位置...

a[k] = a[k-1];

将当前元素向右移动一位。

k--

并向左移动。

<小时/>

因此，将目标位置和结束位置之间的所有元素向右移动。

I thought arrays were immutable once created.

数组大小一旦创建就固定了 - 任何索引处的元素都可以根据您认为合适的方式进行修改或重新分配。

这里可能做了什么 - 创建了一个更大的数组，并使用 nElems 来指示填充值的数量 - 其余索引将只是 null。 Wikipedia's article on dynamic arrays简要提及这一点 - 容量与大小的概念 - 容量为a.length，大小为nElems.这与 ArrayList 的方式相同。有效。