Java ソートアルゴリズムの概要 (II): 選択ソート

選択ソートの基本的な操作は、ソートするデータ要素から毎回最小（または最大）の要素を選択し、ソートするすべてのデータ要素がソートされるまで、ソートされたシーケンスの最後に順番に配置することです。このアルゴリズムは不安定で、追加スペースが O(1)、比較に O(n^2) の時間計算量、スワップに O(n) の時間計算量があり、適応性がありません。ほとんどの場合は推奨されません。これは、スワップの数を減らしたい場合にのみ使用してください。

基本的な考え方

n 個のレコードを持つファイルの直接選択ソートは、n-1 個の直接選択ソートによってソートされ、順序付けられた結果を得ることができます。

①初期状態：順序付けされていない領域はR[1..n]であり、順序付けされた領域は空である。

②1次選別

順序付けられていない領域R[1..n]内で最小のキーワードを持つレコードR[k]を選択し、それを順序付けられていない領域の最初のレコードR[1]と交換します。これにより、R[1..1]とR[2..n]は、それぞれレコードが1つ多い新しい順序付けられた領域と、レコードが1つ少ない新しい順序付けられていない領域になります。

…

③ i番目のソート

i番目のソートが開始されると、現在の順序付けされた領域と順序付けされていない領域はそれぞれR[1..i-1]とR(1≤i≤n-1)になります。このソートパスは、現在の順序付けられていない領域から最小のキーワードを持つレコード R[k] を選択し、それを順序付けられていない領域の最初のレコード R と交換します。これにより、R[1..i] と R は、それぞれレコードが 1 つ多い新しい順序付けられた領域と、レコードが 1 つ少ない新しい順序付けられていない領域になります。

この方法では、n 個のレコードを持つファイルの直接選択ソートを n-1 回の直接選択ソートでソートして、順序付けられた結果を得ることができます。

コードの実装

公共 クラステスト{
公共 静的  int [] a = { 10 , 32 , 1 , 9 , 5 , 7 , 12 , 0 , 4 , 3 }; // プリセットデータ配列 
公共 静的  void main(文字列args[]) {
 int i; // ループカウント変数 
 int Index = a.length; // データインデックス変数 
 System.out.print( "ソート前: " );
 (i = 0 ; i < インデックス - 1 ; i++)の場合
System.out.printf( "%3s" , a);
 System.out.println( "" );
 SelectSort(Index - 1 ); // 選択ソート 
 // ソートされた結果 
 System.out.print( "ソート後: " );
 (i = 0 ; i < インデックス - 1 ; i++)の場合
System.out.printf( "%3s" , a);
 System.out.println( "" );
 }
公共 静的  void SelectSort( intインデックス) {
 int i, j, k; // ループカウント変数 
 int MinValue; // 最小値変数 
 int IndexMin; // 最小インデックス変数 
 int Temp; // 一時変数 
 ( i = 0 ; i < インデックス - 1 ; i++) {
 MinValue = 32767 ; //現在の最小値 
 IndexMin = 0 ; // 最小値のインデックス値を保存します 
 (j = i; j < Index; j++)の場合{
 if (a[j] < MinValue) // 最小値を見つける 
 {
 MinValue = a[j]; // 最小値を保存する 
インデックス最小値 = j;
 }
 Temp = a; // 2つの値を交換する 
ア = ア;
 a = 温度;
 }
 System.out.print( "ソート: " );
 (k = 0 ; k < インデックス; k++)の場合
System.out.printf( "%3s" , a[k]);
 System.out.println( "" );
 }
 }
 }

選択ソート法はバブルソート法と同じです。最も外側のループは依然として n-1 回実行する必要があり、効率は依然として悪いです。

【編集者のおすすめ】

1. 5.5.5 直接選択ソートの使用
2. C# アルゴリズムの選択ソートの簡単な分析
3. C++ ソートの 4 つの選択ソートによる古典的な 4 つの講義