（注意！虽然我知道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。索引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]
我的做法是这样的：
- 当在数组arr中索引为x和y处的元素a和b被交换时，
- 那么设置ref[x] = y和ref[y] = x。
谢谢！
最小可重现示例
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)