JavaScript原型sort函数未与所有数组元素比较的原因排查

你的问题出在自定义排序函数违反了排序算法要求的传递性规则，导致浏览器的排序引擎（比如V8用的Timsort）跳过了部分元素对的比较，最终输出错误结果。

先讲清楚什么是传递性 #

排序比较函数必须满足逻辑上的传递性：如果a应该排在b前面，b应该排在c前面，那a必须排在c前面。用比较函数的返回值来说：

• 要是compare(a,b) ≤ 0且compare(b,c) ≤ 0，那必须compare(a,c) ≤ 0

你的代码哪里踩坑了？ #

看你这段判断：

if(map[a]===undefined || map[b]===undefined || a===b){
    return 0;
}

你把「其中一个元素不在order映射里」的情况直接返回0，相当于告诉排序算法「这两个元素相等，不用调整顺序」。但这会引发逻辑矛盾：

• 比如e（在order里，优先级0）和w（不在order里）比较，返回0 → 算法认为e和w相等
• w和x（在order里，优先级1）比较，返回0 → 算法认为w和x相等
• 按传递性，算法会默认e和x也相等，但实际上e的优先级比x高，应该排在x前面

这种矛盾会让排序算法觉得「通过w就能判断e和x的关系」，从而跳过e和x的直接比较，最终导致x排在e前面的错误结果。

正确的写法应该怎么改？ #

你得明确「不在order里的元素」的排序规则，比如统一把它们排在所有order内元素的后面（或者前面），而不是随便返回0。比如：

• 如果a在order里，b不在 → a排前面，返回-1
• 如果b在order里，a不在 → a排后面，返回1
• 两者都不在的话，可以按字符本身的ASCII顺序排序（或者保持原顺序，但注意Array.sort是不稳定排序，要稳定的话需要额外处理）

修正后的代码：

function customSortString(order: string, s: string): string {
    const map: Record<string, number> = {};
    for(let i=0;i<order.length;i++){
        map[order[i]]=i;
    }
    const newStr=[...s].sort((a,b)=>{
        const aInOrder = map[a] !== undefined;
        const bInOrder = map[b] !== undefined;
        
        // 两者都在order里，按优先级排序
        if(aInOrder && bInOrder){
            return map[a] - map[b];
        }
        // 只有一个在order里，优先排order里的元素
        if(aInOrder) return -1;
        if(bInOrder) return 1;
        // 都不在order里，按字符本身的顺序排
        return a.charCodeAt(0) - b.charCodeAt(0);
    })
    return newStr.join('');
};

现在调用customSortString("exv","xwvee")就能得到预期的"eexvw"了。

为啥自己写的插入排序能 work？ #

插入排序是逐个把元素插入到已排序序列的正确位置，它会强制和前面的每个元素依次比较，哪怕你的比较函数有传递性问题，它也能硬着头皮遍历完所有必要的比较。但这只是歪打正着，根本解决方法还是修复排序比较函数的逻辑，符合传递性要求。

内容的提问来源于stack exchange，提问作者fake822