算法：爲什麼我需要將一個數組元素重新分配給一個變量？

Question

這裏算法很新穎。我開始看普林斯頓的算法與數據結構上課的時候教授給這個代碼：

public void union(int p, int q){ 

int pid = id[p]; 
int qid = id[q]; 

for(int i = 0; i <id.length; i++){ 
if (id[i] = pid) 
    id[i] = qid; 
} 

他說，你需要先分配ID [P]爲PID。這是爲什麼？爲什麼你不能只使用id [p]？另外，我開始閱讀Introduction to Algorithms，並看到了插入排序的實現。我注意到，不是僅僅使用A [j]，而是將它分配給'鑰匙'。這是出於與上述相同的原因嗎？謝謝！

INSERTION-SORT.A/ 
1 for j = 2 to A.length 
2 key = A[j] 
4 i = j - 1 
5 while i>0 and A(i) > key{ 
6 A(i+1) = A(i) 
7 i=i-1} 
8 A[i+1] = key 

Answer 1

您必須將該元素複製到臨時變量中，因爲該值將在算法的後期階段被覆蓋。

考慮你的建議的版本：

for(int i = 0; i <id.length; i++){ 
    if (id[i] == id[p]) { 
     id[i] = id[q]; 
    } 
} 

當i等於p，然後id[p]將通過id[q]值覆蓋。現在被遺忘的原始id[p]，算法的其餘部分將產生錯誤的結果。試試看！

是的，在插入排序中，我們需要保存A [j]的原始值，原因相同：元素值被覆蓋，否則我們會丟失原始值。