python-3.x - 计算排序数组的最小交换次数（选择排序太慢）

Question

我正在尝试计算最小交换次数，同时使用整数对无序数组进行排序。

一个例子。

输入;

array = [4, 3, 1, 2]
calculate_swaps(array)

输出;

# Initial array = [4, 3, 1, 2]
# 1st iteration = [1, 3, 4, 2]
# 2nd iteration = [1, 2, 4, 3]
# 3rd iteration = [1, 2, 3, 4]

3 # minimum amount of swaps to sort the array.

我在下面尝试了“选择排序算法”。它有效。由于它以 O(n2) 时间复杂度执行，我的算法需要太多时间来计算大数组（大小 = 50,000）。

这是我的代码。我怎样才能克服这个性能问题？

def calculate_swaps(arr):
    min_swaps = 0
    minimum = 0
    for i in range(len(arr) - 1):
        if (arr[i] == i + 1):
            continue

        minimum = i

        for j in range(i + 1, len(arr)):
            # Find the smallest value
            if arr[j] < arr[minimum]:
                minimum = j

        # Swap
        if minimum != i:
            arr[minimum], arr[i] = arr[i], arr[minimum]
            min_swaps += 1

    return(min_swaps)

标签： python-3.xsorting