【排序算法】选择排序

一、定义：

        选择排序（Selection sort）是一种简单直观的排序算法。第一次从待排序的数据（元素）中选出最小（或最大）的一个元素，存放在数组的起始位置，然后再从剩余的没有排序的元素中寻找到最小（大）元素，然后放到已排序的数组的末尾。以此类推，直到全部待排序的数据元素的个数为零。对于数据量大的排序就没啥用了，排的比较慢。

二、原理：

1、 对于待排序的数组，我们从首元素开始，将首元素的下标用min记住，认为目前是最小的元素的下标；

2、开始遍历min所指向的元素后面的元素与每个元素和下标min所指向的元素进行比好，当遇到某个元素比min下标所指向的元素时，min里记录其下标，直到遍历结束为止。

3、此时找到了最小元素，和首元素（开始位置的元素）进行交换

4、首元素排序好，认为第一个元素为排序好的元素，进入第二次遍历，从未排序的元素开始（即该数组的第二个元素）将其下标用min记住，重复2-3，直到整个数组排序完成。

 动图用不了，画了遍历第一次的情况：

 三、时间复杂度：

无论最好还是最坏的情况都是O(N^2)

因为就算你是有序的也要遍历一遍，确认是否是最小的元素

 相同的100万个随机数据排序，选择排序和堆排和希尔排序进行比较效率，看结果就知道 为啥说选择排序用到的不多了吧，而且其稳定性也差；

四、代码：

这个是比较简单且没坑的写法！接下来还有一个思路

//交换数据
void Swp(int* p1, int* p2)
{
	assert(p1 && p2);
	int tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}
//选择排序：
void SelectSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int min = i;
		for (int j = i; j < n; j++)
		{
			if (a[j] < a[min])
			{
				min = j;
			}
		}
		Swp(&a[min], &a[i]);
	}
 
}

双向法