题解 | #字符串排序#

HJ14字符串排序

一.题目描述

给定n个字符串，按字典序顺序进行排序。

二.算法(冒泡排序)

我们可以利用string进行读入，string的字典序是可以通过<,>重载来实现的，那么我们本质就是利用一种排序算法来实现，我们可以采用一种简单的排序算法——冒泡算法来实现，下面是冒泡算法的动图和算法简介：

1. 比较相邻元素，前一个比后一个大(或者前一个比后一个小)就交换位置。
2. 每一对相邻的元素进行重复的工作，从开始对一直到结尾对，这一步完成后，结尾为最大值或者是最小值
3. 对所以的元素都进行上面的操作 下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
vector<string> q;     
int n;
int main(){
    cin>>n;
    string s;
    //输入n个字符串
    for(int i=0;i<n;i++){
        cin>>s;
        q.push_back(s); 
    }
    for(int i=0;i<n;i++){
            for(int j=1;j<n;j++){
                //进行比较小于就交换
                if(q[j]<q[j-1]){
                   swap(q[j],q[j-1]);
                }
            }
    }
    for(int i=0;i<n;i++) {
        cout<<q[i]<<endl;
    }
    return 0;
}

时间复杂度：$O(n^2)O(n^\{2\})$ 需要进行两重循环

空间复杂度：$O(1)O(1)$ 不需要什么额外空间

三.算法(sort排序)

可以利用库函数sort来实现，思路很简单，下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<string>q;
    string s;
    for(int i=0;i<n;i++){
        cin >> s;
        q.push_back(s);
    }
    sort(q.begin(),q.end());//利用sort函数进行排序
    for(int i=0;i<n;i++)
        cout<<q[i]<< endl;
    return 0;
}

时间复杂度：$O(nlogn)O(nlogn)$ sort函数的复杂度约是$O(nlogn)O(nlogn)$

空间复杂度：$O(1)O(1)$ 不需要什么额外空间