シンプルなソートアルゴリズム

現在の IT 業界は、以前ほど簡単ではありません。従業員が多すぎるため、若手プログラマーが余ってしまいます。これは間接的に、企業の採用基準がますます高くなり、プログラマーを必要とすることにもつながっています。より多くの知識を習得すること。

#アルゴリズムも長い間議論されてきたテーマですが、プログラマーはアルゴリズムを習得する必要がありますか?人によって答えは異なります。実際、多くの企業ではアルゴリズムに特定の要件を設けており、面接中に面接官にアルゴリズムの質問を直接手書きで要求する企業もあります。これはプログラマーの技術的要件に大きな試練を与えるため、今日の環境に直面して、将来の仕事に就くためにはアルゴリズムを習得する必要があります。

それでは、次に、いくつかの並べ替えアルゴリズムを簡単に紹介します。お役に立てれば幸いです。

バブル ソート

バブル ソート (バブル ソート) は、比較的単純な並べ替えアルゴリズムです。

ソート対象の要素の列を繰り返し訪問し、隣接する 2 つの要素を順番に比較し、順序 (大きいものから小さいもの、A から Z の最初の文字など) が間違っている場合はそれらを入れ替えます。要素を訪問する作業は、隣接する要素を交換する必要がなくなるまで繰り返されます。これは、要素列がソートされたことを意味します。

このアルゴリズムの名前は、炭酸飲料の二酸化炭素の泡が最終的には泡になるのと同じように、より大きな要素が交換 (昇順または降順) によってシーケンスの先頭にゆっくりと「浮く」という事実に由来しています。一番上にフロートするため、「バブル ソート」という名前が付けられています。

デモ:

コードは次のとおりです:

@Test
public void bubbleSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	// 统计比较次数
	int count = 0;
	// 第一轮比较
	for (int i = 0; i  arr[j + 1]) {
				// 交换位置
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
			count++;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("一共比较了:" + count + "次");
}

実行結果:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比较了:105次

Select sort

選択ソートは、シンプルで直感的な並べ替えアルゴリズムです。その動作原理は、まずソートするデータ要素から最小 (または最大) の要素を選択し、それをシーケンスの先頭に格納し、次にソートされていない残りの要素から最小 (最大) の要素を見つけて配置します。ソートされたシーケンスの最後。ソートされるすべてのデータ要素の数がゼロになるまで、同様に続きます。選択ソートは不安定なソート方法です。

デモ:

コードは次のとおりです:

@Test
public void SelectionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 0; i <p>実行結果: </p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

実装も次のとおりです。非常に単純です。まず第一に、インデックス変数は、i の値を格納するために外側のループで定義されます。これは、比較の各ラウンドの後、最初の i 要素がすでに並べ替えられているため、繰り返しの比較を避けるためです。もう一度比較して、「Just start i」から始めてください。以降の比較はすべてインデックス位置の要素に基づいて行われます。比較後のインデックス位置の要素が最小値の場合は、交換する必要はなく、移動しないでください。そして、インデックスの要素より小さい要素が見つかった場合は、その要素のインデックスをインデックスに代入し、比較が完了するまで比較を続けます。比較が完了した後に得られるインデックスは配列の最小値であり、このとき、インデックス位置の要素を位置 i の要素と交換するだけです。

挿入ソート

挿入ソートは、シンプルで直感的で安定した並べ替えアルゴリズムです。すでにソートされたデータ列があり、ソートされたデータ列に数値を挿入する必要があるが、挿入後もデータ列がまだ順序付けされている場合は、新しいソート方法である挿入が必要です。挿入ソートは、ソート済みの順序付きデータにデータを挿入し、数値に 1 を加えた新しい順序付きデータを取得するアルゴリズムです。このアルゴリズムは、少量のデータのソートに適しています。計算量は O(n ^2)。安定した選別方法です。挿入アルゴリズムは、ソートされる配列を 2 つの部分に分割します。最初の部分には、最後の要素を除く配列のすべての要素が含まれます (配列に挿入位置を追加するためのスペースが 1 つ増えます)。2 番目の部分には、この要素のみが含まれます。 1 つの要素 (つまり、挿入される要素)。最初の部分がソートされた後、この最後の要素がソートされた最初の部分に挿入されます。

挿入ソートの基本的な考え方は次のとおりです。各ステップで、ソート対象のレコードが、キー値のサイズに従って、すべてが挿入されるまで、前にソートされた配列内の適切な位置に挿入されます。

デモ:

コードは次のとおりです:

@Test
public void InsertionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 1; i = 0 && insertValue <p>実行結果:</p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

ここでは、配列要素 よくわからないので、配列の最初の要素を順序付けされたシーケンスとみなすことしかできません。そのため、挿入位置を見つける必要がある要素は配列の 2 番目の要素から始まります。したがって、外側のループは 1 から開始し、現在の 2 番目の要素である arr[i] を保存し、挿入される要素の前の要素の添え字 (i-1) を見つけます。このとき、while ループを通過します。比べる。

insertIndex が 0 未満の場合、前のすべての要素と比較されているため、ループを終了する必要があります。比較処理中に、挿入される要素が前の要素より小さい場合、前の要素は後方に移動されます。つまり、前の要素の値が挿入される要素の位置に直接割り当てられます。挿入する要素は最初に保存されているため、挿入する要素の値を前の要素に代入するだけで済みます。 insertIndex は while ループ内で自己減分操作を実行するため、その前の要素の添字は insertIndex 1 である必要があります。また、挿入される要素の値が前の要素よりも大きい場合は、while ループに入らないため、insertIndex 1 以降の位置は依然として独自の位置であるため、代入後も値は変わりません。後続の操作でも同様です。

以上がシンプルなソートアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。