算法对对象列表进行重新排序

Question

我正在搜索一种算法来重新排序字典列表或javascript对象数组。 例如，我有以下对象列表：

my_dict = [
    {
        "id": 123,
        "priority": 1
    },
    {
        "id": 234,
        "priority": 2
    },
    {
        "id": 345,
        "priority": 3
    },
    {
        "id": 654,
        "priority": 4
    }
]

现在我想将id为654的项更改为第一优先级。因此，其他项目自动进入优先级2、3和4。 结果应该是：

my_dict = [
    {
        "id": 654,
        "priority": 1
    }
    {
        "id": 123,
        "priority": 2
    },
    {
        "id": 234,
        "priority": 3
    },
    {
        "id": 345,
        "priority": 4
    },
]

另一个例子是，当我想将项目234的优先级降低到优先级3时，优先级为3的项目应变为优先级2（从原始/第一个dict）。此列表中不应该有两次优先级，也不应该有差距

my_dict = [
    {
        "id": 123,
        "priority": 1
    },
    {
        "id": 345,
        "priority": 2
    },
    {
        "id": 234,
        "priority": 3
    },
    {
        "id": 654,
        "priority": 4
    }
]

为了澄清，这里还有一个例子。 如果我将id为123的项目移动到优先级4，则之前的项目应变为优先级1、2和3

my_dict = [

    {
        "id": 234,
        "priority": 1
    },
    {
        "id": 345,
        "priority": 2
    },
    {
        "id": 654,
        "priority": 3
    }
        {
        "id": 123,
        "priority": 4
    },
]

列表应始终以优先级1开头。有人能解释一下我如何用python或javascript实现它吗？我尝试了一个for循环开始和1，但这不起作用

Answer 1

我不同意以名单中的职位和“优先”成员来代表优先权的想法。这是多余的，会在某一点上造成故障

此外，我必须作出假设来回答这个问题，因为这个问题并不完整

假设：

• 最后，列表应该再次按优先级排序
• 优先级最终应该是整数
• 优先级始终从1开始，并在列表中不留空白

---

第一种方法

使用halfs精确指定要放置项目的位置。这很简单，其他一切都应该到位

范例

任务：将234移动到优先级3

遗憾的是，这并不是唯一的定义，因为不清楚旧的优先项目3应该转移到哪里

而是将其移动到priority3.5以使其明确，然后重新排序并重新枚举：

# Change priority of '234' to '3.5'
my_dict[1]["priority"] = 3.5

# Sort
my_dict.sort(key=lambda x: x["priority"])

# Re-enumerate
for (position, item) in enumerate(my_dict):
    item["priority"] = position + 1

print(my_dict)

[{'id': 123, 'priority': 1}, {'id': 345, 'priority': 2}, {'id': 234, 'priority': 3}, {'id': 654, 'priority': 4}]

---

但对于大型数据集，这确实很慢，因为每个优先级更改都是O（n*log（n）），因为它需要排序

您应该研究更好的数据结构，如堆或链表，这取决于您的确切使用场景

---

第二种方法

如果我们删除'priority'成员，我们可以编写一个更高效的算法：

def move(data, original, target):
    data.insert(target, data.pop(original))

# Important: Start priorities at 0, not 1. This makes this a lot easier.

my_dict = [123, 234, 345, 654]
move(my_dict, 3, 0)
print(my_dict)

my_dict = [123, 234, 345, 654]
move(my_dict, 1, 2)
print(my_dict)

[654, 123, 234, 345]
[123, 345, 234, 654]

https://ideone.com/o9UcCb

有关如何在列表中移动项目的详细讨论，请阅读this discussion