所謂穩(wěn)定排序，是指對一個序列進(jìn)行排序之后，如果兩個元素的值相等，則原來亂序時在前面的元素現(xiàn)在（排好序之后）仍然排在前面。STL中提供stable_sort()函數(shù)來讓我們進(jìn)行穩(wěn)定排序。為了更好的說明穩(wěn)定排序的效果，我們定義了一個結(jié)構(gòu)體元素，一個value成員和一個index成員，前者表示元素的值，后者表示亂序時的索引。
stable_sort()內(nèi)部由歸并排序來實(shí)現(xiàn)。
//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;
}
程序的運(yùn)行結(jié)果如下圖所示，可以看到，對于元素值相同的元素，索引小的在前面，穩(wěn)定排序就是這么一個效果。
