快速排序算法(Python)

Question

QuickSort是一个除法和征服算法，它选择一个元素作为“枢轴”，并将给定的列表围绕这个pivot进行分区。对于如何以不同的方式选择枢轴，快速排序有许多不同的版本：

• 始终选择第一个元素作为枢轴(在下面实现)
• 总是选择最后一个元素作为枢轴。
• 选择一个随机元素作为枢轴
• 选择中间为枢轴

只是为了练习，我已经实现了快速排序算法，如果您想回顾它并提供任何更改/改进建议，请这样做，我对此表示感谢。

码

import random
from typing import TypeVar, List
from scipy import stats

T = TypeVar('T')


def quick_sort(input_list: List[T]) -> List[T]:
    """"
    Returns an ascendingly sorted list;
    Input variable is an integer or float array;
    Theoretical Complexity: O(N*Log N) Time and O(N) Memory
    """

    sort(input_list, 0, len(input_list) - 1)
    return input_list


def sort(input_list: List[T], start_index: int, end_index: int) -> None:
    """Recursively sorts the two pivot-divided sublists;"""
    if start_index >= end_index:
        return
    pivot_index = partition(input_list, start_index, end_index)
    sort(input_list, start_index, pivot_index - 1)
    sort(input_list, pivot_index + 1, end_index)


def partition(input_list: List[T], start_index: int, end_index: int) -> int:
    """
    Returns the end index; Partitions a list into two sublists;
    """
    pivot = input_list[start_index]

    i, j = start_index + 1, end_index

    while i <= j:
        while input_list[i] < pivot and i < end_index:
            i += 1
        while input_list[j] > pivot:
            j -= 1

        if i < j:
            temp = input_list[i]
            input_list[i] = input_list[j]
            input_list[j] = temp
            i += 1
            j -= 1
        else:
            break

    input_list[start_index] = input_list[j]
    input_list[j] = pivot

    return j


if __name__ == "__main__":

    # Creates a dash line string and a new line for in between the tests.
    delimiter = "-" * 70 + "\n"

    # Generates a random integer list.
    test_list_integer = random.sample(range(-100, 100), 15) * 3
    print(f"""The unsorted integer array is:
        {test_list_integer}""")
    print(delimiter)

    # Generates a random float list.
    test_list_float = stats.uniform(0, 100).rvs(45)
    print(f"""The unsorted float array is:
        {test_list_float}""")
    print(delimiter)

    # Sample float/integer test list for input.
    integer_float_input = list(test_list_integer + test_list_float)

    # Sample float/integer test list for output.
    integer_float_output = sorted(integer_float_input)

    sorting_algorithms = [
        ("Quick Sort", quick_sort)
    ]

    # Testing
    for description, func in sorting_algorithms:
        if (func(integer_float_input.copy()) == integer_float_output):
            print(f"{description} Test was Successful.")
        else:
            print(f"{description} Test was not Successful.")
        print(f"""{description} (Integer):
            {func(test_list_integer.copy())}""")
        print(f"""{description} (Float):
            {func(test_list_float.copy())}""")
        print(delimiter)

参考

• 快速排序-极客为极客
• 快速排序- Wiki

Answer 1

我完全支持提供_docstring_s。

对于不熟悉快速排序算法的人来说，我怀疑所提供的文档字符串是否有用：

• 返回一个向上排序的列表；这是一个新的列表还是作为输入提供的?(方法docstring应该以a phrase ending in a period [prescribing the] method's effect as a command ("Do this", "Return that"), not as a description开头)
• 输入变量是整数数组或浮点数数组；不适用于字符串吗?-- python教程名称list_s和_tuple_s as standard sequence data types -- _is an array? (类型提示确实提示了预期的含义)，对于一般的python类型暗示，以及与文档字符串的“交互”，我没有一个有用的直觉。
• 理论复杂性: O(N×Log )时间和O(N)内存没有进一步限定所要求的界，我认为它们是最坏的情形界。
• 递归地对两个支点划分的子列表进行排序；只查看方法接口，但我没有看到_two sublists_ (这恰好是我在方法docstring中希望看到的第一件事情-- The docstring for a function or method should summarize its behavior and document its arguments, …没有强调这一点)。

在代码中有几样东西不完全是pythonic的

• a和b的交换通常使用隐含列表表示: a, b = b, a
• 与两个序列相同类型的连续不变的序列总是会产生一个新的对象。 (第一个操作数的类型，如果不是相同的类型(？))--没有看到在list()中封装test_list_integer + test_list_float的意图。

我更喜欢

if not <condition>:
    <get out of here>
<operate>

结束

if <condition>:
    <operate>
else:
    <get out of here>