作者LPH66 (ゆびさきミルクティー)
看板CSSE
标题Re: [问题] 演算法 Insertion-Sort
时间Wed Apr 19 21:34:43 2006
※ 引述《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 红字表示排好的
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│
9│
15│
17│7│12│
└─┴─┴─┴─┴─┴─┘
下一轮的j是5
step 2: key ← A[5] = 7
step 3: i ← 5-1 = 4
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│
9│
15│
17│7│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
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│
9│
15│X│
17│12│
└─┴─┴─┴─┴─┴─┘
step 6: i ← i-1 = 3
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│
9│
15│X│
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
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│
9│X│
15│
17│12│
└─┴─┴─┴─┴─┴─┘
step 6: i ← i-1 = 2
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│
9│X│
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
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│X│
9│
15│
17│12│
└─┴─┴─┴─┴─┴─┘
step 6: i ← i-1 = 1
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│X│
9│
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
1 2 3 4 5 6
┌─┬─┬─┬─┬─┬─┐
│
4│7│
9│
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
1F:推 ZEROCC:感谢^^ 04/19 21:45