Javaコードと擬似コードを使用して挿入ソートを実装する

挿入ソートの紹介:

ほとんどの人がポーカーをプレイしたことがあると思いますが、多くの人はカードが配られたときにカードを手札に加え、オーダーするのが好きです。カードを順番に置きます。空の左手から始めて、カードはテーブルの上にあります。次に、テーブルからカードを 1 枚ずつ取り出し、左手の所定の位置に挿入します。カードの正しい位置を見つけるには、すでに手札にあるすべてのカードと右から左に比較します。

おすすめの Java 関連の無料ビデオ チュートリアル: Java 無料のビデオ チュートリアル

疑似コード:

INSERTION-SORT(A)	//A是数组
 for j = 2 to A.length
key = A[j]
//(将A[j]插入排序序列A[1..j-1])
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key

Java コード:

//升序排序
public void InsertSortAscending(int[] A){
		for(int j = 1;j < A.length;j++){
			int key = A[j];
			//将A[j]插入排序序列A[1..j-1]
			int i = j - 1;
			while(i >= 0 && A[i] > key){
				A[j+1] = A[i];
				i = i - 1;
			}
			A[i+1] = key;
		}
}

挿入ソートの実行手順を見てみましょう

配列 A[2,4,7,1,3,6] を例として使用します

for ループでは、黄色の四角形が A[j] の値で、7 行目の while ループでは、左側の青い四角形の値と比較されます。青い矢印は、配列が 8 行目で 1 つ右に移動されることを示し、黄色の矢印は、キーワードが 11 行目で移動される場所を示します。

最初のサイクル: 以下の図に示すように:

2 番目のサイクル: 以下の図に示すように:

注: ここで、A[2] は A[1] より大きいです。A[1] は確実に A[0] より大きいため、A[2] を比較する必要はありません。 】A[1]サイズとなります。条件が満たされないため、while ループは終了します。

3 番目のサイクル: 以下の図に示すように:

4 番目のサイクル: 以下の図に示すように:

5 番目のサイクル: 次の図に示すように:

A 配列は次の図のようになります:

6 番目のループでは、j は 6 であり、ループ j

推奨される Java 関連記事チュートリアル: Java エントリー プログラム

以上がJavaコードと擬似コードを使用して挿入ソートを実装するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。