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

Question

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

我给了两个清单:

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

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

list2是保证是的排序版本list1.

我的目标是排序list1 仅通过交换单元内list1.因此,举例来说,我不能遍历list2,只是分配的每一个元素i中list1的每个元素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;
    }
}

此代码的最小交换次数与/sf/answers/2835531261/中的相同

希望这可以帮助你。