选择排序

假设一个待排序的序列中有 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 }