如何使用相邻交换解决字典顺序最小排列？

Question

解决以下问题应该采取什么方法？找不到解决的办法。

给定一个整数数组，找到该数组按字典顺序排列的最小排列，可以通过将每对相邻元素恰好交换一次来生成该排列。

例如，如果数组是 [5, 4, 1, 3, 2]，则答案是 [1, 5, 2, 4, 3]，可以通过以下交换序列生成：

• [5, 4, 1, 3, 2] → [5, 1, 4, 3, 2]
• [5, 1, 4, 3, 2] → [1, 5, 4, 3, 2]
• [1, 5, 4, 3, 2] → [1, 5, 4, 2, 3]
• [1, 5, 4, 2, 3] → [1, 5, 2, 4, 3]

请注意，该序列在每个位置仅包含一次交换：索引 0 和 1 处的元素恰好交换一次，索引 1 和 2 处的元素恰好交换一次，等等。

Answer 1

看来你可以使用贪心的方法：

• 找到数组中的最小值：设其索引为𝑖
• 执行必要的交换，将该值变为索引 0（如果该值尚不存在）。因此交换 (𝑖−1,𝑖), (𝑖−2,𝑖−1), ... 处的对，直到达到索引 0，获得上一步中找到的最小值。
• 如果 𝑖 不是数组的最后一个索引，则考虑从索引 𝑖 到其末尾的子数组，并对该子数组重复上述过程。