algorithm - 简单代码及操作挑战(附图)

Question

我遇到了以下伪代码。这里 A 是一个整数数组:

for i = 1 to n 
{   
    j = i; f = 1;

    while ((j>1) and (f==1))
    {
        if (A[j]<A[j/2]) { swap(A[i], A[j/2]); j = j/2; } 
        else             { f = 0;                       }
    }  
}

我不明白为什么 A 的最小元素总是进入 A[1]。

事实上我有一个问题，这段代码如何改变A[1]？或者至少如果我正确理解这段代码的操作？

Answer 1

即使不清楚整数除法应该如何工作(3/2 == 1 或 3/2 == 2 ？)算法将始终移动数组第一个位置的最小值。

例如对于组成为 {4,5,6,2} 的数组，最后一个元素将首先移动到第二个位置并进行第一次交换(j==4 和i==4) 导致这种情况:{4,2,6,5}。当 j 将更新为 j/2 --> 2 时，数组 2 的第二个元素将与索引中的一个进行比较j/2 --> 1 并移动到第一个位置。这里出现了 split 的问题。

除法 1/2 表示风险，因为它可以转换为 0 导致调用 A[0] 并且导致 ArrayOutOfBoundException，但这是伪代码，如果您将除法的结果四舍五入，它就可以工作。