使用选择排序对 python 中的数组进行排序。我该如何优化？

Question

在 HackerRank 上进行 this 挑战，并让这段代码通过了 15 个测试用例中的 10 个。由于超时错误而失败，这是 HackerRank 告诉您算法未优化的方式。我如何针对更大的输入数据将此代码优化为运行？

目标是计算出对未排序的数组进行排序所需的最少交换次数。

更新：数组中的每个元素都是不同的。

def minimum_swaps(arr):
"""Returns the minimum number of swaps to re-oder array in ascending order."""

    swaps = 0
    for val in range(len(arr) - 1, 0, -1):

        # Index of max value
        max_pos = 0
        for index in range(1, val + 1):

            if arr[index] > arr[max_pos]:
                max_pos = index

        # Skip if value is already in sorted position
        if max_pos == val:
            continue

        arr[val], arr[max_pos] = arr[max_pos], arr[val]
        swaps += 1

    return swaps

Answer 1

看代码。它有 2 个嵌套循环：

外层循环遍历位置 val.
内层循环找到应该在索引 val 处的值的索引，即 max_pos.

光是找索引就花了不少时间。相反，我将计算每个值的索引并将其存储在 dict.

中

index_of = {value: index for index, value in enumerate(arr)}

（请注意，因为 arr 中的所有值都是不同的，所以不应有重复的键）

同时准备一个排序版本的数组：这样可以更容易地找到最大值，而不必遍历数组。

sorted_arr = sorted(arr)

然后像原来的代码一样做剩下的事情：对于访问的每个索引，使用sorted_arr获取最大值，使用index_of获取其当前索引，如果它不合适然后交换。记得在交换时更新 index_of 字典。

该算法需要 O(n) 次操作（包括 dict indexing/modifying），加上 n 个元素的排序成本（大约 O(n log n)）。

注意：如果数组 arr 只包含小范围内的整数，将 index_of 设为数组可能比 dict 更快。

Answer 2

简短的回答是：实施归并排序。您使用的冒泡排序算法有一个 O(n^2) 运行时间，而合并排序有一个 O(log_2(n)) 运行时间。

使用选择排序对 python 中的数组进行排序。我该如何优化？

Using a selection sort to sort an array in python. How can I optimize?

python

algorithm

optimization

selection-sort