选择排序算法(Python)

Question

选择排序

选择排序算法通过从列表的右侧未排序部分查找最小元素并将其放在列表的左排序部分来排序列表。该算法在给定的输入列表中维护两个子列表.1)已经排序的子列表。 2)未排序的剩余子列表。在选择排序的每一次迭代中，从未排序子列表中选择最小元素并移动到排序子列表中。

我一直在尝试使用Python魔术函数(如__iter__ )来实现选择排序算法，如果您检查代码以进行更改/改进，我会很感激。

码

"""
This class returns an ascending sorted integer list
for an input integer list using Selection Sort method.

Sorting: 
- In-Place (space complexity O(1))
- Efficiency (time complexity O(N^2))
- Unstable Sort (Order of equal elements might change)


"""
class SelectionSort(object):
    """
    """
    def __init__(self, input_list:list)->list:
        self.input_list = input_list
        self.__iter__()

    def __iter__(self)->list:
        """
        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
        input_length = len(self.input_list)

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

            min_index = element_index

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

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

        print(self.input_list)
        return self.input_list


SelectionSort([10, 4, 82, 9, 23, -30, -45, -93, 23, 23, 23, 0, -1])

极客的

解决方案--

我不太确定排序稳定性，它说下面的实现是不稳定的。但是，选择排序可以使其稳定：

import sys 
A = [64, 25, 12, 22, 11] 

for i in range(len(A)): 

    min_index = i 
    for j in range(i+1, len(A)): 
        if A[min_index] > A[j]: 
            min_index = j 

    A[i], A[min_index] = A[min_index], A[i] 

for i in range(len(A)): 
    print("%d" %A[i])

参考

• 选择排序(极客对极客的选择)
• 选择排序(Wiki)

Answer 1

我同意@Reinderien的观点，这不应该是一个类。在构造函数中可以看到这方面的证据：

def __init__(self, input_list:list)->list:
    self.input_list = input_list
    self.__iter__()

构建对象(并调用构造函数)只是为了调用self.__iter__()。这里没有理由只为排序列表创建一个对象。如果您需要在各种类型或其他类型之间保持某种状态(我不知道您为什么要这样做)，那么它可能是合适的。

我还要指出，在使用__init__和__iter__时，您至少要违反两个“契约”：

• __init__必须不返回：__init__()不能返回非无值；这样做将导致在运行时引发TypeError。现在，你实际上什么也没有回，但你的类型暗示是说你是。如果要使用类型暗示，提示应该使所涉及的类型更加清晰，而不是作出错误的声明。
• __iter__应该返回一个迭代器：这个方法应该返回一个新的迭代器对象，它可以迭代容器中的所有对象--问题是，您正在返回一个列表，而一个列表不是迭代器，它是一个可迭代的(它有一个迭代器)。这不仅仅是理论上的问题。注意:类T: def __iter__(self)：在T()中返回n的1，2，3：print(n) # TypeError: iter()返回'list‘类型的非迭代器

使用"dunder“方法可以帮助您编写干净的代码，但前提是您没有滥用它们。在尝试使用方法之前，一定要阅读文档并了解方法的用途和契约。

在类型提示的主题上，您可以使用TypeVar来允许类型检查器查看元素类型在排序函数中的进出之间的一致性。在将类变成独立函数之后，基本上有：

def selection_sort(input_list: list) -> list:

问题是，它没有告诉检查器input_list中的元素类型与selection_sort返回的列表之间的关系。这可能导致一些微妙的问题，在这些问题上，它无法帮助您处理类型：

lst: List[int] = [1, 2, 3]
sorted_list = selection_sort(input_list)
x = sorted_list[0]  # It has no idea what type x is

您可以通过引入一个TypeVar来解决这个问题，它告诉它元素类型保持一致。我还在从使用list改为使用List，因为list似乎还不支持泛型：

from typing import List, TypeVar

T = TypeVar("T")

# The sort returns the same element type T that it received
def selection_sort(input_list: List[T]) -> List[T]:
    . . .

现在，它能够推断出x的类型，并且可以提供更好的完成和类型警告。

Answer 2

这基本上是很不错的。只有几件事：

删除-

    print(self.input_list)

你应该把打印留给打电话的人。

还有-为什么要上课？这实际上归结为一个单一的函数。您只有一个成员变量，并且只有一个方法。

还有一个问题--这门课的结果是“令人惊讶的突变”。迭代它会修改它的一个成员。这是一个简单函数的另一个参数。如果你继续上课，你可能

• 将已排序的输出缓存为独立于输入列表的列表，和/或
• 存储输入列表的副本，而不是输入列表本身。

最后一点说明了另一个问题--假设您正在被传递一个列表，这不是严格必要的；您所需要的只是一个可迭代的列表。如果从输入中创建列表，则对调用方的要求较少。