做QuickSort是为了好玩，但有件事我不明白

Question

只是想确保这是而不是的家庭作业问题。我这样做只是为了一些乐趣，可能是为了博客。

我正在按照这个wiki页面实现快速排序的‘就地’版本。

下面是我编写的代码：

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

我不明白的是，根据维基百科的说法，只要参数在一定范围内，就可以随意选择枢轴(变量中点 it qs2)。

但是，如果我只取中点(即(左+右) /2 )，则快速排序不起作用。使用左值，它可以工作。

我是不是错过了理解算法的东西？

编辑：我刚刚意识到堆栈溢出中有一个‘快速排序’的标签。如果以前有人问过这个问题，我很抱歉，请告诉我。我将结束这个问题。同时，我正在用快速排序标签来回答这些问题。

Answer 1

由于存在整数溢出，因此选择pivot元素也很复杂。如果要排序的子数组的边界索引足够大，则中间索引(左+右)/2的朴素表达式将导致溢出，并提供无效的枢轴索引。例如，可以通过使用左+(右左)/2索引中间元素来克服这一问题，而代价是更复杂的算法。在选择枢轴元素的其他一些方法中也会出现类似的问题。

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

Answer 2

你有midpoint = (right - left) / 2。我认为你指的是(right + left) / 2，否则你的中点就超出了给定的界限。