改进的快速排序算法(Python)

Question

我正在学习算法，这是我的快速排序的实现，请指导我如何进一步改进它，还有什么更好的方法来实现快速排序？

def quick_sort(arr):
    length = len(arr)
    if length <= 1:
        return arr

    else:
        pivot = arr.pop()

    items_greater = []
    items_lower = []

    for item in arr:
        if item > pivot:
            items_greater.append(item)
        else:
            items_lower.append(item)

    return quick_sort(items_lower)+[pivot]+quick_sort(items_greater)

Answer 1

不必要的else:

    if length <= 1:
        return arr

    else:
        pivot = arr.pop()

    ...

如果采用第一条路径，则该方法将退出。如果采用第二条路径，则继续执行该方法的其余部分。因此，您可以在else:子句中编写方法的其余部分：

    if length <= 1:
        return arr

    else:
        pivot = arr.pop()

        ...  # Now part of the else statement

或者，对于更多“左倾”代码，完全删除else:子句：

    if length <= 1:
        return arr

    pivot = arr.pop()

    ...

循环类似于本机

    items_greater = []
    items_lower = []

    for item in arr:
        if item > pivot:
            items_greater.append(item)
        else:
            items_lower.append(item)

在这里，您要创建一个列表，然后调用.append()在循环中重复向该列表添加项。Python有一个内置的机制来完成这个任务，速度更快。清单理解：

    items_greater = [item for item in arr if item > pivot]
    items_lower = [item for item in arr if not(item > pivot)]

为什么是not(item > pivot)，而不是简单的item <= pivot？在大多数情况下，后者将起作用。但也有一些问题和特殊情况。如果列表中有无穷大(+Inf，-Inf)或非a-数字(NaN)，则可以从两个列表中省略项。例如，如果列表包含一个NaN，那么NaN > 10和NaN <= 10都是False，这将导致该项没有被添加到items_greater或items_lower列表中！更糟糕的是，如果pivot碰巧变成了NaN，那么所有arr项都将被排除在外！类似地，如果列表中有两个无穷大，+Inf > +Inf和+Inf <= +Inf都是False。

PEP-8

佩普-8编码标准对如何格式化代码有很多建议。例如，二进制运算符应该在二进制运算符的两边都有一个空格。

    return quick_sort(items_lower)+[pivot]+quick_sort(items_greater)

应：

    return quick_sort(items_lower) + [pivot] + quick_sort(items_greater)

Answer 2

记录你的代码。在代码中：同时

quick_sort(arr)在某种程度上(排序为(升序“自然”)顺序(在arr_‘S元素对之间)，附加空间与输入大小成正比，处理时间与其平方不成正比)，

arr不是:在Python中，数组是什么？按照arr的使用方式，任何序列都会做得很好-

由于  缺少有用的docstring，我必须检查代码才能找到答案。

quick_sort(arr)是否保持等价物的相对顺序？

它会返回有用的东西吗？确切地说是什么？

它就位了吗？(修改arr (如果没有排序)(大多数快速排序do的实现)，与arr的S大小相比，使用可忽略不计的额外空间)

• 保持promises__，显式或implied_，您的代码使用与length平方成比例的额外空间，最坏的情况是:对于“生产”实现来说_not是可以容忍的。

虽然通过支点选择来防止不利分裂是可行的，但它比仅对非较大分区使用递归，并在非小分区上迭代，以减少对空间需求的不利影响。简单得多。