题目的主要信息：

• 给定n个字符串，对n个字符串按照字典序排列
• 第一行输入n，后面n行输入n个字符串

我们要知道的是，在C++中，直接对string型字符串做大小比较，是比较字典序，因为string类重载了大小比较符号。了解这个以后问题就迎刃而解了，我们将字符串当成数字，直接用排序算法就可以了。

方法一：冒泡排序

具体做法：

对字符串数组进行$nn$n次循环，每次都依次比较前后两个元素的大小，不断将字典序较小的字符串往前面移，最多移动$nn$n个循环，即可完成排序。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<string> strs; //字符串数组
    string s;
    for(int i = 0; i < n; i++){ //输入n个字符串
        cin >> s;
        strs.push_back(s); //堆排序
    }
    for(int i = 0; i < n; i++)
            for(int j = 1; j < n; j++)
                if(strs[j] < strs[j - 1]){//比较并冒泡
                    string temp = strs[j];  //交换
                    strs[j] = strs[j - 1];
                    strs[j - 1] = temp;
                }
    for(int i = 0; i < n; i++) //输出
        cout << strs[i] << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，两层嵌套循环
• 空间复杂度：$O\left(1\right)O(1)$O(1)，数组strs为必要空间，无额外空间

方法二：堆排序

具体做法：

使用priority_queue优先队列模拟小顶堆，输入的时候每次输入一个字符串就加入堆中，优先队列会对加入的元素自动使用堆排序，然后不断弹出堆顶元素输出即是字典由小到大。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

int main(){
    int n;
    cin >> n;
    priority_queue<string, vector<string>, greater<string> > strs; //小根堆
    string s;
    for(int i = 0; i < n; i++){ //输入n个字符串
        cin >> s;
        strs.push(s); //堆排序
    }
    while(!strs.empty()){ //从小到大输出
        cout << strs.top() << endl;
        strs.pop();
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，优先队列每次插入一个元素是$O\left(lo{g}_{2}n\right)O(log\_2n)$O(log2​n)，一共$nn$n次操作
• 空间复杂度：$O\left(n\right)O(n)$O(n)，最坏空间为优先队列长度，最坏情况是$nn$n

方法三：库函数快排

具体做法：

前面都说了，这个字符串之间的比较就是比较字典序，我们可以用sort函数来排序，且不用重载大小的比较。

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

int main(){
    int n;
    cin >> n;
    vector<string> strs;
    string s;
    for(int i = 0; i < n; i++){ //输入n个字符串
        cin >> s;
        strs.push_back(s);
    }
    sort(strs.begin(), strs.end()); //排序函数
    for(int i = 0 ;i < n; i++) //输出
        cout << strs[i] << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，sort函数属于快排，复杂度为$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)
• 空间复杂度：$O\left(1\right)O(1)$O(1)，数组strs为必要空间，无额外空间

方法四：有序集合

具体做法：

set作为一个依赖于红黑树排序的有序集合，可以实现字符串有序。我们遍历在输入的时候就可以将字符串加入到set中，然后用迭代器遍历set输出字符串即可。

字符串可能会重复，因此要将set换成multiset。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

int main(){
    int n;
    cin >> n;
    multiset<string> strs; //可重复的有序集合
    string s;
    for(int i = 0; i < n; i++){ //输入n个字符串
        cin >> s;
        strs.insert(s); //加入集合中
    }
    for(auto iter = strs.begin(); iter != strs.end(); iter++) //遍历集合输出
        cout << *iter << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，依赖于红黑树的排序插入一次是$O\left(lo{g}_{2}n\right)O(log\_2n)$O(log2​n)，一共$nn$n次插入
• 空间复杂度：$O\left(n\right)O(n)$O(n)，集合大小最大为$nn$n

方法五：归并排序

具体做法：

类似于数字的排序，归并排序利用了分治的思想来对字符串序列进行排序。对一个长为$nn$n的待排序的字符串序列，我们将其分解成两个长度为$n/2n/2$n/2的子序列。每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。

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

vector<string> temp;
void mergeSort(vector<string>& strs, int l, int r) {
    if (l >= r)
        return;
    int mid = (l + r) / 2; //中间划分
    mergeSort(strs, l, mid); //排序两边
    mergeSort(strs, mid + 1, r);
    int i = l, j = mid + 1;
    int cnt = 0;
    //合并
    while (i <= mid && j <= r) { //依次比较，先取较小值
        if (strs[i] <= strs[j])
            temp[cnt++] = strs[i++];
        else
            temp[cnt++] = strs[j++];
    }
    while (i <= mid)  //剩余的元素
        temp[cnt++] = strs[i++];
    while (j <= r)
        temp[cnt++] = strs[j++];
    for (int i = 0; i < r - l + 1; ++i)
        strs[i + l] = temp[i];
}

int main(){
    int n;
    cin >> n;
    vector<string> strs; //可重复的有序集合
    string s;
    for(int i = 0; i < n; i++){ //输入n个字符串
        cin >> s;
        strs.push_back(s); //加入集合中
    }
    temp.resize(n);
    mergeSort(strs, 0, n - 1); //归并排序
    for(auto iter = strs.begin(); iter != strs.end(); iter++) //遍历排序后的结果输出
        cout << *iter << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，递归公式为$T\left(n\right)=2T\left(n/2\right)+O\left(n\right)T(n)=2T(n/2)+O(n)$T(n)=2T(n/2)+O(n)，故复杂度为$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)
• 空间复杂度：$O\left(n\right)O(n)$O(n)，借助了temp数组