C++ sort() 排序函数

我就是我 2023-02-16 12:27 150阅读 0赞

[本文参考的博客链接][Link 1]  
[PAT排序例题A1025][PAT_A1025]  
[经典排序算法][Link 2]  
[算法总目录][Link 3]

## 一、简介 ##

1、头文件：\#include  
2、时间复杂度：sort在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到O(n^2)的极端情况。类似于快排，为nlog(2)n，效率较高。  
3、参数

sort(首元素地址(必填)， 尾元素地址的下一个地址(必填)， 比较函数(非必填));

## 二、如何使用sort排序 ##

1、sort函数实现数的排序

#include<cstdio>
    #include<iostream>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    bool cmp(int a,int b)///实现从大到小排序的比较函数
    { 
        return a>b;
    }
     
    int main()
    { 
        int i,j;
        int arr[10]={ 1,33,56,74,34,34,555,43,43,343};
        sort(arr,arr+10,cmp);
        for(i=0;i<10;i++)
            cout<<arr[i]<<" "<<endl;
        return 0;
    }

2、sort函数实现字符串的排序（根据长度，字母顺序两种情况）

（1）sort函数对string内的字符进行排序（string为字符串类型数据）

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    bool cmp(char a,char b)///比较函数
    { 
        return a>b;
    }
    int main()
    { 
        string s;
        cin>>s;
        sort(s.begin(),s.end());///从小到大
        cout<<s<<endl;
        sort(s.begin(),s.end(),cmp);///从大到小
        cout<<s<<endl;
        cout<<s.length()<<endl;///字符串长度函数
    }

（2）sort对一维字符数组内的字符进行排序

```cpp
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    bool cmp(char a,char b)///比较函数
    { 
        return a>b;
    }
    int main()
    { 
        char a[100];
        scanf("%s",a);
        sort(a,a+strlen(a));///从小到大
        cout<<a<<endl;
        sort(a,a+strlen(a),cmp);///从大到小
        cout<<a<<endl;
        cout<<strlen(a)<<endl;///输出字符数组a的长度
     
    }

（3）sort对string类型的数组按照字典序排序

#include<cstdio>
    #include<iostream>
    #include<cstdlib>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    bool cmp(string a,string b)///按照字典序从大到小排序
    { 
        return a>b;
    }
    int main()
    { 
        int i,j;
        string  s[12]=
        { 
            "January",
            "February",
            "March",
            "April",
            "May",
            "June",
            "July",
            "August",
            "September",
            "October",
            "November",
            "December"
        };
        sort(s,s+12);///字符串默认按照字典序从小到大排序，数默认按照大小从小到大排序
      for(i=0;i<12;i++)
            cout<<s[i]<<endl;
     
            cout<<endl;
        sort(s,s+12,cmp);///按照字典序从大到小排序
        for(i=0;i<12;i++)
            cout<<s[i]<<endl;
      return 0;
    }

（4）sort对char类型的二维数组进行字典序排序

错误，不能这样做。同样也不能进行根据字符串长度的排序

解决方法有：1、使用qsort 2、改用string

（5）sort对string类型的数组根据长度进行排序

#include<cstdio>
    #include<iostream>
    #include<cstdlib>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    bool cmp1(string a,string b)///按照长度从小到大排序
    { 
        return a.length()<b.length();
    }
    bool cmp2(string a,string b)///按照长度从大到小排序
    { 
        return a.length()>b.length();
    }
    int main()
    { 
        int i,j;
        string  s[12]=
        { 
            "January",
            "February",
            "March",
            "April",
            "May",
            "June",
            "July",
            "August",
            "September",
            "October",
            "November",
            "December"
        };
        sort(s,s+12,cmp1);///按照长度从小到大排序
      for(i=0;i<12;i++)
            cout<<s[i]<<endl;
     
            cout<<endl;
        sort(s,s+12,cmp2);///按照长度从大到小排序
        for(i=0;i<12;i++)
            cout<<s[i]<<endl;
      return 0;
    }

3、对结构体数组进行排序（根据结构体中的某元素）

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int n=3;
    struct Student
    { 
            char name[20];///姓名
            char id[20]; ///学号
            int score;  ///成绩
            int r;          ///排名
    }stu[100010];
    /* (1)如果两个学生的分数不同，则分数高的排在前面 (2)否则，将姓名字典序小的排在前面 */
    bool cmp(Student a,Student b)
    { 
        if(a.score!=b.score) return a.score>b.score;
        else return strcmp(a.name,b.name)<0;
    }
     
    /* 排名的实现，一般规则为：分数不同，排名不同，分数相同排名相同但占用同一个排位 例如：分数为90,88,88,88,86;排名为1,2,2,2,5 */
    void Rank()
    { 
        int i,j;
        stu[0].r=1;
        for(i=1;i<n;i++)
        { 
            if(stu[i].score==stu[i-1].score) stu[i].r=stu[i-1].r;
            else stu[i].r=i+1;
        }
    }
    int main()
    { 
        int i,j;
        stu[0]={ "guo","001",82,3};///这样赋值不对，算了，以后再改吧
        stu[1]={ "zhang","002",82,3};
        stu[2]={ "wu","003",99,2};
        sort(stu,stu+n,cmp);
        for(i=0;i<n;i++)
            cout<<stu[i]<<endl;
    }

4、容器的排序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70 1]

[Link 1]: https://www.baidu.com/link?url=0vFROXVvyR6wmcJEhioeAx1Qzw0s778ulzQg9ta1kyUGltx5U7m_G1QWvEawoKHzvRCygSyk8IODxjxZZ5kA88Vo_GgLrx8CHZ4BcIJq7yO&wd=&eqid=fd5422d90011a9ed000000035ee03ad6
[PAT_A1025]: https://blog.csdn.net/qq_21480607/article/details/105316536
[Link 2]: https://blog.csdn.net/qq_21480607/article/details/106639118
[Link 3]: https://blog.csdn.net/qq_21480607/article/details/106660085
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610100010448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200610100050127.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3,size_16,color_FFFFFF,t_70