使用交换距离在选择排序后恢复原始数组

Question

我是CS的新手，我有一个非常艰巨的任务要做。这件事让我害怕。在选择排序过程中，我们可以获得交换距离——（未排序数组中元素的索引值）和（已排序数组中元素的索引值）之间的差异。我们可以这样找（这里是交换距离之和（我自己写的代码，计算交换距离之和是我之前的任务），但是我们很容易得到一个交换距离列表：

x = [int(i) for i in input().split()]
def sel_sort(a):
    swap_dist_sum = 0 
    for i in range(len(a)): 
        min_idx = i 
        for j in range(i+1, len(a)): 
            if a[min_idx] > a[j]: 
                min_idx = j       
        a[i], a[min_idx] = a[min_idx], a[i]
        swap_dist_sum += (min_idx - i)  # new index in sorted list - index from unsorted list
    return swap_dist_sum                # for each element
print(sel_sort(x))

这只是介绍（这种定义很少见）。我有 (n - 1) 个数字，它们是交换距离；第一次排序迭代中的第一个元素，第二次排序迭代中的第二个元素，依此类推。我必须恢复 n 个元素的未排序数组中元素的原始顺序。我不知道我应该做什么。也许你可以建议我 find/read/use library/little 代码 hints/etc.

Sample Input:  # swap distances
1 3 0 1

Sample Output:  # original list
4 1 3 5 2

我的第一步应该是这样的：

swap_dist_l = [int(i) for i in input().split()]  # list containing all swap distances
sorted_l = [i for i in range(1, len(swap_dist_l) + 2)]  # already sorted list

因此，我应该 unsorted_l 具有原始未排序的元素顺序。如果我的演讲难以理解，请见谅！ P.S。我没有找到任何 similar/duplicate 个问题。搜索不好请发个link！

Answer 1

让我们看看选择排序如何对一个简单的列表进行排序lst = [3,1,2]:

我们首先查看索引 0 并在索引 1 处找到最小的元素 1。

然后我们交换这些，即 lst[0], lst[1] = lst[1], lst[0]

然后我们查看索引 1 并在索引 2 处找到最小的元素 2。

然后我们交换这些，即 lst[1], lst[2] = lst[2], lst[1]

现在列表已经排序，我们有一个交换距离列表swap_dst = [1,1]

为了恢复列表，我们需要反转我们为排序所做的交换，或者换句话说，我们需要再次进行相同的交换，但顺序相反。

lst = [1,2,3]
lst[1], lst[2] = lst[2], lst[1]
lst[0], lst[1] = lst[1], lst[0]
print(lst) # [3,1,2]

所以你需要做的是找出如何使用交换距离来找到进行了哪些交换并再次进行这些交换。

Answer 2

你应该执行与你得到的交换距离相对应的交换，但顺序相反，所以从右边开始：

def unsort(data_l, swap_dist_l):
    for i, dist in reversed(list(enumerate(swap_dist_l))):
        # swap
        data_l[i+dist], data_l[i] = data_l[i], data_l[i+dist]

给定的例子调用如下：

swap_dist_l = [1, 3, 0, 1]
data_l = [i for i in range(1, len(swap_dist_l) + 2)]  # [1, 2, 3, 4, 5] 
unsort(data_l, swap_dist_l)
print(data_l)  # [4, 1, 3, 5, 2]

使用交换距离在选择排序后恢复原始数组

Restore original array after selection sort using swap distances

python

arrays

algorithm

sorting

selection-sort