题解 | #整理科研数据文件#

题目链接

整理科研数据文件

题目描述

一位科研人员需要对大量以字母和数字混合命名的文件进行“自然排序”。传统的字典序会将 Run10 排在 Run2 之前，而自然排序需要理解数字的真实大小。

排序规则如下：

分段处理：将文件名分割成“连续的非数字字符串”和“连续的数字字符串”。例如，ts010tc12 分解为 ["ts", "010", "tc", "12"]。
逐段比较：
- 若两段都是非数字串，按字典序（区分大小写）比较。
- 若两段都是数字串，转换为整数值比较。
- 若一个是数字串，另一个是非数字串，数字串优先排在前面。
前缀优先：如果一个文件名是另一个文件名的前缀，较短的排在前面。
稳定性：排序必须是稳定的。如果两个文件名在上述规则下等价（如 Run01 和 Run1），保持原始相对顺序。

输入：

第一行：一个整数 $N$ ，文件名数量。
接下来 $N$ 行：每行一个文件名 $S_i$ （仅含大小写字母和数字，长度 $\le 100$ ）。

输出：

$N$ 行排序后的文件名。

解题思路

这是一个定制规则的排序问题。我们需要实现一个分段逻辑和相应的比较算子。

分段逻辑：使用扫描法或正则表达式将字符串 $S$ 拆分为 $Seg_{i,1}, Seg_{i,2}, \dots, Seg_{i,k}$ 。每一段需要记录其内容以及它是否为数字串。
自定义比较算子：对于两个文件名的段序列进行逐一对比：
- 比较类型：若一段为数字，另一段为非数字，数字段对应的文件名较小。
- 类型相同：
  - 若同为非数字：使用字符串的 compare 或直接比较。
  - 若同为数字：将字符串转为对应的数值（由于连续数字长度不超过 9，int 或 long long 即可处理），比较数值大小。
- 若所有段都相等且一段序列耗尽：短的文件名较小。
稳定性保证：
- C++：使用 std::stable_sort。
- Java：Arrays.sort 对引用类型是稳定的（通常是 TimSort）。
- Python：list.sort() 是稳定的。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 段结构体
struct Segment {
    string val;
    bool isDigit;
};

// 分割字符串为段
vector<Segment> split(const string& s) {
    vector<Segment> res;
    int i = 0, n = s.length();
    while (i < n) {
        string t = "";
        bool digit = isdigit(s[i]);
        if (digit) {
            while (i < n && isdigit(s[i])) t += s[i++];
        } else {
            while (i < n && !isdigit(s[i])) t += s[i++];
        }
        res.push_back({t, digit});
    }
    return res;
}

// 比较逻辑
bool compareNatural(const string& a, const string& b) {
    vector<Segment> sa = split(a);
    vector<Segment> sb = split(b);
    int len = min(sa.size(), sb.size());
    for (int i = 0; i < len; ++i) {
        if (sa[i].isDigit != sb[i].isDigit) {
            // 数字段排在前面
            return sa[i].isDigit;
        }
        if (sa[i].isDigit) {
            long long va = stoll(sa[i].val);
            long long vb = stoll(sb[i].val);
            if (va != vb) return va < vb;
        } else {
            if (sa[i].val != sb[i].val) return sa[i].val < sb[i].val;
        }
    }
    return sa.size() < sb.size();
}

int main() {
    int n;
    cin >> n;
    vector<string> files(n);
    for (int i = 0; i < n; ++i) cin >> files[i];

    // 使用稳定排序
    stable_sort(files.begin(), files.end(), compareNatural);

    for (const string& s : files) {
        cout << s << "\n";
    }
    return 0;
}

import java.util.*;

public class Main {
    static class Segment {
        String val;
        boolean isDigit;
        Segment(String val, boolean isDigit) {
            this.val = val;
            this.isDigit = isDigit;
        }
    }

    static List<Segment> split(String s) {
        List<Segment> res = new ArrayList<>();
        int i = 0, n = s.length();
        while (i < n) {
            StringBuilder sb = new StringBuilder();
            boolean digit = Character.isDigit(s.charAt(i));
            if (digit) {
                while (i < n && Character.isDigit(s.charAt(i))) sb.append(s.charAt(i++));
            } else {
                while (i < n && !Character.isDigit(s.charAt(i))) sb.append(s.charAt(i++));
            }
            res.add(new Segment(sb.toString(), digit));
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] files = new String[n];
        for (int i = 0; i < n; i++) files[i] = sc.next();

        Arrays.sort(files, (a, b) -> {
            List<Segment> sa = split(a);
            List<Segment> sb = split(b);
            int len = Math.min(sa.size(), sb.size());
            for (int i = 0; i < len; i++) {
                Segment segA = sa.get(i);
                Segment segB = sb.get(i);
                if (segA.isDigit != segB.isDigit) {
                    return segA.isDigit ? -1 : 1;
                }
                if (segA.isDigit) {
                    long va = Long.parseLong(segA.val);
                    long vb = Long.parseLong(segB.val);
                    if (va != vb) return Long.compare(va, vb);
                } else {
                    if (!segA.val.equals(segB.val)) return segA.val.compareTo(segB.val);
                }
            }
            return Integer.compare(sa.size(), sb.size());
        });

        for (String f : files) System.out.println(f);
    }
}

import re

def split_segments(s):
    # 使用正则表达式提取数字和非数字部分
    parts = re.findall(r'\d+|[^\d]+', s)
    res = []
    for p in parts:
        if p.isdigit():
            # 记录类型(数字优先，标记为0)和数值
            res.append((0, int(p)))
        else:
            # 记录类型(非数字，标记为1)和内容
            res.append((1, p))
    return res

def solve():
    n = int(input())

    files = []
    for _ in range(n):
        files.append(input().strip())

    # Python的sort是稳定的，直接使用元组序列作为key
    # 元组对比会逐段进行：先比类型，再比值
    files.sort(key=split_segments)

    for f in files:
        print(f)

if __name__ == "__main__":
    solve()

算法及复杂度

算法：自然排序（自定义分段比较） + 稳定排序。
时间复杂度： $\mathcal{O}(N \log N \cdot L)$ 。其中 $N$ 是文件名数量， $L$ 是文件名的平均长度。排序需要 $N \log N$ 次比较，每次比较涉及分段和字符串/数值对比。
空间复杂度： $\mathcal{O}(N \cdot L)$ 。用于存储所有的文件名及其分段后的表示。