白話の経典のアルゴリズムのシリーズの4直接選択の並べ替えと2つのデータの正確な実現を交換します

直接選択ソートは、直接挿入ソートと同様に、データを秩序化領域と無秩序化領域に分けます.異なるのは、直接再生ソートは、無秩序化領域の最初の要素を秩序化領域に直接挿入してより大きな秩序化領域を形成し、直接選択ソートは、無秩序化領域から最小の要素を選択して秩序化領域の最後に直接配置します.
 
配列をa[0...n-1]とする.
1.初期のとき、配列はすべて無秩序領域でa[0..n-1]であった.i=0
2.無秩序領域a[i...n-1]で最小の要素を選択し、a[i]と交換する.交換後a[0...i]は秩序化領域を形成する.
3.i++は、i=n−1になるまで第2のステップを繰り返す.並べ替えが完了しました.
 
直接選択ソートは間違いなく最も容易に実現され、以下にコードを示します.

void Selectsort(int a[], int n)
{
	int i, j, nMinIndex;
	for (i = 0; i < n; i++)
	{
		nMinIndex = i; //        
		for (j = i + 1; j < n; j++)
			if (a[j] < a[nMinIndex])
				nMinIndex = j;

		Swap(a[i], a[nMinIndex]); //             
	}
}

ここでは、Swap()の実装に注意してください.

inline void Swap(int &a, int &b)
{
	int c = a;
	a = b;
	b = c;
}

笔记试験の面接の时に试験して中间のデータの交换の2つの数を使わないで、多くの人はあげました

inline void Swap1(int &a, int &b)
{
	a ^= b;
	b ^= a;
	a ^= b;
}

ネットで検索すると、このような書き方もたくさん見つかります.しかし、このように書くと、a,bが同じ数を指す場合、Swap 1()関数を呼び出すと、この数は0になります.次のようになります.

int i = 6;
Swap2(i, i);
printf("%d %d
", i);

もちろん誰もプログラムの中でこのようなコードを書くことはありませんが、私たちのSelectsort()に戻って、a[0]が最小の数であれば、交換時にa[0]を0にする場合があります.このようなエラーはデバッグしても発見しにくいと信じています.そのため、交換2数の関数を以下のように書くことをお勧めします.

inline void Swap(int &a, int &b)
{
	int c = a;
	a = b;
	b = c;
}

あるいはSwap 1()に判断を加え、2つのデータが等しい場合は交換しなくてもよい.

inline void Swap1(int &a, int &b)
{
	if (a != b)
	{
		a ^= b;
		b ^= a;
		a ^= b;
	}
}