JAVA の単純な選択ソート アルゴリズムの原理と実装

単純な選択ソート: (最小値を選択して最初に配置し、その後、最初の値を後方に移動するなど) 最初の値と後続の値を 1 つずつ比較し、毎回最小値を先頭に配置します。 Post-advance に面する最初の値 (つまり、最初に選択された値は最小値であり、比較には参加しなくなり、比較の数は 1 つ減ります)

複雑さ: レコードの移動に必要な操作の数は 0--3(n-1) 未満です。レコードの最初の配置に関係なく、キーワード間で必要な比較の数は同じであり、n(n-1)/2 であり、合計の時間計算量は O( n2);
空間計算量 O(1)

アルゴリズムの改善: すべての比較は最小値を最初の位置に置くため、最後まで比較して最小値を見つけて、それを最初の位置に直接置くことができます。無意味な交換操作や移動操作が不要になります。また、方向を変更して、最後のビットを前のビットと比較して、毎回最大値が下に下がり、最後のビットが前に進むようにすることもできます。

JAVA ソース コード:

 public static void selectSort(Date[] days) {
  int min;
  Date temp;
  for (int i = 0; i < days.length; i++) {
   min = i;
   for (int j = min + 1; j < days.length; j++) {
    if (days[min].compare(days[j]) > 0) {
     min = j;
    }
   }
   if (min != i) {
    temp = days[i];
    days[i] = days[min];
    days[min] = temp;
   }
  }
 }
class Date {
 int year, month, day;
 Date(int y, int m, int d) {
  year = y;
  month = m;
  day = d;
 }
 public int compare(Date date) {
  return year > date.year ? 1 : year < date.year ? -1
    : month > date.month ? 1 : month < date.month ? -1
      : day > date.day ? 1 : day < date.day ? -1 : 0;
 }
 public void print() {
  System.out.println(year + " " + month + " " + day);
 }
}

単純選択ソート:

単純選択ソートはバブル ソートに似ており、毎回残りの要素セットから最大の値を選択して現在の位置に埋め込みます。唯一の違いは、バブル ソートは要素が現在の値より小さい (または大きい) ことが判明するたびに要素の位置を交換するのに対し、単純選択ソートは残りの要素の中から最も高い値を選択し、データを現在の値と交換することです。位置。

例えば、要素セット R={37, 40, 38, 42, 461, 5, 7, 9, 12} の場合

最初のソートでは、37 が 5 と直接交換されて、新しいシーケンス R1= が形成されます。 {5 ,40,38,42,461,37,7,9,12}
2 番目のソート パス: 40 が 7 と直接交換されて、新しいシーケンス R2={5,7,38,42,461,37,40, 9, 12}

これを最後の要素まで続けます（注: ソートの 2 回目のパスでは、38 は 42 より小さいですが、データは交換されません）。

以下は、単純選択ソートの Java 実装バージョンです:

　　public static void selectionSort（int[] data） {
　　if （data == null || data.length <= 1）
　　return;
　　int i, j, value, minPos, len = data.length;
　　int outer = len - 1, tmp;
　　for （i = 0; i < outer; i++） {
　　value = data[i];
　　minPos = -1;
　　for （j = i + 1; j < len; j++） {
　　if （data[j] < value） {
　　minPos = j;
　　value = data[j];
　　}
　　}
　　if （minPos != -1） {
　　tmp = data[i];
　　data[i] = value;
　　data[minPos] = tmp;
　　}
　　//            for （int k = 0; k < len; k++） {
　　//                System.out.print（data[k] + " , "）；
　　//            }
　　//            System.out.println（）；
　　}
　　}
　　public static void main（String[] args） {
　　int[] coll = {
　　37, 40, 38, 42, 461, 5,  7, 9, 12
　　};
　　selectionSort（coll）；
　　for （int i = 0; i < coll.length; i++） {
　　System.out.print（coll[i] + " , "）；
　　}
　　}

ツリー選択ソート (ツリー選択ソート)
単純選択ソートと比較して、ツリー選択ソート アルゴリズムは、空間と時間を交換する典型的なアルゴリズムです。このアイデアは、ソートされた N 個の要素を処理し、比較的小さな (n+1)/2 数値を構築し、次に要素が 1 つだけになるまで比較的小さな [n+1]/4 数値を構築することです。完全なバイナリ ツリーに構築されます。
ソートするときは、その要素が最小であるため、最小の要素を取り出し、その要素を「最大値」に置き換えて、完全な二分木を調整します。
以下はツリー選択ソートの Java 実装です:

　　public static void treeSelectionSort（int[] data） {
　　if （data == null || data.length <= 1）
　　return;
　　int len = data.length , low = 0 , i , j;
　　// add Auxiliary Space
　　int[] tmp = new int[2*len -1];
　　int tSize = tmp.length;
　　//construct a tree
　　for（i =len-1 , j=tmp.length-1;i >=0 ;i--,j--）{
　　tmp[j]=data[i];
　　}
　　for（i = tSize -1 ; i > 0 ; i-=2）{
　　tmp[（i-1）/2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];
　　}
　　//end
　　//remove the minimum node.
　　while（low < len）{
　　data[low++] = tmp[0];
　　for（j=tSize-1;tmp[j]!=tmp[0];j--）；
　　tmp[j] = Integer.MAX_VALUE;
　　while（j > 0）{
　　if（j%2 == 0）{  //如果是右节点
　　tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j = （j-1）/2;
　　}else{  //如果是左节点
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}
　　}
　　}

完全なバイナリ ツリーを構築する場合、N 要素のセットには 2*N -1 の補助スペースが必要です。
コード:

　　while（j > 0）{
　　if（j%2 == 0）{  //如果是右节点
　　tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j = （j-1）/2;
　　}else{  //如果是左节点
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}

は、新しい集合の最小値の再帰的構築を実現します。

JAVA の単純な選択ソート アルゴリズムの原理と実装に関連するその他の記事については、PHP 中国語 Web サイトに注目してください。