C++ sort( ) 用法详解(新手版)

认识sort ( )

①为什么要选择sort（）

在新入门算法时，我们大多时候都是手写排序，如果题目对规定方法没有要求的情况下，这样手撕排序效率比较低下。如果现在在刷题时，还在纠结冒泡排序、插入排序、快速排序、选择排序、计数排序、希尔排序、桶排序等选哪一个时，不妨学习一下sort（）这个简单又快捷的函数。除非是在特殊题目时，否则大多数时候sort () 不会被禁用。（ps：sort真的会越用越上瘾喵。）

② sort( ) 函数是如何实现排序的

快速排序：快速排序是一种分治算法，它选择一个元素作为“基准”（pivot），然后将数组分为两部分，一部分的所有元素都比基准小，另一部分的所有元素都比基准大。

插入排序：对于小规模的数据集，快速排序可能不是最优的选择。因此，当待排序的数据量小于某个阈值时，sort（）可能会切换到插入排序，因为对于小数组，插入排序通常更快且更简单。

堆排序：为了防止最坏情况的发生，一些实现可能会使用堆排序或者改进版的快速排序，来处理大量重复元素的情况。

使用sort ( )

首先要知道，sort( ) 的使用要包含在头文件#include中。

①sort( ) 的基本语法：sort(begin,end,cmp)

对于这三个参数：begin:指向待排数组的第一个元素的地址。

end:指向待排数组的最后一个元素的下一个位置的地址。

cmp:自定义参数。可写可不写。关于cmp将在下文详解喵。

②sort( ) 的简单实现:

下面这个代码的实现就是没有参数cmp的

#include

#include

using namespace std;

int main( )

{

int arr[8]={49,38,65,97,76,13,27,49};

sort(arr,arr+8);

cout<<"排序之后的代码:";

for(int i=0;i<8;i++)

{

cout<

}

return 0;

}

运行结果：

参数的详细使用方法

①无参数

输出结果为升序输出。（见上文）

②降序排列

直接加上参数greater()后即可实现，如果是其他类型的数，把int改掉即可。当然也可以自定义cmp实现。注意：cmp返回的是一个布尔类型的值，所以一般定义成bool类型。

③自定义参数

利用字典序排序

倒序：

#include

#include

using namespace std;

bool cmp(string x, string y) {

return x > y ;

}

string arr1[1001];

int main()

{

int n;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> arr1[i];

}

sort(arr1, arr1 + n, cmp);

for (int i = 0; i < n; i++) {

cout << arr1[i];

}

return 0;

}

输入输出结果：

在上面这个版本中，cmp 函数直接使用了字符串的比较操作符 >，这会按照字典序进行比较，并且在第一个字符相同时继续比较后续字符。

正序：

#include

#include

#include

using namespace std;

int main()

{

string str;

cin>>str;

sort(str.begin(),str.end());

cout<

return 0;

}

输入输出结果 ：

在上面这个版本中，sort()的格式：sort(str.begin(),str.end());

利用个位数大小排序

#include

#include

using namespace std;

bool cmp(int x, int y) {

return x % 10 > y % 10;

}

int main() {

int num[8] = { 49,38,65,97,76,13,27,49 };

sort(num, num + 8, cmp);

for (int i = 0; i < 8; i++) {

cout << num[i] << " ";

}

return 0;

}

输出结果：

④结构体排序

首先给出一个简单的例子，这里以学生的成绩进行升序排序。

#include

#include

using namespace std;

struct student{

string name;

int score;

};

bool cmp(student x, student y) {

return x.score < y.score;

}

int main()

{

int n;

cin >> n;

struct student s[n];

for (int i = 0; i < n; i++) {

cin >> s[i].name >> s[i].score;

}

sort(s, s + n, cmp);

for (int i = 0; i < n; i++) {

cout << s[i].name << " " << s[i].score << endl;

}

return 0;

}

这里我们分别输入三个人的姓名与成绩：

运行得到结果：

再让我们进阶一下: （本例引用了洛谷P1781 宇宙总统）

输入：第一行为一个整数 n，代表竞选总统的人数。接下来有 n 行，分别为第一个候选人到第 n 个候选人的票数。 输出：共两行，第一行是一个整数 m，为当上总统的人的号数。第二行是当上总统的人的选票。

这里我们给出排序部分的代码

bool cmp(cmd x,cmd y){

if(x.num.length()!=y.num.length()){

return x.num.length()>y.num.length();

}//num是输入的票数

return x.num>y.num;

}

第一个return表示 x 比 y 位数多时，x 在前面。 第二个是位数相同时，字典序大的排前面。

像这样我们就可以在cmp里进行多个条件的判定了！

完整代码如下：

struct cmd{

int id;

string num;

};

bool cmp(cmd x,cmd y){

if(x.num.length()!=y.num.length()){

return x.num.length()>y.num.length();

}

return x.num>y.num;

}

int main( )

{

int n;

cin>>n;

struct cmd s[n];

for(int i=0;i

s[i].id=i+1;

cin>>s[i].num;

}

sort(s,s+n,cmp);

cout<

}

输入：

输出：

本小白第一次写文章，以上就是我对sort()的全部理解了，如果有错请指出，有不完整可以评论留言补充，也可私信。感谢您的观看喵！