题解 | #字符串排序 归并 不使用库函数#

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
std::vector<string> res;
bool compare(const std::string& str1, const std::string& str2){
    int len = min(str1.size(), str2.size());
    // 小到大排序
    for (int i = 0; i < len; ++i){
        if (str1[i] < str2[i]) return true;
        else if (str1[i] > str2[i]) return false;
    }
    if (str1.size() == len) return true;
    return false;
}

bool compare_1(const std::string& str1, const std::string& str2){
    int len = min(str1.size(), str2.size());
    // 大到小排序
    for (int i = 0; i < len; ++i){
        if (str1[i] > str2[i]) return true;
        else if (str1[i] < str2[i]) return false;
    }
    if (str1.size() == len) return false;
    return true;
}

void merge_algorithm(std::vector<string>& vec, int start, int mid, int end){
    // 将两段数组排序
    res.clear();
    int leftStart = start;
    int rightStart = mid + 1;
    int count = 0;
    while (leftStart <= mid && rightStart <= end){
        // 左右两端没有全部排序完 从小到大排序
        if (compare(vec[leftStart], vec[rightStart])){
            // std::cout << "vec[leftStart]: " << vec[leftStart] << std::endl;
            res.push_back(vec[leftStart]);
            leftStart++;
        }else{
            res.push_back(vec[rightStart]);
            rightStart++;
        }
    }
    // 左段数组先排完序
    while (rightStart <= end){
        res.push_back(vec[rightStart++]);
    }
    // 右段数组先排完
    while (leftStart <= mid){
        res.push_back(vec[leftStart++]);
    }
    // 处理原数组
    for (int i = 0; i < res.size(); ++i){
        // std::cout << "res" << res[i] << std::endl;
        vec[i + start] = res[i]; 
        // std::cout << "vec" << vec[i] << std::endl;

    }

}

void merge_sort(std::vector<string>& str, int start, int end){
    // 划分数组
    if (start >= end) return;
    int mid = start + (end - start)/2;
    merge_sort(str, start, mid);
    merge_sort(str, mid+1, end);
    merge_algorithm(str, start, mid, end);

}

int main() {
    int n;
    std::cin >> n;
    std::vector<string> result;
    for (int i = 0; i < n; ++i){
        string tmp;
        std::cin >> tmp;
        result.push_back(tmp);
    }
    // sort(result.begin(), result.end(), compare);
    merge_sort(result, 0, result.size() - 1);
    for (auto tmp : result){
        std::cout << tmp << std::endl;
    }
    return 0;

}
// 64 位输出请用 printf("%lld")