【数据结构与算法】常见排序算法（Sorting Algorithm）-4. 直接选择排序（Selection Sort）

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，逐步向后存放。

数据较为有序的情况下，直接选择排序选要比冒泡、直接插入排序慢。

void SelectionSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int min = begin, max = end;
		for (int i = begin; i <= end; ++i)
		{
			if (a[i] < a[min]) min = i;
			if (a[i] > a[max]) max = i;
		}
		Swap(&a[begin], &a[min]);
		if (max == begin)
		{
			max = min;
		}
		Swap(&a[end], &a[max]);
		++begin; --end;
	}
}

在优化版中，必须有这样一个判断max==begin，并更新max的下标值！最小的数a[min]换到了左边begin位置，如果最大的数的下标max正好等于begin，那就出现这种问题：最大的数a[max]已经被换到min下标位置了，即a[min]才是最大数；而本来a[max]是最大的数，由于max==begin，而经过前面a[begin]与a[min]交换的影响，导致a[begin]/a[max]变成了最小的数，不加判断并更新max的后果是把最小的数放在右边end位置了。