无法实现Quicksort

Question

我已经使用Sedgewick在课程中教授的算法在Python中编写了Quicksort的实现。我无法正确分类。代码有什么问题？

def partition(a, lo, hi): 
    i = lo 
    j = hi 
    v = a[lo] 
    while(True): 
     while(a[i] < v): 
      i += 1 
      if (i == hi): break 

     while(a[j] > v): 
      j -= 1 
      if (j == lo): break 

     if (i >= j): break 

     a[i], a[j] = a[j], a[i] 

    a[lo], a[j] = a[j], a[lo] 
    return j 

def sort(a, lo, hi): 
    if (hi <= lo): 
     return 
    q = partition(a, lo, hi) 
    sort(a, lo, q-1) 
    sort(a, q+1, hi) 
    assert isSorted(a, lo, hi) 

def quick_sort(a): 
    shuffle(a) 
    sort(a, 0, len(a)-1) 
    assert isSortedArray(a) 

Answer 1

你可能会发现这些参考实现有助于理解你自己。

---

返回一个新的列表：

def qsort(array): 
    if len(array) < 2: 
     return array 
    head, *tail = array 
    less = qsort([i for i in tail if i < head]) 
    more = qsort([i for i in tail if i >= head]) 
    return less + [head] + more 

---

排序到位的列表：

def quicksort(array): 
    _quicksort(array, 0, len(array) - 1) 

def _quicksort(array, start, stop): 
    if stop - start > 0: 
     pivot, left, right = array[start], start, stop 
     while left <= right: 
      while array[left] < pivot: 
       left += 1 
      while array[right] > pivot: 
       right -= 1 
      if left <= right: 
       array[left], array[right] = array[right], array[left] 
       left += 1 
       right -= 1 
     _quicksort(array, start, right) 
     _quicksort(array, left, stop) 

---

生成排序从一个可迭代的项目：

def qsort(sequence): 
    iterator = iter(sequence) 
    head = next(iterator) 
    try: 
     tail, more = chain(next(iterator), iterator), [] 
     yield from qsort(split(head, tail, more)) 
     yield head 
     yield from qsort(more) 
    except StopIteration: 
     yield head 

def chain(head, iterator): 
    yield head 
    yield from iterator 

def split(head, tail, more): 
    for item in tail: 
     if item < head: 
      yield item 
     else: 
      more.append(item)