如何优化JavaScript数组排序代码以解决在线编程超时问题？

你的问题出在使用通用排序算法处理特定场景的数组。题目明确是对仅包含0、1、2的数组排序，JS内置的sort方法（时间复杂度O(nlogn)）在面对超大测试用例时效率不足，导致超时。

优化思路：荷兰国旗算法（线性时间原地排序） #

这是专门解决0、1、2元素排序的经典算法，时间复杂度O(n)，仅需一次遍历，空间复杂度O(1)（原地修改数组），完全适配这类问题的性能要求。

算法核心逻辑：

• 用三个指针划分三个区域：
  • low：标记下一个0应该放置的位置
  • mid：当前正在遍历的元素位置
  • high：标记下一个2应该放置的位置
• 遍历过程中根据arr[mid]的值做不同处理：
  1. 若为0：交换arr[low]和arr[mid]，low++、mid++（0区域扩大，继续遍历下一个元素）
  2. 若为1：直接mid++（1区域自然扩大，无需操作）
  3. 若为2：交换arr[mid]和arr[high]，high--（2区域扩大，交换过来的元素未处理，mid不前进）

优化后的代码实现 #

class Solution {
    sort012(arr, N) {
        let low = 0;
        let mid = 0;
        let high = N - 1;
        
        while (mid <= high) {
            if (arr[mid] === 0) {
                [arr[low], arr[mid]] = [arr[mid], arr[low]];
                low++;
                mid++;
            } else if (arr[mid] === 1) {
                mid++;
            } else {
                [arr[mid], arr[high]] = [arr[high], arr[mid]];
                high--;
            }
        }
        return arr;
    }
}

为什么这个算法更快？ #

该算法仅遍历数组一次，每一步操作都是O(1)的交换或指针移动，没有通用排序中的递归、分治等额外开销，在数据量极大的测试用例中，性能会远优于O(nlogn)的通用排序算法，完全能通过时间限制。

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