经典排序之选择排序(最大值、最小值)

选择排序(Select Sort):找到待排序数据里的最小值/最大值放入到对应位置。
假如待排序数据为12，8，1，9，3，我们假设开始时下标为0的元素是最大元素max。
第一趟：max是12，max跟8比，比8大，下标不改变，max跟1比，比1大，下标不改变，max跟9比，比9大，下标不改变，max跟3比，比3大，3是最后一个元素，则把max与3交换位置，即交换下标为0和下标为n-1的数据。
数据变成 3，8，1，9，12，且经过第一趟n-1的位置已经是最大值。
第二趟：max是3，下标为0，max跟8比，比8小，下标改变，下标变成1，即max现在是8，max跟1比，比1大，下标不改变，max跟9比，比9大，下标改变，下标变成3，max是9，下标3等于n-2，就相当于不发生改变。
数据变成 3，8，1，9，12，且现在最后两个位置已经放好
第三趟：max是3，下标为0，max跟8比，比8小，下标改变，下标变成1，即max现在是8，max跟1比，比1大，下标不改变，交换下标为1和下标为n-3的数据。
数据变成3，1，8，9，12，现在后三个位置都已经放好。
第四趟:max是3，下标为0，max跟1比，比1大，下标不改变，交换下标为0和下标为n-4的数据。
数据变成1，3，8，9，12，结束，即有n个数据的序列，需要n-1趟排序完成。

假定最大值代码如下：

void SelectSort(int arr[],int nlength)
{
	if(arr == NULL ||nlength <= 0) return;
	int nMax;
	int i;
	int j;
	for(i = 0;i < nlength-1;i++)  //要有n-1趟循环
	{
		nMax = 0;   //每次都假设下标为0的元素是最大值
		for(j = 0;j<nlength-i;j++)  //因为每1趟都会排好1个元素，则经过i趟以后就有i个排好的元素，每次后i个无需比较
		{
			if(arr[j] > arr[nMax])
			{
				nMax = j;
			
			}
		}
		//最大值放入相应位置
		if(nMax != nlength-i-1) //如果下标与除去遍历完的元素最后一个不同，交换
		{
			arr[nMax] = arr[nlength-i-1]^arr[nMax];
			arr[nlength-i-1] = arr[nlength-i-1]^arr[nMax];
			arr[nMax] = arr[nlength-i-1]^arr[nMax];
		
		}
	}
}

假定最小值代码如下：

void SelectSort(int arr[],int nlength)
{
	if(arr == NULL ||nlength <= 0) return;
	int nMin;
	int i;
	int j;
	for(i = 0;i<nlength-1;i++)
	{
		nMin = i;
		for(j = i+1;j<nlength;j++)
		{
			if(arr[j] < arr[nMin])
			{
				nMin = j;
			
			}
		}
		//最小值放入相应位置
		if(nMin !=i)
		{
			arr[nMin] = arr[i]^arr[nMin];
			arr[i] = arr[i]^arr[nMin];
			arr[nMin] = arr[i]^arr[nMin];
		
		}
	}

}