python - Python中的快速排序实现不间断运行

Question

这是我的快速排序算法。很简单

x = 0
def swap(list, a, b):
    temp = list[a]
    list[a] = list[b]
    list[b] = temp
    return list
def quicksort2(list, left, right):
    if right > left:
        global x
        x = x + 1
        print x , list, left, right
        l = left+1
        r = right
        while l <= r :
            while list[l] < list[left]:
                l = l + 1
            while list[r] > list[left]:
                r = r - 1
            if l < r:
                list = swap(list, l, r)
        list = swap(list, left, r)
        list = quicksort2(list, left, r-1);
        return quicksort2(list, r+1, right);
    return list

但是当我运行我的测试用例时

b = list([1, 2, 2, 3, 4, 5, 6, 12, 6, 32])
quicksort2(b, 0, len(b)-1)

结果是

1 [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 0 9
2 [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 1 9

并就此打住...任何人都有任何理由...

Answer 1

您是否尝试过在调试器下跟踪程序执行...？

循环永远运行，while l <= r因为经过几次递减r

• left == 1
• l == 2
• r == 2

和

• l不递增，因为list[2]不小于list[1]
• r不再递减，因为list[2]不大于list[1]
• 没有交换，因为l不小于r
• 并且循环将继续，因为l仍然等于r.......

Answer 2

我只是稍微修改了您的代码.. 发现了几个错误，其中一些已经被其他人提到了。其余的我不会经历。但是，您不必返回修改后的列表，因为 python 中的列表总是通过引用传递。

这应该有效：

def quicksort2(list, low, high):
    global x
    x = x + 1
    print x , list, low, high

    l = low
    r = high
    mid = list[(r + l) / 2]
    while l <= r:
      while list[l] < mid: l += 1
      while list[r] > mid: r -= 1
      if l <= r:
        list[l], list[r] = list[r], list[l] #swap(r,l)
        l += 1
        r -= 1

    if r > low: quicksort2(list, low, r);
    if l < high: quicksort2(list, l, high);


if __name__ == '__main__':
  x = 0
  b = [1, 2, 2, 3, 4, 5, 6, 12, 6, 32]
  quicksort2(b, 0, len(b)-1)
  print b