Python:修改的冒泡排序

Question

这个程序是用python编写的。它的目标是通过交换将一个位置号移到合适的位置，然后输出它进行的交换次数。因此，它非常类似于冒泡排序，除了程序不需要与其相邻的数字进行切换。请看下面的示例

示例输入：

5 2 4 7 7 3  

示例输出:2

示例说明：

24773 -5个整数的起始集合

24377 -用3交换第一个7(第一个交换)(7不在3旁边)

23477 -调换3和4以获得最小到最大的数字(第二次调换)

这是我用Python编写的当前代码。它执行传统的冒泡排序方法。

def bubbleSort(alist):
times = 0
for passnum in range(len(alist)-1,0,-1):
    for i in range(passnum):
        if alist[i]>alist[i+1]:
            times = times + 1 
            temp = alist[i]
            alist[i] = alist[i+1]
            alist[i+1] = temp
            print(alist)

return(times)

arrin = [5, 2, 4, 7, 7, 3]
print(bubbleSort(arrin))

输出：3

这个答案是不正确的，因为冒泡排序将3与相邻的7交换，将输出增加到3(应该是2)。

我该如何修改这段代码以满足示例的要求？

Answer 1

可以通过创建map来实现，其中key是数组的值，value是数组的索引。之后，循环输入列表，并比较当前值和排序列表中的值。如果是不同的：

-increment交换的数量

来自映射、映射排序列表的排序列表的-get索引

-in输入列表将当前值与排序后的当前值互换

更新mapcurrent list value=mapsorted当前列表值

这需要在输入列表和反转输入列表上执行。答案是以较小者为准。

def bubbleSort(alist):

 m = {}
 for i in range(len(alist)):
     m[alist[i]] = i 

 sorted_alist = sorted(alist)
 times = 0

 for i in range(len(alist)):
     if alist[i] != sorted_alist[i]:
         times +=1
         ind_to_swap = m[ sorted_alist[i] ]
         m[ alist[i] ] = m[ sorted_alist[i]]
         alist[i],alist[ind_to_swap] = sorted_alist[i],alist[i]
 return times

arrin = [2, 4, 7, 7, 3]
asc=bubbleSort(arrin)
desc=bubbleSort(list(reversed(arrin)))
print (min(asc,desc))