python - "Unsorting"快速排序

Question

(快速说明!虽然我知道在 Python 中有很多排序选项，但这段代码更像是一个通用的概念验证，稍后将移植到另一种语言，所以我不会能够使用任何特定的 Python 库或函数。

另外，您提供的解决方案不一定非得按照我下面的做法。)

背景

我有一个快速排序算法，我正在尝试实现一种方法以允许稍后“取消排序”已排序元素的新位置。也就是说，如果元素 A在索引 x并排序到索引 y ，然后“指针”(或者，根据您的术语、引用或映射)数组更改其在索引 x 处的值来自 x至 y .

更详细:
您以一个数组开始程序，arr ，有一些给定的数字集。该数组随后通过快速排序算法运行，因为对数组进行排序对于将来对其进行处理很重要。

这个数组的顺序很重要。因此，您有另一个数组 ref ，其中包含原始数组的索引，这样当您将引用数组映射到数组时，将再现数组的原始顺序。

在数组排序之前，数组和映射是这样的:

arr = [1.2, 1.5, 1.5, 1.0, 1.1, 1.8]
ref = [0,   1,   2,   3,   4,   5]
--------
map(arr,ref) -> [1.2, 1.5, 1.5, 1.0, 1.1, 1.8]

您可以看到 ref 的索引 0指向 arr 的索引 0 , 给你 1.2 . ref 的索引 1指向 arr 的索引 1 , 给你 1.5 , 等等。

算法排序时，ref应该重新排列，以便当您根据上述过程映射它时，它会生成预排序的 arr :

arr = [1.0, 1.1, 1.2, 1.5, 1.5, 1.8]
ref = [2,   3,   4,   0,   1,   5]
--------
map(arr,ref) -> [1.2, 1.5, 1.5, 1.0, 1.1, 1.8]

同样，ref 的索引 0|是2，所以映射数组的第一个元素是arr[2]=1.2 . ref 的索引 1是 3，所以映射数组的第二个元素是 arr[3]=1.5 , 等等。

问题

我的代码的当前实现非常适合排序，但可怕重新映射 ref .

给定相同的数组 arr ，我的程序的输出如下所示:

arr = [1.0, 1.1, 1.2, 1.5, 1.5, 1.8]
ref = [3,   4,   0,   1,   2,   5]
--------
map(arr,ref) -> [1.5, 1.5, 1.0, 1.1, 1.2, 1.8]

这是一个问题，因为这个映射绝对不等于原来的:

[1.5, 1.5, 1.0, 1.1, 1.2, 1.8] != [1.2, 1.5, 1.5, 1.0, 1.1, 1.8]

我的方法是这样的:

1. 当元素 a和 b , 在指数 x和 y在arr已切换，
2. 然后设置ref[x] = y和 ref[y] = x .

这行不通，我想不出另一个不需要 O(n^2) 的解决方案时间。

谢谢!

最小可复制示例

testing = [1.5, 1.2, 1.0, 1.0, 1.2, 1.2, 1.5, 1.3, 2.0, 0.7, 0.2, 1.4, 1.2, 1.8, 2.0, 2.1]

# This is the 'map(arr,ref) ->' function
def print_links(a,b):
    tt = [a[b[i]-1] for i in range(0,len(a))]
    print("map(arr,ref) -> {}".format(tt))

    # This tests the re-mapping against an original copy of the array
    f = 0
    for i in range(0,len(testing)):
        if testing[i] == tt[i]:
            f += 1

    print("{}/{}".format(f,len(a)))

def quick_sort(arr,ref,first=None,last=None):
    if first == None:
        first = 0
    if last == None:
        last = len(arr)-1

    if first < last:
        split = partition(arr,ref,first,last)
        quick_sort(arr,ref,first,split-1)
        quick_sort(arr,ref,split+1,last)

def partition(arr,ref,first,last):
    pivot = arr[first]

    left = first+1
    right = last

    done = False
    while not done:
        while left <= right and arr[left] <= pivot:
            left += 1

        while arr[right] >= pivot and right >= left:
            right -= 1

        if right < left:
            done = True
        else:
            temp = arr[left]
            arr[left] = arr[right]
            arr[right] = temp

            # This is my attempt at preserving indices part 1
            temp = ref[left]
            ref[left] = ref[right]
            ref[right] = temp

    temp = arr[first]
    arr[first] = arr[right]
    arr[right] = temp

    # This is my attempt at preserving indices part 2
    temp = ref[first]
    ref[first] = ref[right]
    ref[right] = temp

    return right

# Main body of code
a = [1.5,1.2,1.0,1.0,1.2,1.2,1.5,1.3,2.0,0.7,0.2,1.4,1.2,1.8,2.0,2.1]
b = range(1,len(a)+1)

print("The following should match:")
print("a = {}".format(a))
a0 = a[:]
print("ref = {}".format(b))
print("----")
print_links(a,b)

print("\nQuicksort:")
quick_sort(a,b)
print(a)

print("\nThe following should match:")
print("arr = {}".format(a0))
print("ref = {}".format(b))
print("----")
print_links(a,b)

Answer 1

您可以按照您的要求去做，但是当我们在现实生活中必须做这样的事情时，我们通常会弄乱排序的比较函数而不是交换函数。常见语言提供的排序例程通常具有内置的功能，因此您不必编写自己的排序。

在此过程中，您对 ref 进行排序数组(下面称为 order)，由 arr 的值它指向的值。生成相同的 ref您已有数组，但没有修改 arr .

使用此顺序映射会对原始数组进行排序。您希望它对已排序的数组取消排序，这就是您的代码无法正常工作的原因。

您可以反转此顺序以获得 ref你原来要找的数组，或者你可以离开 arr未分类并将其映射到 order当您需要时订购。

arr = [1.5, 1.2, 1.0, 1.0, 1.2, 1.2, 1.5, 1.3, 2.0, 0.7, 0.2, 1.4, 1.2, 1.8, 2.0, 2.1]

order = range(len(arr))
order.sort(key=lambda i:arr[i])

new_arr = [arr[order[i]] for i in range(len(arr))]

print("original array = {}".format(arr))
print("sorted ordering = {}".format(order))
print("sorted array = {}".format(new_arr))

ref = [0]*len(order)
for i in range(len(order)):
    ref[order[i]]=i

unsorted = [new_arr[ref[i]] for i in range(len(ref))]
print("unsorted after sorting = {}".format(unsorted))

输出:

original array = [1.5, 1.2, 1.0, 1.0, 1.2, 1.2, 1.5, 1.3, 2.0, 0.7, 0.2, 1.4, 1.2, 1.8, 2.0, 2.1]
sorted ordering = [10, 9, 2, 3, 1, 4, 5, 12, 7, 11, 0, 6, 13, 8, 14, 15]
sorted array = [0.2, 0.7, 1.0, 1.0, 1.2, 1.2, 1.2, 1.2, 1.3, 1.4, 1.5, 1.5, 1.8, 2.0, 2.0, 2.1]
unsorted after sorting = [1.5, 1.2, 1.0, 1.0, 1.2, 1.2, 1.5, 1.3, 2.0, 0.7, 0.2, 1.4, 1.2, 1.8, 2.0, 2.1]