守望

Here we go!
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  0 随笔 :: 6 文章 :: 0 评论 :: 0 Trackbacks
[排序]选择排序(Selection sort)
第一步，选择一个最大的元素，放在列表的尾端。
第二部，从第0个到第n-1个元素中选择一个最大的，放在列表倒数第二个位置。
。。。。。
 1template <class Record>
 2void SelectionSort(Record *array, int count)
 3{
 4    for (int i = count - 1; i > 0; --i)
 5    {
 6        int max = MaxKey(Record *array, 0, i);
 7        Record tmp = array[max];
 8        array[max] = array[i];
 9        array[i] = tmp;
10    }
11}
12
13template <class Record>
14int MaxKey(Record *array, int low, int high)
15{
16    int largest = low;
17    for (int cur = low + 1; cur <= high; ++cur)
18    {
19        if (array[largest] < array[cur])
20        {
21            largest = cur;
22        }
23    }
24
25    return largest;
26}

时间复杂度：
比较：1/2n^2 + O(n)
赋值：O(n)

稳定性：
不稳定。
但把19行的条件改为
if (array[largest] <= array[cur])
就是稳定的了
posted on 2011-10-03 14:59 winter 阅读(171) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理