sorting - 快速排序两个 N 大小的相同值数组，通过比较一个到另一个

Question

我有两个数组 A 和 B，它们的值相同（所以它们的大小都是 N），但它们的顺序不同。我需要对两个数组进行排序，因此每个 i 的 A[i]==B[i] 。问题是我无法将 A 与自身进行比较，将 B 与自身进行比较。排序必须通过将 A[i] 与 B 中的值和 B[i] 与 A 中的值进行比较。

我尝试了这个版本的随机快速排序（反映使用的更新代码leftmark）leftmark + 1：

import random
import sys

def swap(a, l, r):
    a[l], a[r] = a[r], a[l]


def partition(arr, left, right, pivot):
    leftmark = left
    rightmark = right

    while 1:
        while leftmark <= rightmark and arr[leftmark] <= pivot:
            leftmark = leftmark + 1

        while arr[rightmark] >= pivot and rightmark >= leftmark:
            rightmark = rightmark -1

        if rightmark < leftmark:
            break
        temp = arr[leftmark]
        arr[leftmark] = arr[rightmark]
        arr[rightmark] = temp

    temp = arr[left]
    arr[left] = arr[rightmark]
    arr[rightmark] = temp

    return rightmark

def sort_arrays(arr1, arr2, low1, high1, low2, high2):
    if low1 < high1:
        # v = low2
        # pivotB = partition(arr2, low2, high2, arr1[v])
        # pivotA = partition(arr1, low1, high1, arr1[low1])
        # pivotB=0

        a1 = arr1[low1]
        pivotB = partition(arr2, low2, high2, a1)
        pivotA = partition(arr1, low1, high1, arr2[pivotB])

        sort_arrays(arr1, arr2, low1, pivotA - 1, low2, pivotB - 1)
        sort_arrays(arr1, arr2, pivotA + 1, high1, pivotB + 1, high2)

arr1 = [4, 2, 1, 5, 6, 3]
arr2 = [2, 3, 1, 4, 5, 6]

sort_arrays(arr1, arr2, 0, len(arr1) - 1, 0, len(arr2) - 1)
print('arr1', arr1)
print('arr2', arr2)

不幸的是，我没有做对，也无法找出我错过了什么。

标签： sortingquicksort

Answer 1

在partition函数中， 的初始值leftmark应该是left，而不是left + 1。