为了好玩做快速排序，但有些地方我不理解

Question

我只是想确保你知道，这不是一个作业问题。我只是为了好玩，可能还会写博客。

我正在按照这个维基页面实现快速排序的“原地”版本。

这是我写的代码：

# 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中的midpoint变量）可以是随机的，只要它在范围内。

但是，如果我只是取中点（也就是(left + right) / 2），快速排序就不管用了。用left值就可以。

我是不是在理解这个算法时漏掉了什么？

编辑：我刚意识到在StackOverflow上有一个“quicksort”的标签。如果这个问题之前有人问过，我很抱歉，请告诉我。我会关闭这个问题。同时我会去看看那些带有quicksort标签的问题。

Answer 1

你现在的计算方式是 midpoint = (right - left) / 2。我觉得你应该用 (right + left) / 2，否则你算出来的中点会在给定范围之外。

Answer 2

选择一个“基准元素”时会遇到一个麻烦，就是整数溢出的问题。如果你要排序的子数组的边界索引（也就是最左和最右的索引）非常大，简单的计算中间索引的方法 (left + right) / 2 可能会导致溢出，从而得到一个无效的基准索引。为了避免这个问题，可以使用 left + (right - left) / 2 来计算中间元素的索引，虽然这样算起来会稍微复杂一些。类似的问题在其他选择基准元素的方法中也会出现。

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