「JavaScript」字符串排序「排序与模拟」🗂️

一、算法思路

这道题需要根据特定规则对字符串进行排序。解决思路如下：

提取和分类：
- 提取字符串中的所有英文字母，忽略大小写进行排序。
- 保留原始字符串中的非字母字符位置不变。
排序规则：
- 按照英文字母从 A 到 Z 排列。
- 同一字母的大小写按输入顺序排列。
实现方法：
- 遍历字符串，将所有英文字母提取到一个数组中，并对该数组排序。
- 遍历原始字符串，将非字母直接放入结果中；对于字母，按排序后的顺序插入。

通过以上步骤，最终可得到符合题意的输出字符串。

二、代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // 读取输入字符串
    const input = await readline();

    // 提取英文字母，保留原始顺序和位置
    const letters = [];
    for (const char of input) {
        if (/[a-z]/i.test(char)) {
            letters.push(char);
        }
    }

    // 忽略大小写排序
    letters.sort((a, b) => {
        const lowerA = a.toLowerCase();
        const lowerB = b.toLowerCase();
        if (lowerA === lowerB) {
            return 0; // 相同字母，保持原顺序
        }
        return lowerA < lowerB ? -1 : 1;
    });

    // 构建最终结果字符串
    let result = "";
    let letterIndex = 0;
    for (const char of input) {
        if (/[a-z]/i.test(char)) {
            result += letters[letterIndex++]; // 插入排序后的字母
        } else {
            result += char; // 非字母保持原位置
        }
    }

    console.log(result); // 输出结果
}()

比较函数逻辑

在 JavaScript 的 Array.prototype.sort 方法中，比较函数接收两个参数 a 和 b，返回值决定两者在排序中的相对顺序：

如果返回负数（如 -1），表示 a 排在 b 前面。
如果返回正数（如 1），表示 a 排在 b 后面。
如果返回 0，表示 a 和 b 的相对顺序不变。

三、复杂度分析

时间复杂度：
- 遍历字符串提取字母： $O(n)$ 。
- 字母排序： $O(k \log k)$ ，其中 $k$ 是字母的数量， $k \leq n$ 。
- 构建结果字符串： $O(n)$ 。
- 总时间复杂度为 $O(n + k \log k)$ 。
空间复杂度：
- 存储字母的数组和结果字符串，占用 $O(n)$ 空间。
- 总空间复杂度为 $O(n)$ 。