python - 在快速排序中弄错递归

Question

我在堆栈上看到了很多Python中Quicksort实现的相关疑惑，但找不到我要找的东西。我的问题特定于以下实现:

# Implementation of Quick-Sort algorithm in Python as taught in the course: Design and Analysis of Algorithms on Coursera

def QuickSort(array, length):
    if (length == 1 or length == 0):
        return

    numComparisons = 0
    numComparisons = numComparisons + length - 1

    print('array to be sorted is: ', array) 
    pivot = ChoosePivot(array,length)
    print('Pivot is: ', pivot)
    left    = 0
    right = length

    pivotIndex = Partition(array,left,right)

    print('array after partitioning step is: ', array)
    print('Pivot Index in the array is:', pivotIndex)

    QuickSort(array[:pivotIndex], pivotIndex)
    QuickSort(array[pivotIndex+1:], length-pivotIndex-1)
    print('Sorting is done! Final array is:', array)

    return numComparisons,array

def ChoosePivot(array,length):
    #For the first part of the question, choosing first element of array as pivot element
    return (array[0])

def Swap(array,elementLeft,elementRight):
    tmp = array[elementLeft]
    array[elementLeft] = array[elementRight]
    array[elementRight] = tmp
    return array

def Partition(array,left,right):
    pivot = array[left]
    i = left + 1
    j = left + 1    

    for j in range(right):
        if (array[j] < pivot):
            Swap(array,j,i)
            i = i + 1

    # send pivot to the correct position
    array = Swap(array,left,i-1)
    return (i-1)

array = [7,5,4,6,1,15,12]
numElements = len(array)  
numComp, array = QuickSort(array,numElements)
print('Total number of comparisons',numComp)
print(array)

所以思路是将数组的第一个元素作为枢轴元素，以枢轴元素为基础进行分区。 (这里不解释算法，因为我认为它在这里不是很重要)

在运行上面的代码时，我得到以下输出:

('array to be sorted is: ', [7, 5, 4, 6, 1, 15, 12])
('Pivot is: ', 7)
('array after partitioning step is: ', [1, 5, 4, 6, 7, 15, 12])
('Pivot Index in the array is:', 4)
('array to be sorted is: ', [1, 5, 4, 6])
('Pivot is: ', 1) 
('array after partitioning step is: ', [1, 5, 4, 6])
('Pivot Index in the array is:', 0)
('array to be sorted is: ', [5, 4, 6])
('Pivot is: ', 5)
--->('array after partitioning step is: ', [4, 5, 6])
--->('Pivot Index in the array is:', 1)
--->('Sorting is done! Final array is:', [4, 5, 6])
--->('Sorting is done! Final array is:', [1, 5, 4, 6])
('array to be sorted is: ', [15, 12])
('Pivot is: ', 15)
('array after partitioning step is: ', [12, 15])
('Pivot Index in the array is:', 1)
--->('Sorting is done! Final array is:', [12, 15])
--->('Sorting is done! Final array is:', [1, 5, 4, 6, 7, 15, 12])
('Total number of comparisons', 6)
[1, 5, 4, 6, 7, 15, 12]

所以，我无法理解为什么即使在显示排序已经发生之后，元素的位置也会发生变化(查看标有'--->的行' 在前)。

我觉得这与我传递数组的方式有关。任何帮助将不胜感激，如果需要更多详细信息，请告诉我

Answer 1

尝试改变:

array = Swap(array,left,i-1)

到:

Swap(array,left,i-1)

当你在函数内部给数组赋值时，python 会创建一个新数组，你会丢失对原始数组的引用

编辑:我认为问题是出于同样的原因对 QuickSort 的函数调用，传递带有开始/结束索引的数组而不是切割它。另一个问题是在分区函数中，你应该将 left 添加到 j。

这是完整的代码:

def QuickSort(array, start, end, length):
    if (end - start <=1):
        return

    numComparisons = 0
    numComparisons = numComparisons + length - 1

    print('array to be sorted is: ', array[start:end]) 
    pivot = ChoosePivot(array[start:end],length)
    print('Pivot is: ', pivot)
    left    = start
    right = end

    pivotIndex = Partition(array,left,right)

    print('array after partitioning step is: ', array[start:end])
    print('Pivot Index in the array is:', pivotIndex)

    QuickSort(array,start, pivotIndex, pivotIndex)
    QuickSort(array, pivotIndex+1, end, length-pivotIndex-1)
    print('Sorting is done! Final array is:', array[start:end])

    return numComparisons,array

def ChoosePivot(array,length):
    #For the first part of the question, choosing first element of array as pivot element
    return (array[0])

def Swap(array,elementLeft,elementRight):
    tmp = array[elementLeft]
    array[elementLeft] = array[elementRight]
    array[elementRight] = tmp
    return array

def Partition(array,left,right):
    pivot = array[left]
    i = left + 1
    j = left + 1    

    for j in range(right):
        if (array[left+j] < pivot):
            Swap(array,left+j,i)
            i = i + 1

    # send pivot to the correct position
    Swap(array,left,i-1)
    return (i-1)

array = [7,5,4,6,1,15,12]
numElements = len(array)  
numComp, array = QuickSort(array,0,6,numElements)
print('Total number of comparisons',numComp)
print(array)