日本語
日本語
Simple Selection Sortingは、さまざまなデータを効果的に処理できる直感的で一般的に使用されるソートアルゴリズムです。コアのアイデアは、毎回ソートされる要素から最小値を選択し、ソートされたシーケンスの最後に配置することです。特定のプロセスは次のとおりです。最初に配列全体で最小の要素を選択し、最初の位置を交換し、2回目は残りの要素から最小値を選択し、2番目の位置を交換し、すべての要素がソートされるまで。
最初に配列長nを取得し、次にn-1ラウンド選択操作を実行します。選択の各ラウンドでは、アンソートされていない部分から最小値を見つけ、現在のラウンドの開始位置で要素と交換して、ローカル注文を達成し、最終的に全体的なソートを完了します。
以下は、Algorithmの特定の実行プロセスの理解を容易にするPHP実装の単純な選択のサンプルコードです。
function selectionSort(&$arr)
{
$len=count($arr);
for($i=0;$i<$len-1;$i++)
{
$min=$i; // 現在の要素が最小値位置であると仮定します
for($j=$i+1;$j<$len;$j++) // 後続の要素からより小さな値を見つけます
{
if($arr[$j]<$arr[$min])
{
$min=$j; // 最小値位置を更新します
}
}
if($min!=$i) // 位置が変更されたときに要素を交換します
{
$temp=$arr[$min];
$arr[$min]=$arr[$i];
$arr[$i]=$temp;
}
}
}
シンプルな選択ソートには、選択のn-1ラウンドが必要であり、各ラウンドでは残りの要素間で最小値が見つかります。したがって、比較数は約n²/2であり、動きの数は初期データ順序によって異なります。合計時間の複雑さはO（n²）です。それにもかかわらず、データのボリュームが小さいか、基本的に順序付けられている場合、アルゴリズムはまだ実用的です。
このアルゴリズムは、1つの一時変数のみを使用して交換を支援し、非常に小さなスペースのオーバーヘッドとOの空間的複雑さを備えています。
Simple Selection Sortingは、不安定なソートアルゴリズムです。同じ要素は、ソートプロセス中に位置を交換するため、相対順序を変更する可能性があります。たとえば、シーケンス5 8 5 2 9では、交換の最初のラウンドの後、最初の要素5を持つ最小の要素2の後、5の同じ位置順序が破壊されます。
