【排序算法】选择排序

一、定义：

选择排序（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]);
	}

}

双向法👉一次性排好2个，一个maxi，一个mini，初始状态时，maxi和mini一起出发✨

接下来就是和上面一样的思路，分别进行比较，找到各自对应的最大值和最小值

最小的元素到了首位置（begin），最大的到了尾位置（end）；然后对2者中间当成未进行排序的数据，再次重复进行上述操作；此时从未排序的数组从 下标1（begin+1）开始到下标4（end--）的位置结束；依次类推；

注意喽！！！实现这个时会出现一些问题哦！！不是这个方法不行，是个人没有考虑到方方面面！就是这个方法需要注意的地方

一般人写好一次排序的代码可能会是这样的写的，从end+1开始比较的，一看是和自己比较没有意义，当然如果没有就算了，建议先完善好第一趟，再去考虑整体代码，减低错误；ok 回归正轨；下面听我分析 go——>✨✨✨✨✨✨✨✨

写了一个例子（单趟啊），如果刚好出现这种情况时，是不是就和我想要的结果不一样了，交换以后又回到了交换前，此时不得发现我们得考虑maxi在头位置不变的情况那么是不是当 maxi==begin 且min = end 时是不是就是双方互相交换

本来么，一开始想到的是直接换2个元素，但是仔细一想，我是指向的下标，那我是不是给maxi的指向改下；互换一下就可以了！！👉👉👉👉这样写憋说还真有好处👍👍👍👍👍👍

✨好了，竟然我们能考虑了相等，为啥不考虑mini不在end的情况呢？？咦~~~对哦，mini不在end的位置是怎么交换的？？假设哈 🧑‍🎓🧑‍🎓咋看？？看下结果🫰 maxi指向的还是最大的

这个时候我们在将maxi指向的元素和end（最后的位置）进行交换问题就这么解决了!!!!!!!!!!!!

不知道有人会不会想如果mini在begin的位置（下标为0）呢？？？其实不用考虑了，因为我们考虑maxi在begin 是因为我们先将mini指向的元素和头位置交换，导致maxi丢掉了正确的指向，而mini指向begin时，不就是自己和自己交换么，不会影响双方的指向，当然不要考虑；没必要么

✨👉代码实现：

//交换数据
void Swp(int* p1, int* p2)
{
	assert(p1 && p2);
	int tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
			if (a[mini] > a[i])
			{
				mini = i;
			}
		}
		Swp(&a[mini], &a[begin]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swp(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}