python – “Unsorting”一个Quicksort

(快速注意！虽然我知道有很多选项可以在 Python中进行排序,但这段代码更像是一个通用的概念验证,后来将被移植到另一种语言,所以我将无法使用任何特定的Python图书馆或功能.

此外,您提供的解决方案不一定要遵循我的方法.)

背景

我有一个快速排序算法,我正在尝试实现一种方法,以便以后“取消”排序元素的新位置.也就是说,如果元素A位于索引x并且被排序为索引y,则“指针”(或者,取决于您的术语,引用或映射)数组将其索引x处的值从x更改为y.

更详细：
您使用数组arr开始程序,并使用一组给定的数字.此数组稍后通过快速排序算法运行,因为对数组进行排序对于将来对其进行处理非常重要.

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

在对数组进行排序之前,数组和映射如下所示：

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

你可以看到ref的索引0指向arr的索引0,给你1.2. ref的索引1指向arr的索引1,给你1.5,依此类推.

当算法被排序时,ref应该重新排列,这样当你按照上面的过程映射它时,它会生成预先排序的arr：

arr = [1.0,1.2,1.8]
ref = [2,1.8]

同样,ref的索引0是2,所以映射数组的第一个元素是arr [2] = 1.2. ref的索引1是3,因此映射数组的第二个元素是arr [3] = 1.5,依此类推.

问题

我的代码的当前实现非常适合排序,但对于重新映射ref非常糟糕.

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

arr = [1.0,1.8]
ref = [3,ref) -> [1.5,1.8]

这是一个问题,因为这个映射肯定不等于原始映射：

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

我的方法是：

>当转换元素a和b,在arr中的索引x和y时,
>然后设置ref [x] = y和ref [y] = x.

这不起作用,我想不出另一个不需要O(n ^ 2)时间的解决方案.

谢谢！

最简单的可重复实例

testing = [1.5,1.3,2.0,0.7,0.2,1.4,1.8,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,first,last)
        quick_sort(arr,split-1)
        quick_sort(arr,split+1,last)

def partition(arr,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,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)

unsortedArray =  [1.2,2.1]
unsortedIndexes = [0,2]
sortedAray = [1.2,2.1]

def inplace_quick_sort(s,indexes,start,end):
    if start>= end:
        return
    pivot = getPivot(s,end)#it's should be a func
    left = start
    right = end - 1
    while left <= right:
        while left <= right and customCmp(pivot,s[left]):
        # s[left] < pivot:
            left += 1
        while left <= right and customCmp(s[right],pivot):
        # pivot < s[right]:
            right -= 1
        if left <= right:
            s[left],s[right] = s[right],s[left]
            indexes[left],indexes[right] = indexes[right],indexes[left]
            left,right = left + 1,right -1
    s[left],s[end] = s[end],s[left]
    indexes[left],indexes[end] = indexes[end],indexes[left]
    inplace_quick_sort(s,left-1)
    inplace_quick_sort(s,left+1,end)
def customCmp(a,b):
        return a > b
def getPivot(s,end):
    return s[end]
if __name__ == '__main__':
    arr = [1.5,2.1]
    indexes = [i for i in range(len(arr))]
    inplace_quick_sort(arr,len(arr)-1)
    print("sorted = {}".format(arr))
    ref = [0]*len(indexes)
    for i in range(len(indexes)):
        #the core point of Matt Timmermans' answer about how to construct the ref
        #the value of indexes[i] is index of the orignal array
        #and i is the index of the sorted array,#so we get the map by ref[indexes[i]] = i
        ref[indexes[i]] = i
    unsorted = [arr[ref[i]] for i in range(len(ref))]
    print("unsorted after sorting = {}".format(unsorted))