8-6选择排序-简单选择排序

原理（从小到大）：每轮从待排序的序列中选择最小的元素放到前面

一.具体实现和效率分析
第一轮：默认0号位的49最小，从1号位开始遍历列表，找到最小的元素13，与0号位的49交换
代码：

int min = 0;
for (int j = 0 + 1; j < n; j++)
	{
		if (a[j] < a[min]) min = j;
	}
if(min!=0) swap(a[min], a[0]);
1
2
3
4
5
6

其中swap为交换函数
原理

void swap(int &a, int &b)
{
	int t;
	t = a;
	a = b;
	b = t;
}
1
2
3
4
5
6
7

第一轮结束，此时有一个元素放到了正确的位置上

第二轮，排1-7，设1最小，从2开始遍历
找到最小的27，与1号位的38交换
代码：

int min = 1;
		for (int j = 1 + 1; j < n; j++)
		{
			if (a[j] < a[min]) min = j;
		}
		if(min!=1) swap(a[min], a[1]);
1
2
3
4
5
6

第二轮结束

第三轮，找到最小的38，与65交换

第四轮，有两个49，选择左边的49，与97交换

第五轮，选择49与76交换

第六轮，选择65，与97交换

第七轮，选择76，与97交换

剩最后一个元素，无需处理。
因此对n个元素一共需要n-1趟的处理（图中8个元素7趟）

可以看出，第一轮处理了n-1个元素，第二轮处理了n-2个元素，最后处理了1个元素。因此处理次数=n-1+n-2+…+1=n(n-1)/2，总的元素交换次数不会超过3(n-1)次（含swap中temp的交换）。可以看出，复杂度主要取决于元素的处理次数（比较次数），而该算法中元素是逐个比较的，因此该算法元素的比较次数与初始序列无关，算法的时间复杂度与初始序列无关

所以总的时间复杂度为O(n²)
空间复杂度为O(1)

通过一下三个元素的排序，可以看出该算法是不稳定的

二.代码实现

#include
#include
using namespace std;
void SelectSort(int a[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[min]) min = j;
		}
		if(min!=i) swap(a[min], a[i]);
	}
}
int main()
{
	int a[5] = { 432,21,46,4322,645 };
	SelectSort(a, 5);
	for (int i = 0; i < 5; i++)
	{
		cout << a[i] << " ";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

该算法也适用于链表

三.总结