選擇排序
假設(shè)一個(gè)待排序的序列中有 n 個(gè)元素，從這 n 個(gè)元素中選出一個(gè)最小(大)的元素放在第 0 個(gè)元素的位置，再?gòu)挠嘞碌?/span> n-1 元素中選出一個(gè)次小(大)的元素放在第 1 個(gè)元素的位置，繼續(xù)這個(gè)過(guò)程...，經(jīng)過(guò) n-1 次選擇和交換，整個(gè)序列成為一個(gè)升(降)序序列，這就是選擇排序的排序過(guò)程。無(wú)論最好還是最壞情況，選擇排序的時(shí)間復(fù)雜度始終為O(n2)，空間復(fù)雜度為O(1)，選擇排序并不穩(wěn)定。
以一個(gè)隨機(jī)整數(shù)序列為例，選擇排序過(guò)程見(jiàn)下表。
| 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 無(wú)需交換 |
| 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 無(wú)需交換 |
| 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 無(wú)需交換 |
| 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 無(wú)需交換 |
| 14 21 31 39 42 49 52 53 64 65 73 80 85 85 86 97 | 85 無(wú)需交換 |
| 14 21 31 39 42 49 52 53 64 65 73 80 85 85 86 97 | 86 無(wú)需交換 |
| 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); // 用于交換兩個(gè)元素的swap函數(shù)實(shí)現(xiàn)見(jiàn)本主頁(yè)快排的介紹
20 }
21 }