python - 为什么我的快速排序实现的边界是错误的？

Question

我正在尝试在 python 中实现快速排序：

def partition(ls):
  if len(ls) == 0:
    return 0
  pivot = ls[0]
  i = 0
  j = 1
  while j < len(ls):
    if ls[j] <= pivot:
      i += 1
      temp = ls[i]
      ls[i] = ls[j]
      ls[j] = temp
    j += 1
  ls[0] = ls[i]
  ls[i] = pivot
  return i

assert(partition([1,2]) == 0)
assert(partition([3,2]) == 1)
assert(partition([3,2,1,4,5]) == 2)
assert(partition([]) == 0)
assert(partition([45]) == 0)

def sort(ls):
  if len(ls) == 0:
    return
  pivotIndex = partition(ls)
  sort(ls[0:pivotIndex])
  sort(ls[(pivotIndex + 1):len(ls)])

ls = [54,1,3,2,4,3,5,4]
sort(ls)
print ls

根据我的断言，我知道我的分区算法工作正常。

但是，我的排序函数返回错误的结果。这段代码打印

[4, 1, 3, 2, 4, 3, 5, 54]

递归调用排序的边界应该是什么？我的目标是将子列表分区到枢轴左侧，将子列表分区到枢轴右侧，两者都不包括枢轴本身。

Answer 1

Python 中一些已知良好的排序，带有可选的 Cython，包括 Quicksort。顺便说一句，查看性能比较；您可能会发现 Quicksort 不如内置的 Timsort 有吸引力： http ://stromberg.dnsalias.org/~strombrg/sort-comparison/

Answer 2

sort(ls[0:pivotIndex])
sort(ls[(pivotIndex + 1):len(ls)])

切片复制列表的一部分，因此在递归调用中，您不会修改原始列表。因此只有第一个partition修改列表。