※ 引述《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