25.选择排序

从前有个王国，国王骄奢无度，贪图女色，后宫佳丽三千，但还是动用大量财力物力在全国范围内招妃纳妾，浸淫于女色之中。

又是一年的选妃开始，今年国王对身高比较敏感，要求这些候选者按照从低到高的顺序排列，供其选择。。。

宫廷首席太监小桂子于是命令所有小公公把宫女的身高都量出来并上报到他处，然后命令身为太监伴读小书童的你帮他按身高大小排好序，数据如下：

常规思维：
第一步先找出所有候选美女中身高最高的，与最后一个数交换

第二步再找出除最后一位美女外其它美女中的最高者，与倒数第二个美女交换位置

第三步 再找出除最后两位美女外其它美女中的最高者，与倒数第三个美女交换位置，因为倒数第三个本身已是最大的，所以实际无需交换。

。。。。。。重复以上步骤，直到最后只剩下一人，此时，所有的美女均已按照身高由矮到高的顺序排列

代码实现:

#include <stdio.h>
#include <stdlib.h>

void swap(int* num1, int* num2)//交换两个指针保存的值
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

void SelectSort1(int arr[], int len)
{
	for (int i = 0; i < len - 1; i++) 
	{
		int max = 0;
		for (int j = 1; j < len - i; j++) //查找未排序的元素
		{ 
			if (arr[j] > arr[max])  //找到目前最大值
			{
				max = j;
			}
		}

		//printf("max: %d beauties %d\n", max,len-i-1);

		if (max != (len - i - 1)) 
		{
			swap(&arr[max], &arr[len - i - 1]);
		}
	}
}

void SelectSort2(int arr[], int len) 
{
	int i, j;

	for (i = 0; i < len - 1; i++)
	{
		int min = i;
		for (j = i + 1; j < len; j++) //查找未排序的元素
		{ 
			if (arr[j] < arr[min])//找到目前最小值
			{ 
				min = j; //记录最小值
			}
		} 
		swap(&arr[min], &arr[i]); //交换
	}
}

int main()
{
	int beauties[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 };

	int len = sizeof(beauties) / sizeof(beauties[0]);

	/*
	for (int i = 0; i < len - 1; i++)//len个元素，执行len-1次选择
	{
		int max = 0;

		for (int j = 1; j < len - i; j++)//查找未排序元素
		{
			if (beauties[j] > beauties[max])
				max = j;//找到未排序元素中的最大值
		}

		if (max != len - i - 1)//把最大值和倒数第一个待处理元素交换
		{
			swap(&beauties[max], &beauties[len - i - 1]);
		}
	}
	*/

	SelectSort2(beauties, len);

	printf("美女排序以后的结果是：\n");
	for (int i = 0; i < len; i++)
	{
		printf("%d ", beauties[i]);
	}


	system("pause");
	return 0;
}

参考资料来源：

奇牛学院