我的快速排序算法实现中的错误

Question

最近想在Python中实现quicksort算法，但无法正常运行。即使程序对子数组进行排序，它也不会反映在主列表中。我是编程新手，谁能帮我理解我做错了什么部分或概念？

def swap(arr, right, left):
    temp = arr[right]
    arr[right] = arr[left]
    arr[left] = temp

def split_array(arr, right):
    left_half = arr[:right]
    right_half = arr[right:]
    a = (left_half, right_half)
    return a

def quick_sort(arr):
    if len(arr) >= 2:
        pivot = 0
        left_mark = pivot + 1
        right_mark = len(arr) - 1
        stop = True

        while stop:
            while arr[pivot] > arr[left_mark] and left_mark < right_mark:
                left_mark += 1
            while arr[pivot] < arr[right_mark] and left_mark < right_mark:
                right_mark -= 1
            if left_mark < right_mark:
                swap(arr, right_mark, left_mark)
                right_mark -= 1
                left_mark += 1
            else:
                if arr[pivot] > arr[right_mark]:
                    swap(arr, right_mark, pivot)
                stop = False
        left, right = split_array(arr, right_mark)
        quick_sort(left)
        quick_sort(right)
    return arr

array = [8, 6, 1, 7, 0, 5, 4, 3, 2, 1]
print(quick_sort(array))

Answer 1

你完全正确！ left 和 right 是 split_array 之后的独立实体，而不是原始 arr 的一部分。在 quick_sort(right) 之后说 arr=left+right。我认为这会做到。（需要检查 left 或 right 中只有一个元素的情况。）

Answer 2

改变这个：

left, right = split_array(arr, right_mark)
quick_sort(left)
quick_sort(right)

对此：

left, right = split_array(arr, right_mark)
arr = quick_sort(left) + quick_sort(right)

通常实施快速排序 "in-place" 以避免复制数组。您的实现会在每个步骤创建数组的完整副本，并且 returns 它，因此您需要自己重新组装这些片段。

更新

一个小改动，让您的算法就地生效：

def quick_sort(arr, start=0, end=None):
    if end is None: end = len(arr)-1
    if end > start:
        pivot = start
        left_mark = start + 1
        right_mark = end
        stop = True

        while stop:
            while arr[pivot] > arr[left_mark] and left_mark < right_mark:
                left_mark += 1
            while arr[pivot] < arr[right_mark] and left_mark < right_mark:
                right_mark -= 1
            if left_mark < right_mark:
                swap(arr, right_mark, left_mark)
                right_mark -= 1
                left_mark += 1
            else:
                if arr[pivot] > arr[right_mark]:
                    swap(arr, right_mark, pivot)
                stop = False
        quick_sort(arr, start, right_mark - 1)
        quick_sort(arr, right_mark, end)

array = [8, 6, 1, 7, 0, 5, 4, 3, 2, 1]
quick_sort(array) # in-place
print(array) # now sorted

IMO，下面更清楚也更符合算法的典型描述：

def quick_sort(arr, start=0, end=None):
    if end is None:
        end = len(arr) - 1

    if end <= start:
        return

    pivot = arr[start]
    left_mark = start - 1
    right_mark = end + 1

    while left_mark < right_mark:
        left_mark += 1
        while arr[left_mark] < pivot:
            left_mark += 1

        right_mark -= 1
        while arr[right_mark] > pivot:
            right_mark -= 1

        if left_mark < right_mark:
            arr[left_mark], arr[right_mark] = arr[right_mark], arr[left_mark]

    quick_sort(arr, start, right_mark)
    quick_sort(arr, right_mark + 1, end)

我的快速排序算法实现中的错误

Bug in my quick sort algorithm implementation

python

sorting

quicksort

python-2.7