python-3.x - 如何找到最小开关数以按升序对给定的排列(比方说 1-10)进行排序

Question

亚瑟王的书架上有 10 本书，编号为 1,2,3,...,10。多年来，卷变得困惑。 Arthur 试图通过同时交换两本书的位置来按升序排列这些书。由于书很重，他每天只能换两册。帮助 Merlin 订购书籍。

例如，如果一个排列是 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 那么我们只需要 5 个开关来按升序排序

注意:最坏情况下会有9个开关

Q1。找出最坏情况对应的排列

Q2。如何找到给定排列所需的最少开关数。 (算法和可能的 C、C++、Python 代码)

PS:我能够手动解决它，最好说 Trial N 错误(对 Q1.10、1、2、3、4、5、6、7、8、9 的回答)。但我想知道算法

Answer 1

使用 1 索引列表，

在问题给出的示例中获取包含相同元素的列表:

[0,10,9,8,7,6,5,4,3,2,1] # 在前面加0使列表以1为索引

第 1 步:将列表的最后一个索引...作为迭代器

Step2:运行while循环直到迭代器值大于0

第三步:如果迭代器中的元素与值匹配，那么我们必须减少迭代器的值，因为不需要执行交换操作。

Step4:如果元素不匹配，则将元素与其索引值交换并将操作计数增加 1。不需要像可能那样减少迭代器值我们在迭代器位置获得的值可能与其索引不匹配的情况...

解决方案的时间复杂度是 O(2*N) ~~ O(N)。

arr = [0,10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
iterator = 10
count_of_operations = 0
while(iterator>0):
    index_to_swap = arr[iterator]
    if(index_to_swap == iterator):
        iterator = iterator - 1
    else:
        arr[iterator],arr[index_to_swap] = arr[index_to_swap],arr[iterator]
        count_of_operations = count_of_operations + 1
        
print(count_of_operations)