python - QuickSort 是为了好玩，但有些地方我不明白

Question

只是想向您保证，这不是作业问题。我这样做只是为了一些乐趣，也可能是为了写博客。

我正在根据此 wiki page 实现快速排序的“就地”版本.

这是我写的代码:

# solution 2

def swap(arr, left, right):
    try:
        tmp = arr[left]
        arr[left] = arr[right]
        arr[right] = tmp
    except IndexError:
        print "!IndexError: left, right", left, right
        raise

def partition(arr, left, right, pindex):
    pivot = arr[pindex]
    swap(arr, right, pindex)
    npindex = left
    for i in range(left, right+1): # +1 so the last item is included
        if arr[i] < pivot:
            swap(arr, i, npindex)   
            npindex += 1
    swap(arr, npindex, right)
    return npindex

def qs(arr):
    qs2(arr, 0, len(arr)-1)
    return arr

def qs2(arr, left, right):
    if left < right:
        # midpoint = (right - left) / 2
        midpoint = left # this works.
        nindex = partition(arr, left, right, midpoint)
        qs2(arr, left, nindex-1)
        qs2(arr, nindex+1, right)

def test():
    test = [23, 45, 12, 1, 3, -9, 67, 122, 8, 2, 0]
    res = qs(list(test))
    print "start\t", test
    print "end\t", res

if __name__ == "__main__":
    test() 

我不明白的是，根据维基百科，枢轴的选择(变量midpoint inside function qs2)可以是随机的，只要它在界限。

但是，如果我只取中点(即 (left + right)/2 )，则快速排序不起作用。使用 left 值，它有效。

我在理解算法时是否遗漏了什么？

编辑:我刚刚意识到在 stackoverflow 中有一个“快速排序”标签。如果之前有人问过这个问题，我深表歉意，请告诉我。我会关闭这个问题。同时，我正在使用快速排序标签来解决这些问题

Answer 1

Selecting a pivot element is also complicated by the existence of integer overflow. If the boundary indices of the subarray being sorted are sufficiently large, the naive expression for the middle index, (left + right)/2, will cause overflow and provide an invalid pivot index. This can be overcome by using, for example, left + (right-left)/2 to index the middle element, at the cost of more complex arithmetic. Similar issues arise in some other methods of selecting the pivot element.

应该是(left + right)/2，而不是(right - left)/2。维基百科解释说，使用 left + (right - left)/2 是为了避免整数溢出。