先来看对一组结构体数据排序:
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
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
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;
}
#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;
}
#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
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 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
排序后数据
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
排序后数据 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;
}
#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;
}
#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函数排序的方法,接下来介绍一些经典的排序算法,虽然实际编程的时候少用这些排序算法,但是大家要体会这些排序算法的思想,这对编程很有帮助!