stable_sort的含义

stable_sort的含义

所谓稳定排序，是指对一个序列进行排序之后，如果两个元素的值相等，则原来乱序时在前面的元素现在（排好序之后）仍然排在前面。

STL中提供stable_sort()函数来让我们进行稳定排序。

为了更好的说明稳定排序的效果，我们定义了一个结构体元素，一个value成员和一个index成员，前者表示元素的值，后者表示乱序时的索引。

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;struct TagNode
{int value;int index;
};bool myCmp(const TagNode &a, const TagNode &b)
{return a.value < b.value;	//升序排列
}bool myCmp2(const TagNode &a, const TagNode &b)
{return a.value > b.value;	//降序排列
}int main(int argc, char **argv)
{vector<TagNode> coll;TagNode 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<TagNode>::iterator pos;for(pos = coll.begin(); pos != coll.end(); ++pos){cout << pos->index << "\t" << pos->value << endl;}system("pause");return 0;
}