1

私は擬似コードクラスを使用しており、7行目を除いて挿入ソートアルゴリズムを順守しています。これが何を意味するのか説明してもらえますか？この時点までの前の行は理にかなっています。6行目は、インデックス/プレースホルダーA[i]が右に1ステップ進むことを意味します。これは、「i<-i-1」については不明な次のステップです。

1 for j ← 2 to length[A]
2   do key ← A[j]
3     ▹ Insert A[j] into the sorted sequence A[1  j - 1].
4     i ← j - 1
5     while i > 0 and A[i] > key
6      do A[i + 1] ← A[i]
7         i ← i - 1
8     A[i + 1] ← key
4

2 に答える 2

0

i が 0 よりも大きい間、何らかの処理を行ってから、i から 1 を引きます。そうしないと、ループが永遠に続きます。（無限ループ）

于 2012-11-02T21:07:06.717 に答える
0

実際には、6 行目で次のセルの値が現在のセルの値に割り当てられます。行 7 は、インデックスを 1 つ戻します。実際には、ループ内で次のポイントに到達したとします。

(Assuming the first item is at index 1)
A = { 1, 2, 3, 4, 5, 6 }
i = 4

Line 6: Set A[i+1] to have the value of A[i]
        ==> A[5]                        A[4]
        ==> A = { 1, 2, 3, *5*, 5, 6 }

Line 7: Shift i to the next lower position
        ==> i = 3

この後、ループの最後に到達し、5 行目のループの先頭に戻り、ループの条件をテストして続行します。

于 2012-11-02T21:26:02.930 に答える