选择排序(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
伪代码:1
2
3
4
5
6repeat (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++ 实现:1
2
3
4
5
6
7
8
9
10
11
12void 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]);
}
}