昂贵交换的排序算法？

Question

昂贵交换的排序算法？

algorithmsorting

5

我在开发中遇到了以下问题：

给定两个列表： list1 = { Z, K, A, B, A, C } list2 = { A, A, B, C, K, Z } list2保证是list1的排序版本。

我的目标是仅通过在list1中交换元素来对list1进行排序。例如，我不能迭代list2并将list1中的每个元素i分配给list2中的每个元素j。

使用list2作为资源，我需要以最少的交换次数来排序list1。

是否有专门用于此目的的算法集？我没有听说过这样的东西。

- Hatefiend

不，搜索的时间复杂度是O（n ^ 2），但如果我们可以使用额外的数据结构等进行优化，甚至可以将其最小化。对于每个项目，我们在尾部执行“线性搜索”。 - Willem Van Onsem

使用上面的示例，从索引0开始，属于此处的元素是A，在list1中进行线性搜索以查找A，返回索引2。交换索引0和2，以此类推。 - Hatefiend

1

在你正在开发的应用程序中？你确定这不是家庭作业或编程竞赛的问题吗？在现实世界中，在99.9999％的情况下，你不会关心最小交换次数，而且你可能只会根据第二个列表中的索引运行正常排序。 - Bernhard Barker

2

@Hatefiend，那么你可能遇到了XY问题。 - Bernhard Barker

3

可能是重复的问题，关于如何找到将一个字符串转换为另一个字符串所需的最小交换次数，其中字符串可能包含重复字符。原问题链接：https://dev59.com/5GMl5IYBdhLWcg3wknsT - juvian

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ahmad Shabib · Answer 1

我用Java编写了这段代码，以便进行最小交换，由于第二个列表保证已排序，因此我们可以查找其中每个元素并从第一个列表中找到其索引，然后在当前索引元素和我们找到的元素之间进行交换。

更新：我修改了findLastElementIndex函数，它会根据list2检查交换后的元素是否在正确的索引位置。

public class Testing {

    private static String[] unorderedList = {"Z", "C", "A", "B", "A", "K"};
    private static String[] orderedList = {"A", "A", "B", "C", "K", "Z"};
    private static int numberOfSwaps;

    public static void main(String[] args) {
        for (int i = 0; i < unorderedList.length; i++) {
            if (!unorderedList[i].equals(orderedList[i])) {
                int index = findElementToSwapIndex(i, orderedList[i]);
                swapElements(unorderedList, i, index);
            }
        }
        System.out.println(numberOfSwaps);
    }

    private static void swapElements(String[] list, int indexOfFirstElement, int IndexOfSecElement) {
        String temp = list[indexOfFirstElement];
        list[indexOfFirstElement] = list[IndexOfSecElement];
        list[IndexOfSecElement] = temp;
        numberOfSwaps++;
    }

    private static int findElementToSwapIndex(int currentIndexOfUnorderedList , String letter) {
        int lastElementToSwapIndex = 0;
        for (int i = 0; i < unorderedList.length; i++) {
            if (unorderedList[i].equals(letter)) {
                lastElementToSwapIndex = i;
            if(unorderedList[currentIndexOfUnorderedList].equals(orderedList[lastElementToSwapIndex])){// check if the swapped element will be in the right place in regard to list 2
                    return lastElementToSwapIndex;
                }
            }
        }
        return lastElementToSwapIndex;
    }
}

这段代码的最小交换次数与https://dev59.com/6GUp5IYBdhLWcg3woonS#40507589中的相同。

希望这能对你有所帮助。