求助：实现符合特定规则的对象数组排序函数

需求规则 #

• 所有包含xid属性的对象需置于数组末尾区域
• 若对象A的options数组中存在带xid的step对象，对应根层级的对象B，则B必须放在A的下方（例如：A的options里有step.xid=1，则xid=1的B要紧跟在A之后；B的options里有step.xid=2，则xid=2的对象要紧跟在B之后）

示例说明 #

文本为"Looking for online"的对象，其options数组第0项的step属性包含xid=1，因此根层级xid=1、文本为"Select City"的对象需放在它下方；同理，xid=2的"Select Area"对象需放在"Select City"对象下方。

输入数组 #

let array = [
    {
        type: 'radio',
        text: "Looking for online",
        options: [
            {
                text: "Yes",
                step: {
                    text: "Select City",
                    xid: 1
                }
            },
            {
                text: "No"
            }
        ]
    },
    {
        type: "single",
        text: "First Name",
    },
    {
        type: "single",
        text: "Last Name"
    },
    {
        type: 'radio',
        text: "Select Area",
        xid: 2,
        options: [
            {
                text: "Yes",
            },
            {
                text: "No"
            }
        ]
    },
    {
        type: 'radio',
        text: "Select City",
        xid: 1,
        options: [
            {
                text: "Mumbai",
                step: {
                    text: "Select Area",
                    xid: 2
                }
            },
            {
                text: "Delhi",
            }
        ]
    },
]

期望输出数组 #

let array = [
    {
        type: "single",
        text: "First Name",
    },
    {
        type: "single",
        text: "Last Name"
    },
    {
        type: 'radio',
        text: "Looking for online",
        options: [
            {
                text: "Yes",
                step: {
                    text: "Select City",
                    xid: 1
                }
            },
            {
                text: "No"
            }
        ]
    },
    {
        type: 'radio',
        text: "Select City",
        xid: 1,
        options: [
            {
                text: "Mumbai",
                step: {
                    text: "Select Area",
                    xid: 2
                }
            },
            {
                text: "Delhi",
            }
        ]
    },
    {
        type: 'radio',
        text: "Select Area",
        xid: 2,
        options: [
            {
                text: "Yes",
            },
            {
                text: "No"
            }
        ]
    },
];

现有代码问题 #

尝试用for循环调整索引时，多对象移动逻辑混乱，导致排序不符合预期。现有代码：

const filteredArray = [...array];
for(let index = 0; index < filteredArray?.length; index++) {
  if (filteredArray[index]?.type === 'radio' && filteredArray[index].options && filteredArray[index]?.options?.length) {
    const length = (filteredArray[index].options && filteredArray[index]?.options?.length) || 0;
    for(let index1 = 0; index1 < length; index1++) {
      const option = filteredArray[index]?.options?.[index1];
      if (option && option?.step && option?.step?.xid){
        const idx = array.findIndex(item => item?.xid === option?.step?.xid);
        if (idx >= 0 && idx !== index + 1) {
          const removedItem = array.splice(idx, 1)[0];
          array.splice(index, 0, removedItem);
        } 
      }
    }
  }
}

解决方案 #

采用依赖映射+链式构建的思路，先建立对象索引，再按依赖关系逐步构建结果数组：

function sortArray(arr) {
    // 1. 建立xid到对象的映射表，方便快速查找
    const xidMap = new Map();
    arr.forEach(item => {
        if (item.xid !== undefined) {
            xidMap.set(item.xid, item);
        }
    });

    // 2. 区分无xid的基础对象和有xid的关联对象
    const baseItems = arr.filter(item => item.xid === undefined);
    const linkedItems = new Set(arr.filter(item => item.xid !== undefined));

    const result = [];
    const added = new Set();

    // 3. 先处理基础对象，同时处理它们的依赖链
    for (const item of baseItems) {
        result.push(item);
        added.add(item);
        // 查找当前对象的所有依赖xid
        const dependentXids = new Set();
        if (item.options?.length) {
            item.options.forEach(opt => {
                if (opt.step?.xid) {
                    dependentXids.add(opt.step.xid);
                }
            });
        }
        // 遍历依赖xid，构建链式结构
        for (const xid of dependentXids) {
            let current = xidMap.get(xid);
            while (current && !added.has(current)) {
                result.push(current);
                added.add(current);
                linkedItems.delete(current);
                // 查找当前对象的下一级依赖
                const nextXids = new Set();
                if (current.options?.length) {
                    current.options.forEach(opt => {
                        if (opt.step?.xid) {
                            nextXids.add(opt.step.xid);
                        }
                    });
                }
                // 取第一个有效依赖（按示例逻辑，优先处理关联的依赖）
                current = Array.from(nextXids).map(x => xidMap.get(x)).find(item => item && !added.has(item));
            }
        }
    }

    // 4. 添加剩余未被关联的有xid对象（如果有的话）
    result.push(...linkedItems);

    return result;
}

// 测试使用
const sortedArray = sortArray(array);
console.log(sortedArray);

代码说明 #

1. 映射表建立：用Map存储xid和对应对象，避免多次遍历查找，提升效率。
2. 对象分类：把数组分成无xid的基础组和有xid的关联组，确保基础组优先排列。
3. 依赖链构建：遍历基础组对象时，自动查找其options中关联的xid对象，递归添加后续依赖对象，保证链式顺序。
4. 剩余对象处理：最后添加未被任何对象关联的有xid对象，确保所有元素都被包含。

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