外壳排序，插入排序，气泡排序，选择排序算法

Question

在下面复制的代码中有七种排序算法。

前五种算法已经在这个链接中进行了回顾。

选择排序

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

气泡排序

Bubble排序算法反复使用两个循环替换输入列表中的相邻元素，如果它们的顺序不正确的话。

有效气泡排序

一个可能是稍微有效的版本的气泡排序算法是打破外部循环，当没有更多的交换，在整个过程中。例如，如果列表中有1,000万个元素，则可能在外部For循环中，例如，在超过10,000时，如果数组已经排序，则不再需要进行交换，因此循环的其余部分将不再需要继续。

插入排序

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

Shell排序

Shell排序只是插入排序的一个变体。在插入排序中，当元素必须向前移动时，涉及的动作太多，这是一个缺点。在Shell排序中，我们会将数组“h排序”作为h的一个大值，然后将h (sublist_increment)的值缩减到1。在Shell排序中，为“h排序”选择奇数并不是最好的方法，因为与偶数相比，存在更多的重叠。在下面的实现中，sublist_increment是一个奇数。

高效Shell排序

在Shell排序中，h值的选择非常重要。例如，[9, 6, 3, 1]不是h的适当值，因为3、6和9重叠。像这样的素数列表对于Shell排序算法来说是非常有效的。

将两个列表合并为一个新的列表

在这个算法中，我们首先使用上述的一种就地排序方法对两个列表进行排序，然后创建一个新列表，比较列表元素，最后使用三个简单的循环将它们放入新列表中：

• 如果两个列表都有要比较的元素
• 如果列表1中有要放置在新列表中的元素
• 如果列表2中有要放置在新列表中的元素

我一直试图在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 gets an integer/float list and returns 
    an ascendingly sorted integer/float list using Selection Sort Algorithm.

    Attributes:
    - In-Place Sort: 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 value found from the right unsorted side
    of the list with the 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:
            _swap_elements(input_list, element_index, min_index)

    return input_list


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

    Attributes:
    - In-Place Sort: 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 efficient_bubble_sort(input_list: List[T]) -> List[T]:
    """
    This method gets an integer/float list and returns 
    an ascendingly sorted integer/float list 
    using a slightly efficient 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.

    Attributes:
    - In-Place Sort: 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 swaps in iteration i, the array is already sorted.
        if number_of_swaps == 0:
            break

    return input_list


def _swap_elements(input_list: List[T], index1: int, index2: int) -> None:
    """
    Swaps the adjacent elements of the input list.
    """
    input_list[index1], input_list[index2] = input_list[index2], input_list[index1]


def insertion_sort(input_list: List[T]) -> List[T]:
    """
    This method gets an integer/float list and returns 
    an ascendingly sorted integer/float list using Shell Sort algorithm.

    Attributes:
    - 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 = 5) -> List[T]:
    """
    This method gets an integer/float list and returns 
    an ascendingly sorted integer/float list using Insertion Sort algorithm.

    Attributes:
    - In-Place: Space Complexity O(1)
    - Efficiency (Time Complexity O(N*(log N)^2 ) or O(N^1.25)
    - Good if N is large 
    - It reduces the number of movements as compared to Insertion Sort
    - Unstable Sort: Order of duplicate elements is not preserved
    """
    try:
        if sublist_increment // 2 == 0:
            return
    finally:

        # 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


def efficient_shell_sort(input_list: List[T]) -> List[T]:
    """
    This method gets an integer/float list and returns 
    an ascendingly sorted integer/float list using Insertion Sort algorithm.

    Here, we would use prime numbers, 
    somewhat distributed relative to the length of list to be sorted,
    such that we'd have optimal number of sublists and movements.

    Attributes:
    - In-Place: Space Complexity O(1)
    - Efficiency (Time Complexity O(N*(log N)^2 ) or O(N^1.25) 
    - Good if N is large 
    - It reduces the number of movements as compared to Insertion Sort
    - Unstable Sort: Order of duplicate elements is not preserved
    """

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

    # Assigns a list of prime numbers larger than three
    # as well as one, in descending order, for sublist increments of Shell Sort.
    sublist_increments = prime_numbers_and_one(length)[::-1]

    for sublist_increment in sublist_increments:

        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

    return input_list


def merge_two_sorted_lists(list1: List[T], list2: List[T]) -> List[T]:
    """
    This method sorts two integer/float lists first, then it'd merge them into a new list.

    Attributes:
    - Initial In-Place Sorting (Space Complexity O(1) = O(1) + O(1))
    - Secondary Not-In-Place Sorting (Space Complexity O(N+M) = O(N) + O(M))
    - Efficiency (Experimental Time Complexity O(N*(log N)^2 ) or O(N^1.25)
    - Good if N is large 
    - It reduces the number of movements as compared to Insertion Sort
    - Stable Sort: Order of duplicate elements would be preserved
    """

    # Sorts both arrays using for instance Optimized Shell Sort.
    efficient_shell_sort(list1)
    efficient_shell_sort(list2)

    # Assigns the lengths of two lists.
    length1, length2 = len(list1), len(list2)

    # Increments for the two lists and the third output list.
    i = j = k = 0

    # Creates a new list with size of lists one and two.
    merged_list = [None] * (length1 + length2)

    # If both lists are have elements to be inserted in the new merged array.
    while i <= length1 - 1 and j <= length2 - 1:
        if list1[i] < list2[j]:
            merged_list[k] = list1[i]
            i += 1
        else:
            merged_list[k] = list2[j]
            j += 1
        k += 1

    # If list one has elements to be inserted in the new merged array,
    # and list two is already done.
    while i <= length1 - 1:
        merged_list[k] = list1[i]
        i += 1
        k += 1

    # If list two has elements to be inserted in the new merged array,
    # and list one is already done.
    while j < length2 - 1:
        merged_list[k] = list1[j]
        j += 1
        k += 1

    return merged_list


def prime_numbers_and_one(array_length: int = 5, prime_numbers=[1]) -> List[T]:
    """
    This method returns a list of prime numbers larger and equal than three
    in addition to one, such as:
    [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    """
    if array_length <= 1:
        return prime_numbers

    number = 3
    while len(prime_numbers) in range(array_length):
        i = 2
        count_divisibles = 0
        for i in range(2, number):
            # If it is not a prime number:
            if number % i == 0:
                count_divisibles += 1
                break
            i += 1

        # If it is a prime number:
        if count_divisibles == 0:
            prime_numbers.append(number)
        number += 1

    return prime_numbers


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 = [
        ("Selection Sort", selection_sort),
        ("Bubble Sort", bubble_sort),
        ("Efficient Bubble Sort", efficient_bubble_sort),
        ("Insertion Sort", insertion_sort),
        # Wrap shell_sort into a lambda to make it a single-argument function for testing
        ("Shell Sort", lambda s: shell_sort(s, 5)),
        ("Efficient Shell Sort", efficient_shell_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)

    print(f"""Merging and sorting float and integer lists:\n
        {merge_two_sorted_lists(TEST_LIST_INTEGER, TEST_LIST_FLOAT)}""")

参考资料

• -代码检查外壳排序，插入排序，气泡排序，选择排序算法(Python)
• -代码评审排序算法(Python)
• -代码评审选择排序算法(Python)

Answer 1

以下几点：

• 如前所述，一旦lambda s: shell_sort(s, 5)的第二个参数具有默认值，就不再需要shell_sort中的lambda表达式，因为shell_sort(input_list)可以像其他函数一样调用该函数。因此，使用shell_sort就足够了。
• 这段代码写得不正确。def shell_sort(input_list: List，sublist_increment: int = 5) ->列表：->：if sublist_increment // 2 == 0:返回最后：.应该是这样的。def shell_sort(input_list: List，sublist_increment: int = 5) ->列表：# //是楼层划分，所以这是等价的形式。#我不确定这种逻辑是否真的正确。#也许应该用sublist\_increment < 2代替。如果0 <= sublist_increment < 2:引发ValueError(“.错误消息.”)剩下的代码..。
• 正如其他人在上一次评审中所建议的那样，这些函数修改了就地输入。所以最好不要返回一个列表(只需省略返回语句)。它的名字是: list_items =.func(list_items) .list_items保存输出，因此可以直接使用.
• 在小型程序中，测试用例可以更好地组织为一个列表或元组，并在测试期间迭代，类似于测试函数。它使添加新测试用例(手动构建或自动生成)变得更容易。对于较大的项目，需要其他工具，如pytest。GENERATED_INTEGER_TEST =# \_表示不小心变量GENERATED_FLOAT_TEST = test_cases =([“测试1(正常)”，]，[“测试2(排序列表)”，]，[“测试3(反向有序列表)”，]，]，.)#为test_case添加test_cases中的预期输出:test_case.append(排序(Test_case)).# func_description的实际测试，sorting_algorithms中的func : test_description，test_input，expected_output in test: output = test_input func( output ) message = "passed“，如果output == expected_output else "failed”print(test_description )，信息) ..。如果需要，可以使用test\_input和output打印输入和输出。还要注意，需要设计测试用例以涵盖通过不同代码分支进行的不同类型的输入，包括可能导致错误的边缘案例。在这里，只要相应的整数测试成功，浮点数上的测试就会成功。因此，不需要对整数和浮点数重复每次测试。换句话说，只要比较操作符定义得很好，输入的类型就不会导致被测试函数的不同行为。您需要寻找其他变体，如上面的示例代码所示。另外，示例代码还演示了使用random模块生成随机数，因此不再需要scipy。