選擇排序
假設一個待排序的序列中有 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 }