sort函数对数组排序

在生活中，我们往往需要排序，例如考试结束后老师会按照成绩高低排序确定名次，对每天要完成的工作按照紧急程度排序后优先完成急需完成的工作。排序就是将杂乱无章的无序的数据按照某种规则整理使这些数据有序。

一、sort函数对数组排序

排序的算法很多，这里先介绍一个实用的专门用来排序的 sort 函数，后面的章节会介绍一些实用的排序算法供大家学习其中的思想。

一般我们将要排序的数据存放在数组中，使用 algorithm（算法）头文件中的 sort 函数可以很方便地对数组中的数据排序。例如对 int 数组中的数据按照从小到大（升序）的顺序排序：

#include<iostream>
#include<algorithm>    //使用sort函数要引入algorithm头文件
using namespace std;
int main()
{
	const int N = 10;
	int a[N] = {5,8,3,4,9,2,6,7,1,10};
	
	for(int i=0;i<N;i++) cout<<a[i]<<" ";
	cout<<endl;
	
	sort(a,a+N);
	
	for(int i=0;i<N;i++) cout<<a[i]<<" ";
	cout<<endl;
	return 0;
} 

sort(a,a+N);可以将a数组中a[0]到a[N-1]的所有元素从小到大排序。其实sort函数的前两个参数都是指针，指定了排序的开始位置和结束位置（不包括结束位置），从而就指定了排序的区间。

如果我们使用sort(a+2,a+7);，那么将会对将a数组中a[2]到a[6]的所有元素从小到大排序（因为排序区间不包括第二个参数所以这里不包括a[7]）。

注意，这里的sort函数的时间复杂度是 \(O(n\log{n})\)，相比较其它排序算法，效率已经很高了。不过sort函数默认的是从小到大排序（升序排序，严格地说是非降序排序），如何实现从大到小排序（降序排序）呢？其实排序函数还可以有第三个参数，这个参数很特别，是一个函数的名称，称为比较函数。通过指定sort函数第三个参数，可以实现灵活的自定义排序，当然从大到小排序更不在话下：

#include<iostream>
#include<algorithm>
using namespace std;

//用来指定sort排序规则的比较函数
//因为要对int数组排序，所以这里的比较函数的参数都是int类型 
bool cmp(int a,int b){
	return a>b;
}
int main()
{
	const int N = 10;
	int a[N] = {5,8,3,4,9,2,6,7,1,10};
	
	for(int i=0;i<N;i++) cout<<a[i]<<" ";
	cout<<endl;
	
	sort(a,a+N,cmp);
	
	for(int i=0;i<N;i++) cout<<a[i]<<" ";
	cout<<endl;
	return 0;
} 

排序的基本操作是通过比较两个元素来确定两个元素排序后存放的先后顺序，上面的比较函数的作用就是在排序时实现自定义比较。对于两个元素 a、b 作为参数执行比较函数，如果比较函数返回值是 true，那么排序后元素 a 会存放在元素 b 的前面（排序后元素a在数组存放的下标小于元素b），反之亦反。

思考使用下面的比较函数的排序效果：

bool cmp(int a,int b){
    return abs(a)<abs(b);
}

bool cmp(int a,int b){
    return abs(a-5)>abs(b-5);
}

【扩展】要实现从大到小排序，除了使用自定义的比较函数外，还可以使用STL（标准模板库）中已有的greater<int>()，此时排序函数的使用方法是：sort(a,a+N,greater<int>());。

二、sort函数对字符串数组排序

【问题】对小组内5位同学的姓名按照字典顺序从小到大排序。

【分析】使用string数组存储5位同学的姓名，因为string字符串是可以直接比较大小的，所以使用sort函数直接排序即可：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	const int N = 5;
	string names[N] = {"Jerry","Tom","Hellen","Lucy","Tiger"};
	
	for(int i=0;i<N;i++) cout<<names[i]<<" ";
	cout<<endl;
	
	sort(names,names+N);
	
	for(int i=0;i<N;i++) cout<<names[i]<<" ";
	cout<<endl;
	return 0;
} 

但是如果使用字符数组来存储字符串，那么这里需要使用二维数组来存储所有同学的姓名，此时如果直接使用sort函数排序会出现编译错误，原因是字符数组存储的字符串不能直接比较大小：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	const int N = 5;
	char names[N][10] = {"Jerry","Tom","Hellen","Lucy","Tiger"};
	
	for(int i=0;i<N;i++) cout<<names[i]<<" ";
	cout<<endl;
	
	sort(names,names+N);     //会出现编译错误
	
	for(int i=0;i<N;i++) cout<<names[i]<<" ";
	cout<<endl;
	return 0;
}

这个时候需要通过指定sort的比较函数来避免编译错误：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

//用来指定sort排序规则的比较函数
//因为要对char*数组排序，所以这里的比较函数的参数都是char*类型
bool cmp(char *a,char *b){
	return strcmp(a,b)<0;
}
int main()
{
    const int N = 5;
    char names[N][10] = {"Jerry","Tom","Hellen","Lucy","Tiger"};
    
    //char*数组pnames，用来存放names数组每一行（字符串）的首地址 
    char *pnames[N];
    for(int i=0;i<N;i++) pnames[i] = names[i];
    
    for(int i=0;i<N;i++) cout<<pnames[i]<<" ";
    cout<<endl;
    
    sort(pnames,pnames+N,cmp);	//用names作为参数会出现编译错误 
    
    for(int i=0;i<N;i++) cout<<pnames[i]<<" ";
    cout<<endl;
    return 0;
}

可见使用char数组来存储字符串，此时使用sort函数来对字符串数组（是一个二维数组）排序比较繁琐（因为字符数组存储字符串是C的做法，sort函数是C++新引入的），推荐使用C++的string来存储字符串，sort函数对string字符串数组的排序就像对int数组排序一样方便。

三、sort函数对高精度数排序

因为只涉及到高精度数排序，所以可以直接将高精度数存储到string字符串中，使用自定义比较函数来实现排序。对于存储在string中的两个非负高精度整数，如果长度相等，那么可以按照字典顺序直接比较大小；如果长度不等，那么长度小的字符串中存储的高精度数小：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N = 1000;
string a[N+10];
//自定义排序：实现存储在字符串中的高精度数比较
//参数类型使用const string &比string执行效率更高 
bool cmp(const string &a,const string &b){
	int la = a.length(),lb = b.length();
	if(la == lb) return a<b;
	return la<lb; 
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) cout<<a[i]<<endl;	
	return 0;
}

读者可以自行实现对高精度整数（有正有负）的排序。