QuickSort批评

Question

这是我第一次尝试快速排序，并在寻找一些有用的批评，我如何使我的代码更好。谢谢

def manSort(self, unSorted):
    if len(unSorted) <= 1:
        return unSorted
    else:
        greater = []
        less = []
        pivots = unSorted[len(unSorted)/2]
        pivotPlace = [pivots]
        for i in range(len(unSorted)):
            if unSorted[i] < pivots:
                less.append(unSorted[i])
            elif unSorted[i] > pivots:
                greater.append(unSorted[i])
            elif i == len(unSorted)/2:
                pass
            else:
                pivotPlace.append(unSorted[i])

        return self.manSort(less) + pivotPlace + self.manSort(greater)

Answer 1

看上去很不错。有几件小事是可以改进的。为了清楚起见，我避免使用pivotPlace这个名称，而选择equal，因为函数就是这样做的，它将值放置在那里，与支点相等。

正如Janne所提到的，for循环可以替换为遍历未排序列表中的项的循环。

地板分区而不是常规分区确保这也适用于Python 3。

最后，可以完全删除else (如果初始条件为真，控制永远不会流到那里)，将代码进一步拉到基线。

def manSort(unsorted):
    if len(unsorted) <= 1:
        return unsorted

    less = []
    equal = []
    greater = []
    pivot = unsorted[len(unsorted) // 2]
    for item in unsorted:
        if item < pivot:
            less.append(item)
        elif item > pivot:
            greater.append(item)
        else:
            equal.append(item)

    return manSort(less) + equal + manSort(greater)

Answer 2

您没有遵循PEP 8样式指南，这是python的正式样式。要解决这个问题：

• 标识符应该是lower_case_with_underscore
• 函数应该是lower_case_with_underscore
• 类应该是FullCamelCase

你在重复列表中的错误，这根本不是节奏曲。使用普通的for代替：

for element in sequence:
     # work with element

如果还需要索引，则使用内置的enumerate：

for index, element in enumerate(sequence):
    # work with element and its index

您的方法实际上是一个函数。它从不使用self，除非执行递归调用，因此您应该考虑将其置于类之外，或者将此方法设置为staticmethod。

一些标识符有奇怪的名称(例如pivot_place)。

最后，您的代码不是最优的。它使用O(nlog(n))空间而不是O(log(n))。快速排序的通常实现使用partition算法，该算法在不创建临时lesser、greater列表的情况下将元素移到原地。有了这样一个函数，快速排序的整个实现将变成：

def quicksort(sequence, start=0, end=None):
    if end is None:
        end = len(sequence)
    if end - start > 1:
        q = partition(sequence, start, end)
        quicksort(sequence, start, q)
        quicksort(sequence, q+1, end)

在其中，partition可以是这样的：

def partition(sequence, start, end):
    pivot = sequence[start]
    sequence[start], sequence[end-1] = sequence[end-1], pivot
    # i: index of the last "lesser than" number.
    i = start - 1
    # j: index to scan the array
    for j in range(start, end-1):
        element = sequence[j]
        if element <= pivot:
            i += 1
            sequence[i], sequence[j] = sequence[j], sequence[i]
    # move pivot in the correct place
    i += 1
    sequence[i], sequence[end-1] = sequence[end-1], sequence[i]
    return i

在这段代码中，我确实对索引进行了迭代，因为迭代是从某个索引start开始的。在您的情况下，您总是对整个序列进行迭代。

注意，这个实现在一般情况下使用O(log(n))内存，在最坏情况下使用O(n)，但是最坏的情况可能是一个问题，因为它是在输入被排序的时候。

为了提高性能，您应该将partition函数随机化。您只需更改最初的行：

import random

def partition(sequence, start, end):
    # use a random element instead of the first element.
    pivot_index = random.randint(start, end-1)
    pivot = sequence[pivot_index]
    sequence[pivot_index], sequence[end-1] = sequence[end-1], pivot
    # same as before.

Answer 3

有一个不必要的复杂问题:在循环之前将pivots放在pivotPlace中，然后在循环中跳过它。

您还可以直接循环unSorted，而不是使用索引循环。

pivotPlace = []
for item in unSorted:
    if item < pivots:
        less.append(item)
    elif item > pivots:
        greater.append(item)
    else:
        pivotPlace.append(item)