Shell排序，插入排序，气泡排序，选择排序算法(Python)

Question

有一个后续问题可用：undefined。

选择排序

选择排序算法通过从列表的右侧(未排序部分)查找最小元素，并将其放在列表的左边(排序部分)来排序列表(数组)。

气泡排序

Bubble排序算法通过重复交换相邻元素来工作，如果它们的顺序不正确的话。

优化气泡排序

一个优化版本的气泡排序算法是打破循环，当没有更多的交换，在整个过程中。

插入排序

插入排序算法以一种时间方式在一个项中生成最终排序数组。与更高级的算法(如快速排序、堆排序或合并排序)相比，它在大列表上的效率较低，但它提供了一些优点，如实现简单、小数据集的效率和排序稳定性。

Shell排序(优化插入排序)

Shell排序只是插入排序的一个变体，其中元素只向前移动一个位置。当一个元素必须向前移动时，涉及的动作太多，这是一个缺点。在Shell排序中，我们将数组“h -排序”为h，然后将h (sublist_increment)的值缩减到1。

我一直试图在Python中实现上述算法，并根据以前的评论对其进行了修改，如果您能对其进行其他任何更改/改进，我将不胜感激。

码

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

T = TypeVar('T')


def selection_sort(input_list: List[T]) -> List[T]:
    """
    This method returns an ascending sorted integer list
    for an input integer/float list using Selection Sort Algorithm.

    Sorting:
    - In-Place (space complexity O(1))
    - Efficiency (Time Complexity => O(N^2))
    - Unstable Sort (Order of duplicate elements is not preserved)


    Iterates through the list and swaps the min from the right side
    to sorted elements from the left side of the list.
    """

    # Is the length of the list.
    length = len(input_list)

    # Iterates through the list to do the swapping.
    for element_index in range(length - 1):

        min_index = element_index

        # Iterates through the list to find the min index.
        for finder_index in range(element_index + 1, length):
            if input_list[min_index] > input_list[finder_index]:
                min_index = finder_index

        # Swaps the min value with the pointer value.
        if element_index is not min_index:
            input_list[element_index], input_list[min_index] = input_list[min_index], input_list[element_index]

    return input_list


def bubble_sort(input_list: List[T]) -> List[T]:
    """
    This method returns an ascending sorted integer list
    for an input integer/float list using regular Bubble Sort algorithm.

    Sorting:
    - In-Place (Space Complexity => O(1))
    - Efficiency (Time Complexity => O(N^2))
    - Stable Sort (Order of equal elements does not change)
    """

    length = len(input_list)
    for i in range(length - 1):
        for j in range(length - i - 1):
            if input_list[j] > input_list[j + 1]:
                _swap_elements(input_list, j, j + 1)

    return input_list


def optimized_bubble_sort(input_list: List[T]) -> List[T]:
    """
    This method returns an ascending sorted integer list
    for an input integer/float list using an Optimized Bubble Sort algorithm.

    For optimization, the Bubble Sort algorithm stops if in a pass there would be no further swaps
    between an element of the array and the next element.

    Sorting:
    - In-Place (Space Complexity => O(1))
    - Efficiency (Time Complexity => O(N^2))
    - Stable Sort (Order of equal elements does not change)
    """

    # Assigns the length of to be sorted array.
    length = len(input_list)

    for i in range(length - 1):
        number_of_swaps = 0
        for j in range(length - i - 1):
            if input_list[j] > input_list[j + 1]:
                _swap_elements(input_list, j, j + 1)
                number_of_swaps += 1

        # If there is no further swap in iteration i, the array is already sorted.
        if number_of_swaps == 0:
            break

    return input_list


def _swap_elements(input_list: List[T], current_index: int, next_index: int) -> None:
    """
    Swaps the adjacent elements.
    """
    input_list[current_index], input_list[next_index] = input_list[next_index], input_list[current_index]


def insertion_sort(input_list: List[T]) -> List[T]:
    """
    This method returns an ascending sorted integer list
    for an input integer/float list using a Insertion Sort algorithm.

    Sorting:
    - In-Place (space complexity O(1))
    - Efficiency (time complexity O(N^2) - Good if N is small - It has too many movements)
    - Stable Sort (Order of duplicate elements is preserved)
    """

    # Assigns the length of to be sorted array.
    length = len(input_list)

    # Picks the to-be-inserted element from the right side of the array, starting with index 1.
    for i in range(1, length):
        element_for_insertion = input_list[i]

        # Iterates through the left sorted-side of the array to find the correct position for the element to be inserted.
        j = i - 1
        while j >= 0 and input_list[j] > element_for_insertion:
            input_list[j + 1] = input_list[j]
            j -= 1

        # Inserts the element.
        input_list[j + 1] = element_for_insertion

    return input_list


def shell_sort(input_list: List[T], sublist_increment: int) -> List[T]:
    if sublist_increment // 2 == 0:
        print("Please select an odd number for sublist incrementation. ")
        return

    # Assigns the length of to be sorted array.
    length = len(input_list)

    while sublist_increment >= 1:

        for i in range(sublist_increment, length):
            element_for_insertion = input_list[i]

            # Iterates through the left sorted-side of the array to find the correct position for the element to be inserted.
            j = i - sublist_increment
            while j >= 0 and input_list[j] > element_for_insertion:
                input_list[j + sublist_increment] = input_list[j]
                j -= sublist_increment

            # Inserts the element.
            input_list[j + sublist_increment] = element_for_insertion

        # Narrows down the sublists by two increments.
        sublist_increment -= 2

    return input_list


if __name__ == "__main__":

    # Generates a random integer list
    TEST_LIST_INTEGER = random.sample(range(-1000, 1000), 15)

    # Generates a random float list
    TEST_LIST_FLOAT = stats.uniform(-10, 10).rvs(10)

    print(f"The unsorted integer input list is:\n{TEST_LIST_INTEGER}\n-----------------------------------\n")
    print(f"The unsorted float input list is:\n{TEST_LIST_FLOAT}\n-----------------------------------\n")

    # Tests the Selection Sort Algorithm:
    print("---------------------------------")
    print(f"Selection Sort (Integer): {selection_sort(TEST_LIST_INTEGER.copy())}")
    print(f"Selection Sort (Float): {selection_sort(TEST_LIST_FLOAT.copy())}")

    # Tests the Optimized Bubble Sort Algorithm:
    print("---------------------------------")
    print(f"Optimized Bubble Sort (Integer): {optimized_bubble_sort(TEST_LIST_INTEGER.copy())}")
    print(f"Optimized Bubble Sort (Float): {optimized_bubble_sort(TEST_LIST_INTEGER.copy())}")
    # Tests the Bubble Sort Algorithm:
    print("---------------------------------")
    print(f"Bubble Sort (Integer): {bubble_sort(TEST_LIST_INTEGER.copy())}")
    print(f"Bubble Sort (Float): {bubble_sort(TEST_LIST_INTEGER.copy())}")
    # Tests the Insertion Sort Algorithm:
    print("---------------------------------")
    print(f"Insertion Sort (Integer): {insertion_sort(TEST_LIST_INTEGER.copy())}")
    print(f"Insertion Sort (Float): {insertion_sort(TEST_LIST_INTEGER.copy())}")

    # Tests the Shell Sort Algorithm:
    print("---------------------------------")
    print(f"Shell Sort (Integer): {shell_sort(TEST_LIST_INTEGER.copy(), 5)}")
    print(f"Shell Sort (Float): {shell_sort(TEST_LIST_INTEGER.copy(), 5)}")

参考资料

• -代码评审排序算法(Python)
• -代码评审选择排序算法(Python)
• 外壳排序-极客的极客
• 泡泡分类-极客为极客
• 气泡排序- Wiki
• 选择排序-极客为极客
• 选择排序- Wiki
• 插入排序- Wiki

Answer 1

就地排序

您的selection_sort是一个就地排序，因此不需要返回与给定的列表相同的列表。事实上，返回列表是令人困惑的，因为它在某种程度上意味着您将返回与您所得到的内容不同的内容。您可以在这里和类似的函数中删除返回。

失效模式

if sublist_increment // 2 == 0:
    print("Please select an odd number for sublist incrementation. ")
    return

这有问题。你在打印-但是如果来电者不想让你打印呢？您正在返回None -但是如果调用者想要捕获一个异常并尝试使用不同的输入怎么办？在这里，您应该是raise异常，而不是打印和返回None。

，不要重复，

# Tests the Selection Sort Algorithm:
print("---------------------------------")
print(f"Selection Sort (Integer): {selection_sort(TEST_LIST_INTEGER.copy())}")
print(f"Selection Sort (Float): {selection_sort(TEST_LIST_FLOAT.copy())}")

# Tests the Optimized Bubble Sort Algorithm:
print("---------------------------------")
print(f"Optimized Bubble Sort (Integer): {optimized_bubble_sort(TEST_LIST_INTEGER.copy())}")
print(f"Optimized Bubble Sort (Float): {optimized_bubble_sort(TEST_LIST_INTEGER.copy())}")
# Tests the Bubble Sort Algorithm:
print("---------------------------------")
print(f"Bubble Sort (Integer): {bubble_sort(TEST_LIST_INTEGER.copy())}")
print(f"Bubble Sort (Float): {bubble_sort(TEST_LIST_INTEGER.copy())}")
# Tests the Insertion Sort Algorithm:
print("---------------------------------")
print(f"Insertion Sort (Integer): {insertion_sort(TEST_LIST_INTEGER.copy())}")
print(f"Insertion Sort (Float): {insertion_sort(TEST_LIST_INTEGER.copy())}")

# Tests the Shell Sort Algorithm:
print("---------------------------------")
print(f"Shell Sort (Integer): {shell_sort(TEST_LIST_INTEGER.copy(), 5)}")
print(f"Shell Sort (Float): {shell_sort(TEST_LIST_INTEGER.copy(), 5)}")

这应该是一个执行五次的循环。可以在包含

• 排序算法的名称，以及
• 对除TEST_LIST之外传递参数的包装函数的引用

测试

似乎存在bug或未实现的机制，因为“整型”和“浮点”测试没有区别。它们都是整数测试。

此外，这些只是测试，因为开发人员必须使用他们的眼球并手动验证输出。您应该考虑编写真正的自动化测试:传递方法一个已知的输入(就像您已经做的那样)，并断言输出等于预期的输出。

Answer 2

除了@Reinderien的评论之外，还有以下几点：

测试

• 测试代码对每个函数都有一些重复的语句。最好把它放在这样的for循环中: sorting_algorithms = (“壳牌”，选择_(排序)，.#包裹壳_将其排序为lambda，使其成为用于测试的单参数函数(“shell排序”，lambda s: shell)_排序(S，5)作为描述，func以sorting_algorithms：.打印(f“{description} (Integer)：{func(TEST_LIST_INTEGER.copy())}")
• 由于通常期望排序函数的调用方只提供要排序的列表，所以最好让所有其他参数都是可选的: def shell_sort(input_list: ListT，sublist_increment: int = 5) -> ListT：这将为sublist_increment参数设置一个默认值。通过这一更改，不再需要上面代码中用于shell_sort的lambda包装器(如果要测试使用非默认参数调用函数，仍然需要它)。
• random.sample执行采样而不进行替换。因此，每个输入只发生一次，并且输出列表中没有重复项。对于测试目的来说，这是不可取的，因为预期这些函数将与重复的元素一起工作。应该使用random.choice。
• 对于相同的任务使用两个模块scipy.stats和random是有点不寻常的--生成随机数。前者更强大，但在这种情况下，两者都是足够的。

编码风格

• 既然您已经定义了函数_swap_elements，那么当需要该功能时，最好在任何地方使用它。selection_sort函数还没有使用它。
• 函数_swap_elements不需要知道输入索引对调用者意味着什么。只要索引有效，该函数就能工作。因此，在这个声明中，def _swap_elements(input_list: ListT，current_index: int，next_index: int)参数名current_index和next_index可以更改为更一般的名称，如index1和index2。
• 有一些超长的队伍。虽然不一定一定要符合PEP 8推荐的79焦耳限值，但最好不要让线路太长。长注释可以写在多行。类似于这个打印的语句(f“未排序的整数输入列表is:\n{TEST_LIST_INTEGER}\n-----------------------------------\n")可以写入此打印(”未排序整数输入列表为：“，TEST_LIST_INTEGER，“”sep=‘\n’或者这个(Python自动加入相邻的没有分隔符的字符串)打印(“未排序的整数输入列表是：\n”f"{TEST_LIST_INTEGER}\n“)--”f“”{}\n“-”未排序的整数输入列表是：\n“”f“”{}\n“

Answer 3

正如另一个答案在@莱因德林中所指出的，您的一些函数修改了列表的位置，而有些则没有。这已经不是很好了，但是所有的docstring都声称函数返回一个排序列表，这意味着它不会对任何输入进行变异，这使情况更加恶化。

如果您将其修复(例如，by)，作为一种粗糙的黑客，首先复制列表，您将立即对代码的可测试性进行改进。突然之间，对算法进行性能比较变得非常容易：

为了公平起见，我在所有函数中添加了行input_list = input_list[:]。我还为sublist_increment提供了5的默认值，如@GZ0在答案中建议的那样，并附带了内置的sorted函数(带有包含input_list = input_list[:]行的包装器)。

以下几点值得注意：

• 很难超越内置的排序函数(特别是用Python而不是C编写的代码)。它比您编写的函数快3到400倍。对于性能关键的应用程序总是倾向于内置函数，除非您有一些奇怪的边缘案例和为特定情况优化的排序函数。
• 您的所有函数似乎不仅在绝对值上较慢，而且在相对范围内也是如此。它的渐近行为看起来与sorted的斜率不同，后者是\mathcal{O}(n\log n)。正如在评论中 by @GZ0所提到的，您的算法都是\mathcal{O}(n^2)。
• 请注意，我被限制在长度小于1000的列表，因为否则运行时会变得太长。
• 您称之为“优化”气泡排序的函数似乎没有比正常的气泡排序更好的性能。
• 相反，shell排序(优化的插入排序)实际上比正常的插入排序执行得更好。