Selection Sort

选择排序（Selection sort） 是一种非常简单且直观的排序算法，其主要思路是将数列中未排序部分的最小（大）元素与起始位置的元素进行交换，并放入已排序部分的末尾，直到完成排序。当未排序部分的第一个元素即为最小（大）元素时，算法仍然需要将该元素与未排序部分中的所有元素依次比较大小；而每次交换则至少有一个元素被放在正确位置，也就是说，对于一个有$N$个元素的数列，实际发生的交换次数最多为$N - 1$. 因此，算法性能是由数列元素的比较次数所决定的。对于一个有$n$个元素的数列来说，选择排序算法的时间复杂度总是$O(n^2)$. 总的来说，选择算法排序有两个明显特点：

• 运行时间与输入无关。无论输入数列是顺序的还是需要交换次数最多的，算法的时间复杂度都不变，仅与数列元素个数有关。
• 数据移动次数最少。对数列元素的交换次数和数列元素个数是线性关系。

举个例子，我们使用选择排序算法对数列$ \lbrace 4, 5, 3, 1, 2\rbrace $进行排序：

i	pos of min	array
0	3	4 5 3 1 2
1	4	1 5 3 4 2
2	2	1 2 3 4 5
3	3	1 2 3 4 5
4	4	1 2 3 4 5
5	0	1 2 3 4 5

Codes

伪代码：

repeat (num_of_elements - 1) times
	set the first unsorted element as the min
	for each of the unsorted elements
		if element < current_minimum
			set element as new minimum
	swap minimum with first unsorted position

C++ 实现：

void selection_sort(vector<int> vec)
{
	int len = vec.size();
	for (int i = 0; i < len - 1; ++i) {
		int min_pos = i;
		for (int j = i + 1; j < len; ++j) {
			if (vec[j] < vec[min_pos])
				min_pos = j;
		}
        swap(vec[min_pos], vec[i]);
	} 
}