使用python的快速排序实现，无法弄清楚我在实现中错在哪里

Question

下面是我在 python 中实现快速排序的代码。但是我无法理解我在实施过程中出错的地方。有线索吗？

def quicksort(arr, size):
    partition(arr, size)

def partition(arr, size):
    if size <= 1:
        return

    left = 0
    right = size - 1
    pivot = arr[size/2]

    while left < right:
        while arr[left] < pivot:
            left += 1
        while arr[right] > pivot:
            right -= 1

        temp = arr[left]
        arr[left] = arr[right]
        arr[right] = temp

    partition(arr, left)
    partition(arr[left:], len(arr[left:]))
arr = [1,2,3,4,5,45,3,5,4,6]  
quicksort(arr, len(arr))

Answer 1

您正在对新切片进行排序：

partition(arr[left:], len(arr[left:]))

这些切片是新列表，而不是原始列表对象。您对这些所做的任何操作都不会显示在 arr.

的原始值中

如果您想就地进行排序，您需要传递数组中要排序的部分的起始值和终止值，而不是传递切片：

def quicksort(arr):
    partition(arr, 0, len(arr) - 1)

def partition(arr, start, stop):
    if stop - start < 1:
        return

    left = start
    right = stop
    pivot = arr[start + ((stop - start) / 2)]

    while left <= right:
        while arr[left] < pivot:
            left += 1
        while arr[right] > pivot:
            right -= 1

        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1

    partition(arr, start, right)
    partition(arr, left, stop)

我做了一些调整，调整了边界测试并使用元组赋值来交换两个元素。

此版本排序正确：

>>> def quicksort(arr):
...     partition(arr, 0, len(arr) - 1)
... 
>>> def partition(arr, start, stop):
...     if stop - start < 1:
...         return
...     left = start
...     right = stop
...     pivot = arr[start + ((stop - start) / 2)]
...     while left <= right:
...         while arr[left] < pivot:
...             left += 1
...         while arr[right] > pivot:
...             right -= 1
...         if left <= right:
...             arr[left], arr[right] = arr[right], arr[left]
...             left += 1
...             right -= 1
...     partition(arr, start, right)
...     partition(arr, left, stop)
... 
>>> arr = [1,2,3,4,5,45,3,5,4,6]  
>>> quicksort(arr)
>>> arr
[1, 2, 3, 3, 4, 4, 5, 5, 6, 45]

使用python的快速排序实现，无法弄清楚我在实现中错在哪里

quick sort implementation using python, can't figure out where I'm wrong in the implementation

python

quicksort