woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

STL stable_sort 稳定排序

所谓稳定排序,是指对一个序列进行排序之后,如果两个元素的值相等,则原来乱序时在前面的元素现在(排好序之后)仍然排在前面。STL中提供stable_sort()函数来让我们进行稳定排序。为了更好的说明稳定排序的效果,我们定义了一个结构体元素,一个value成员和一个index成员,前者表示元素的值,后者表示乱序时的索引。

stable_sort()内部由归并排序来实现。

//Coded by 代码疯子

//http://www.programlife.net/

#include <iostream>

#include <vector>

#include <algorithm>

#include <iterator>

using namespace std;

 

typedef struct TagNode

{

        int value;

        int index;

}Node;

 

bool myCmp(const Node& a, const Node& b)

{

        return a.value < b.value;

}

 

int main(int argc, char **argv)

{

        vector<Node> coll;

        Node tmp;

        int idx = 0, num;

 

        while(cin >> num && num)

        {

               ++idx;

               tmp.value = num;

               tmp.index = idx;

               coll.push_back(tmp);

        }

 

        stable_sort(coll.begin(), coll.end(), myCmp);

 

        cout << "Index\tValue:" << endl;

        vector<Node>::iterator pos;

        for(pos = coll.begin(); pos != coll.end(); ++pos)

        {

               cout << pos->index << "\t" << pos->value << endl;

        }

 

        return 0;

}

程序的运行结果如下图所示,可以看到,对于元素值相同的元素,索引小的在前面,稳定排序就是这么一个效果。

clip_image001

 

posted on 2011-02-17 10:39 肥仔 阅读(5165) 评论(1)  编辑 收藏 引用 所属分类: Boost & STL

评论

# re: STL stable_sort 稳定排序  回复  更多评论   

哦哦,说得很好,^_^
2011-07-23 00:49 | xingyezhi

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理