选择排序详解(c语言)

一.选择排序的图解及原理

选择排序的原理：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
通俗的讲，就是先找最小，再找次小，再找次次小…主打一个暴力排序

对于所有的排序，我们都可以先实现单趟排序，选择排序也不例外，因此我们先实现单趟循环（即先找最小的元素放在第一个位置）
我们以一个数组为例：{ 4, 3, 1, 9, 6}

选择排序简单但是低效，尽管接下来的优化能好一点点

二.选择排序的代码

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		int mini = 0;               //最小元素的下标
		int j = 0;
		for (j = i+1; j < n; j++)   //i是来控制j的
		{
			if (a[j] < a[mini])
			{
				mini = j;
			}
		}
		Swap(&a[i], &a[mini]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三.选择排序的优化

1.原理

上面的选择排序每一次都找最小的，效率很低，但是我们可以在找小的同时找大，可以减少一半的遍历次数

int begin=0,end=n-1;
1

begin等价于上面代码的 i,end和begin的效果是一样的，只是因为我们要找大又找小，所以定义了两个变量~

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

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这段代码和上面代码逻辑是一样的，只不过两个变量要一起控制，理解之后也没有什么难度。但是这段代码与下面完整代码不同，我扣去了一段代码，那么我扣去的这段代码有什么作用呢？
试想排序这串数组： { 8 ，2 ，1 ，6 ，7 }

我们发现最大值的位置和最开始的位置重叠了，这时候代码就变成Bug代码了
执行完上面的代码就变成：

发现问题了吧，第一次交换完之后最大的元素的位置变了，但是第二次交换可不管这么多，不经过任何处理肯定会出错的
解决方案的话我们可以在第一次交换后面加上一层判断：

if (maxi == begin)
		{
			maxi = mini;
		}
1
2
3
4

结合上面的图例相信你能理解的很清楚

2.代码

int begin = 0, end = n - 1;

	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);

		++begin;
		--end;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

四.选择排序的时间复杂度

选择排序时间复杂度是经典的 O(n^2);
初始版本的执行次数：（n-1)+(n-2)+…+1
优化版本的执行次数：（n-1)+(n-3)+(n-5)+…1
可以发现优化版本好一点的原因就在于每次都少那么一点点次数，总体来说，
效率都是很低下的