稳定排序与不稳定排序

先来看对一组结构体数据排序：

20
Name01 1
Name02 2
Name03 3
Name04 4
Name05 1
Name06 5
Name07 4
Name08 2
Name09 7
Name10 9
Name11 3
Name12 5
Name13 7
Name14 2
Name15 8
Name16 1
Name17 4
Name18 6
Name19 9
Name20 1

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500;
struct Node{
	string name;
	int n;
};
Node nodes[N+1]; 

void printArray(Node nodes[],int n){
	for(int i=0;i<n;i++){
		cout<<nodes[i].name<<"\t"<<nodes[i].n<<endl;
	} 
	cout<<endl<<endl;
}

//比较函数：升序排序
bool cmp(const Node &a,const Node &b){
	return a.n<b.n;
}

int main(){ 
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>nodes[i].name>>nodes[i].n;
	}
	
	//原始数据
	cout<<"原始数据"<<endl; 
	printArray(nodes,n);
	
	//升序排序
	cout<<"排序后数据"<<endl; 
	sort(nodes,nodes+n,cmp);
	printArray(nodes,n);
	return 0;
} 

程序运行结果如下（分两部分显示）：

原始数据
Name01  1
Name02  2
Name03  3
Name04  4
Name05  1
Name06  5
Name07  4
Name08  2
Name09  7
Name10  9
Name11  3
Name12  5
Name13  7
Name14  2
Name15  8
Name16  1
Name17  4
Name18  6
Name19  9
Name20  1

排序后数据
Name01  1
Name20  1
Name16  1
Name05  1
Name08  2
Name14  2
Name02  2
Name11  3
Name03  3
Name04  4
Name07  4
Name17  4
Name06  5
Name12  5
Name18  6
Name09  7
Name13  7
Name15  8
Name10  9
Name19  9

分析排序结果可知，按照结构体成员n升序排序，对于成员n相等的结构体数据，排序后没有维持原来的相对顺序（例如n=1的所有结构体数据，原始顺序是“Name01 1”、“Name05 1”、“Name16 1”、“Name20 1”，但是排序后顺序是“Name01 1”、“Name20 1”、“Name16 1”、“Name05 1”，排序后没有维持原来的相对顺序），像这样的排序结果是不稳定的。其实sort函数是不稳定的排序，对于“相等”的数据，不能保证排序结束后能够维持它们原来的相对顺序。

如果要实现稳定的排序（在一些特殊场合），那么可以用stable_sort函数替代sort函数。stable_sort函数的使用方法和sort完全相同，不过stable_sort是稳定排序。

其实我们还可以改造一下结构体和比较函数，让sort函数也能稳定：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500;
struct Node{
	int index;
	string name;
	int n;
};
Node nodes[N+1]; 

void printArray(Node nodes[],int n){
	for(int i=0;i<n;i++){
		cout<<nodes[i].name<<"\t"<<nodes[i].n<<endl;
	} 
	cout<<endl<<endl;
}

//比较函数：升序排序
bool cmp(const Node &a,const Node &b){
	//n相等，那么按照index（出现次序）升序排序，排序结果就稳定了 
	if(a.n==b.n) return a.index<b.index;
	return a.n<b.n;
}

int main(){ 
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		nodes[i].index = i;	 //index成员变量记录原始数据的出现次序 
		cin>>nodes[i].name>>nodes[i].n;
	}
	
	//原始数据
	cout<<"原始数据"<<endl; 
	printArray(nodes,n);
	
	//升序排序
	cout<<"排序后数据"<<endl; 
	sort(nodes,nodes+n,cmp);
	printArray(nodes,n);
	return 0;
} 

前面介绍了简单实用的使用算法库中的sort函数排序的方法，接下来介绍一些经典的排序算法，虽然实际编程的时候少用这些排序算法，但是大家要体会这些排序算法的思想，这对编程很有帮助！