algorithm - 用于昂贵交换的排序算法？

Question

我在开发的应用程序中遇到了以下问题:

我有两个列表:

list1 = { Z, K, A, B, A, C }

list2 = { A, A, B, C, K, Z}

list2 保证是 list1 的排序版本。

我的目标是对 list1 仅通过交换 list1 中的元素 进行排序。因此，例如，我无法遍历 list2 并简单地将 list1 中的每个元素 i 分配给每个元素 j 在 list2 中。

使用 list2 作为资源，我需要在 可能的绝对最小交换数 中对 list1 进行排序。

是否有一套专门用于此目的的算法？我没听说过这样的事情。

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://stackoverflow.com/a/40507589/6726632 中的相同

希望对您有所帮助。