“解排序”--快速排序

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，在arr中的索引x和y被切换时，
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

您不需要维护索引和元素的映射，只需在排序array.for示例时对索引进行排序：

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

然后，在对0 and 1进行排序时，只需交换unsortedArray.and获取sortedIndexes[1, 0, 2]，就可以通过sortedArray[1],sortedArray[0],sortedArray[2]获得原始数组。

def inplace_quick_sort(s, indexes, start, end):
    if start>= end:
        return
    pivot = getPivot(s, start, 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, indexes, start, left-1)
    inplace_quick_sort(s, indexes, left+1, end)
def customCmp(a, b):
        return a > b
def getPivot(s, start, end):
    return s[end]
if __name__ == '__main__':
    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]
    indexes = [i for i in range(len(arr))]
    inplace_quick_sort(arr,indexes, 0, 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))

Answer 2

你可以做你想做的事情，但是当我们在现实生活中不得不这样做的时候，我们通常会处理排序的比较函数，而不是交换函数。普通语言提供的排序例程通常具有内置的功能，因此不必编写自己的排序。

在此过程中，根据ref数组所指向的arr值的值对arr数组进行排序(下面称为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]

Answer 3

这并不可怕:你只是改变了你的引用用法。您的索引ref告诉您如何从原始列表中构建排序列表。但是，您使用它的方向正好相反:您已经将它应用到排序列表中，试图重建原始列表。你需要逆映射。

这足以让你解决你的问题吗？