推 ZEROCC:感謝^^ 04/19 21:45
※ 引述《ZEROCC (ZEROCC)》之銘言：
: 1 for j←2 to length[A]
: 2 do key ← A[j]
: 3 i ← j-1
: 4 while i > 0 and A[i] > key
: 5 do A[i+1] ← A[i]
: 6 i ← i-1
: 7 A[i+1] ← key
: 好像是很基本的東西 可是我有問題@@
: Step 6 是必要的嗎?
: Step 7 可以改成 A[j] ← key 嗎?
畫個圖就知道了
這是某個陣列做完j=4的A 紅字表示排好的
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│９│15│17│７│12│
└─┴─┴─┴─┴─┴─┘
下一輪的j是5
step 2: key ← A[5] = 7
step 3: i ← 5-1 = 4
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│９│15│17│７│12│
└─┴─┴─┴─┴─┴─┘
↑
A[i]
step 4: while i>0 and A[i]>key (i=4>0 and A[4]=17>7)
step 5: do A[i+1] ← A[i] = 17
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│９│15│Ｘ│17│12│
└─┴─┴─┴─┴─┴─┘
step 6: i ← i-1 = 3
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│９│15│Ｘ│17│12│
└─┴─┴─┴─┴─┴─┘
↑
A[i]
step 4: while i>0 and A[i]>key (i=3>0 and A[3]=15>7)
step 5: do A[i+1] ← A[i] = 15
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│９│Ｘ│15│17│12│
└─┴─┴─┴─┴─┴─┘
step 6: i ← i-1 = 2
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│９│Ｘ│15│17│12│
└─┴─┴─┴─┴─┴─┘
↑
A[i]
step 4: while i>0 and A[i]>key (i=2>0 and A[2]=9>7)
step 5: do A[i+1] ← A[i] = 9
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│Ｘ│９│15│17│12│
└─┴─┴─┴─┴─┴─┘
step 6: i ← i-1 = 1
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│Ｘ│９│15│17│12│
└─┴─┴─┴─┴─┴─┘
↑
A[i]
(到這裡你應該可以發現為什麼step 6有必要了)
step 4: while i>0 and A[i]>key (i=1>0 and A[1]=4<7)
step 7: A[i+1] ← key = 7
１ ２ ３ ４ ５ ６
┌─┬─┬─┬─┬─┬─┐
│４│７│９│15│17│12│
└─┴─┴─┴─┴─┴─┘
↑ ↑ ↑
A[i] A[i+1] A[j]
(這裡不能改成A[j]的原因: 注意此時j是幾? 是5啊
如果改成A[j]就會寫錯地方)
--
"LPH" is for "Let Program Heal us"....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.54