python - 做快速排序是为了好玩，但有一些我不明白的事情

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() 

我不明白的是，根据维基百科，枢轴的选择(函数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.

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