我喜欢考察面试者对递归和迭代的理解。
一般会先出一道如何使用递归求解，再出一道使用迭代求解上题。
本来准备用快速排序作为考题。想了想自己作为面试者，肯定是不会的。
就没有为难面试者。
但是作为算法分析题，这两种技巧还是需要掌握。
我自己就花时间调研了一下：
递归版：
def partition(A, lo, hi):
tmp_p = int(lo + (hi - lo) / 2)
tmp_value = A[tmp_p]
A[lo], A[tmp_p] = A[tmp_p], A[lo]
p = lo
for i in range(lo + 1, hi + 1):
if A[i] < tmp_value:
p += 1
A[i], A[p] = A[p], A[i]
A[p], A[lo] = A[lo], A[p]
return p
def quick_sort(lst, start, end):
if start < end:
split = partition(lst, start, end)
quick_sort(lst, start, split - 1)
quick_sort(lst, split + 1, end)
迭代版 (同一 partition)
def quicksort(A):
lo = 0
hi = len(A) - 1
range_queue = Queue()
range_queue.put([lo, hi])
while not range_queue.empty():
lo, hi = range_queue.get()
if lo < hi:
p = partition(A, lo, hi)
range_queue.put([lo, p - 1])
range_queue.put([p + 1, hi])
因为不是所有递归算法都可以转为迭代的，或者很难转化
上面快速排序的迭代，我是看到 Leslie Lamport 的视频，才知道。