欢迎您来到芯片的主页!

Welcome to Chipset's homepage!

选择排序

选择排序

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

posted on 2011-08-16 13:41 Chipset 阅读(201) 评论(0)  编辑 收藏 引用 所属分类: 算法和数据结构消遣


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理