直接选择排序

​ 直接选择排序是比较简单的一个种排序算法。它的基本思路是：先定义一个参数tmp,用来存储较小的数的位置，先把最左边的数的位置放入，然后用第一个数与第二个数比，把较小的数的位置放入tmp中，第一次遍历完后，tmp为最小数的位置，所以把tmp位置的与第一个数交换。然后再从第二个数开始，以此类推，就能比较完成。

例子：用直接选择排序（升序）36 80 45 66 22 16 36 9

#include 
#include 
template 
void print(const Type *arr, const int size)
{
	for (int i = 0; i < size; i++)
	{
		std::cout << arr[i] << " ";
	}
	std::cout << std::endl;
}
template 
void straighSelectSort(Type *arr, const int size)
{
	Type min;
	for (int i = 0; i < size - 1; i++)
	{
		min = i;
		for (int j = i + 1; j < size; j++)
		{
			if (arr[i] > arr[j])
			{
				min = j;
			}
		}
		if (min != i)
			std::swap(arr[i], arr[min]);
	}
}
int main()
{
	int arr[] = {1, 7, 5, 2, 3, 88, 9};
	int size = sizeof(arr) / sizeof(arr[0]);
	straighSelectSort(arr, size);
	print(arr, size);
	return 0;
}

直接选择排序存在大跨度的数据移动，是一种不稳定的排序方式，它的平均时间复杂度是O(n^2),空间复杂度为O(1)。