ソートアルゴリズム2:直接選択ソート

直接選択ソートアルゴリズムも単純で直感的なアルゴリズムであり,バブルソートアルゴリズムとはわずかな違いしかない.
その時間的複雑度はO(n^2),空間的複雑度O(1)であり,不安定な並べ替えである.(配列で不安定、チェーンテーブルで安定)

基本思想

ソートを直接選択するというのは、各ソートで最初に、ソートされていないキューのキューの先頭にあるIDを定義して、ソート中にソートされていないシーケンスの最大(小)値の位置を記録し、ソート中にソートされていないシーケンスの最大(小)値を直接選択し、ソート開始時に定義されたIDにその位置を記録することを考えているからです.最後に、識別された値を、ソートされていないキューヘッダの値と直接交換すると、このソートが完了します.交換時に判断する必要があり、自身がこのソートが秩序化されている(すなわち、識別された位置が変動せず、ソートされていないキューの先頭にある)場合、交換動作を行う必要はありません.

とバブルソートの違い

一言でまとめると、泡は1つのソートで複数回交換される可能性がありますが、選択したソートは1つのソートで最大1回しか交換されません.
簡単に言えば、バブルソートと似ています.同様に、外側層はソートされたキューを維持するために1つのループを使用します.ただし、バブルソートは、内側層で定義された2番目のレイヤループ(すなわち、各ソート)で隣接する要素を2つ比較し、必要に応じて交換します.最悪の場合、このソートは比較のたびに交換され、効率が非常に低下します.一方、直接選択ソートは、内層のループで行われ、このソートを開始する前に、ソートされていないキューのキューヘッダに位置する識別を定義します.ソートされていないキューの各数は、現在指定されている数と比較され、要求(たとえば、指定されている値よりも小さい)に達した場合、その数の下付きラベルが、そのソートが終了するまで指定されます.最後に、指定された数と現在のソートされていないシーケンスを識別するキューを交換し(このソート自体がソートされている場合は交換する必要はありません)、このソートを完了します.

具体的なコード(配列実装は小さいから大きいまで並べ替えられる)

void change(int arr[], int a,int b)
{
	int tmp;
	tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}

void SelectSort (int arr[],int len)
{
	for (int i = 0; i < len - 1 ;i++)		//i           ，i          
	{
		int min = i;						//min           
		for (int j = i + 1; j < len ; j++)  //for                    （min）
		{
			if(arr[j] < arr[min])
			{
				min = j;
			}
		}

		
		if (min != i)				//           ，            。
		{
			change(arr,i,min);
		}
	}
}

ここでchange()関数は2つの数を交換する関数である.配列int arr[]={2,4,6,0,1}で;の最初のソートで説明します.
まず関数はarrとその長さ5を取得し,SelectSortソート関数に入る.外層ループ定義iは、並べ替えられた数字を記録する一方で、並べ替えられていないシーケンスのキューヘッダの下付き文字としても存在する.
現在並べ替えられている数字は0で、並べ替えられていないキューヘッダはarr[0]、すなわち2である.最初のソートが開始されます.
まず、minを識別子として定義(本例では小さいから大きいまで並べ替え)、その初期位置が未並べ替えシーケンスヘッダである(arr[0]).
内層サイクルに入る:arr[i+1](すなわち4)からarr[len](すなわち1)の終了まで、各数字とarr[min]を比較する.現在のarr[j]このときminは2を指し,4からそれぞれ2と比較する.j=3すなわちarr[j]==0ループを終了するとminは3でありarr[3]を表すのが今回の中で最小の数である.
一つの判断を行い、minとiが等しくなければ今回の交換が確実に必要であることを表し、arr[i]とarr[min]を交換する.
arrは{0,4,6,2,1}である.
このようにして、次のサイクルに入り、min=1、arr[min]=4で、新しいラウンドの比較を行います...

その不安定性について

これは,配列{5,5,2}を与え,最初の比較後2が最初の5と交換して{2,5,5}となり,このとき2つの5の相対位置が変化したことを実証している.
ただし,チェーンテーブルでのソート選択は安定しているが,配列では不安定である.