选择排序
假设一个待排序的序列中有 n 个元素，从这 n 个元素中选出一个最小(大)的元素放在第 0 个元素的位置，再从余下的 n-1 元素中选出一个次小(大)的元素放在第 1 个元素的位置，继续这个过程...，经过 n-1 次选择和交换，整个序列成为一个升(降)序序列，这就是选择排序的排序过程。无论最好还是最坏情况，选择排序的时间复杂度始终为O(n2)，空间复杂度为O(1)，选择排序并不稳定。
以一个随机整数序列为例，选择排序过程见下表。
| 49 52 53 39 86 97 21 85 64 31 80 65 73 85 42 14 | 待排序序列 |
| 14 52 53 39 86 97 21 85 64 31 80 65 73 85 42 49 | 49 与14 交换后 |
| 14 21 53 39 86 97 52 85 64 31 80 65 73 85 42 49 | 52 与21 交换后 |
| 14 21 31 39 86 97 52 85 64 53 80 65 73 85 42 49 | 53 与31 交换后 |
| 14 21 31 39 86 97 52 85 64 53 80 65 73 85 42 49 | 39 无需交换 |
| 14 21 31 39 42 97 52 85 64 53 80 65 73 85 86 49 | 86 与42 交换后 |
| 14 21 31 39 42 49 52 85 64 53 80 65 73 85 86 97 | 97 与49 交换后 |
| 14 21 31 39 42 49 52 85 64 53 80 65 73 85 86 97 | 52 无需交换 |
| 14 21 31 39 42 49 52 53 64 85 80 65 73 85 86 97 | 85 与53 交换后 |
| 14 21 31 39 42 49 52 53 64 85 80 65 73 85 86 97 | 64 无需交换 |
| 14 21 31 39 42 49 52 53 64 65 80 85 73 85 86 97 | 85 与65 交换后 |
| 14 21 31 39 42 49 52 53 64 65 73 85 80 85 86 97 | 80 与73 交换后 |
| 14 21 31 39 42 49 52 53 64 65 73 80 85 85 86 97 | 85 与80 交换后 |
| 14 21 31 39 42 49 52 53 64 65 73 80 85 85 86 97 | 85 无需交换 |
| 14 21 31 39 42 49 52 53 64 65 73 80 85 85 86 97 | 85 无需交换 |
| 14 21 31 39 42 49 52 53 64 65 73 80 85 85 86 97 | 86 无需交换 |
| 14 21 31 39 42 49 52 53 64 65 73 80 85 85 86 97 | 排序完毕 |
1 template <typename ForwardIterator, typename Compare>
2 ForwardIterator selection(ForwardIterator first, ForwardIterator last, Compare cmp)
3 {
4 ForwardIterator next = first;
5 for(++first; first != last; ++first)
6 if(cmp(*first, *next))
7 next = first;
8 return next;
9 }
10
11 template <typename ForwardIterator, typename Compare>
12 void selection_sort(ForwardIterator first, ForwardIterator last, Compare cmp)
13 {
14 if(first == last || first + 1 == last) return;
15 for(ForwardIterator current = first; first != last; ++first, ++current)
16 {
17 ForwardIterator it = selection(first, last, cmp);
18 if(it != current)
19 swap(*current, *it); // 用于交换两个元素的swap函数实现见本主页快排的介绍
20 }
21 }