簡単
選択ソートは、配列から最大または最小の要素を選択し、キューの先頭または末尾の要素と相互作用させるプロセスです。
セレクション・ソートと呼ばれるのは、最初に行われるのがセレクション・プロセスだからです。
選択ソートの例
29,10,14,37,20,25,44,15という配列があった場合、どのように選択的にソートしますか？
アニメーションから始めましょう：
選別の原理は以下の通り：
8つの数字がある場合、7ラウンドの並べ替えが必要です。
例えば、最初のラウンドでは、ペアはすべてのデータを比較し、10の中で最も小さいものを見つけ、その10を配列の最初に入れます。
2巡目になると、配列の最初の要素である10はすでにソートされているので、2番目の位置から始めればよく、同様に2巡目では、次の要素の中で最も小さい14を見つけ、配列の2番目の位置に配置します。
7回にわたる類推による選別で、最終的な結果が出ました。
選択ソートJavaコードの実装
上記のロジックをJavaコードで実装すると以下のようになります：
public class SelectionSort {
public void doSelectionSort(int[] array){
log.info("ソート前の配列は次のようになる。:{}",array);
//すべてのラウンドを反復する外側ループ
for(int i=0; i< array.length-1; i++){
//内側ループで最小数を求める
int minIndex=i;
for(int j=i+1;j<array.length;j++)
{
if(array[j] < array[minIndex])
{
minIndex = j;
}
}
//各選択の後、minIndexがある要素とi番目の要素を入れ替える。
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
log.info("第{}ラウンドソート後の配列は次のようになる。:{}", i+1, array);
}
}
public static void main(String[] args) {
int[] array= {29,10,14,37,20,25,44,15};
SelectionSort selectionSort=new SelectionSort();
selectionSort.doSelectionSort(array);
}
}走行結果
選択的ソートの2番目のJava実装
上記のコードでは、最小の要素が毎回ルックアップされ、同様に最大の要素をルックアップすることができます。
public class SelectionSort1 {
public void doSelectionSort(int[] array){
log.info("ソート前の配列は次のようになる。:{}",array);
//すべてのラウンドを反復する外側ループ
for(int i=0; i< array.length-1; i++){
//内部ループで最大の数を求める
int maxIndex=0;
for(int j=0;j<array.length-i;j++)
{
if(array[j] > array[maxIndex])
{
maxIndex = j;
}
}
//各選択の後、maxIndexが位置する要素と長さ-i-1要素交換
int temp = array[array.length-i-1];
array[array.length-i-1] = array[maxIndex];
array[maxIndex] = temp;
log.info("第{}ラウンドソート後の配列は次のようになる。:{}", i+1, array);
}
}
public static void main(String[] args) {
int[] array= {29,10,14,37,20,25,44,15};
SelectionSort1 selectionSort=new SelectionSort1();
selectionSort.doSelectionSort(array);
}
}走行結果
どちらのソートでも、内部ループの比較条件が異なることに注意する必要があります。
選択ソートの時間複雑性
選択ソートもバブルソートと同様にn*n回のループを必要とするので、その時間複雑度はO(n²)となります。
この記事のコードアドレス
この記事は www.flydean.com/algorithm-s...
最も人気のある説明、最も深く辛口で簡潔なチュートリアル、そしてあなたが知らなかった数々のヒントが、あなたの発見を待っています！
