做有趣的快速排序，但有一些我不明白

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）可以是随机的只要它在范围内。

但是，如果我只取中点（即（左+右）/ 2），则快速排除不起作用。使用左侧价值，它的作品。

我在理解算法时错过了什么吗？

编辑：我只是意识到在stackoverflow中有一个'quicksort'标签。如果以前有人问过这个问题，我的道歉，请让我知道。我将结束这个问题。同时，我正在通过快速排序标记

Answer 1

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

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

Answer 2

您有midpoint = (right - left)/2。我认为你的意思是(right + left)/2，否则你的中点超出了给定的范围。