在Python中进行分类和搜索-Python教程-PHP中文网

Sorting and Searching in Python

想象一下，你手里有一张纸，上面列着1000个名字，你需要找到其中一个，但这份名单并非按字母顺序排列。这将非常令人沮丧，不是吗？虽然整理这份名单需要很长时间，但它能使查找名字变得容易得多。因此，将事物排序是我们人类的自然愿望，搜索已排序的列表显然比搜索无序列表更省力。

在计算机世界中，需要搜索的列表可能非常庞大，即使是速度很快的计算机，性能也可能会受到影响。在这种情况下，合适的排序和搜索算法将是解决此类问题的方案。排序是将值列表按顺序排列的过程，而搜索是在列表中查找值位置的过程。

为了说明这个问题的重要性，让我向您展示伟大的美国计算机科学家唐纳德·克努斯（Donald Knuth）所说的内容：

20世纪60年代的计算机制造商估计，考虑到所有客户，他们的计算机运行时间的25%以上都花在了排序上。事实上，在许多安装案例中，排序任务占用了超过一半的计算时间。从这些统计数据中，我们可以得出结论：（i）排序有许多重要的应用，或者（ii）许多人在不应该排序的时候进行排序，或者（iii）低效的排序算法已被普遍使用。——《计算机程序设计艺术》第3卷：排序和搜索，第3页

在本教程中，我将向您展示如何实现选择排序算法和线性搜索算法。

但在我们开始之前，如果您只想在Python代码中进行排序和搜索，我将向您展示内置的方法。

Python中的内置排序方法和函数

您可以使用Python创建许多排序算法。这是一个很好的学习练习，但对于生产应用程序，您应该坚持使用Python中的内置存储函数和方法。

Python有一个list.sort()方法，您可以使用它来就地排序列表。Python幕后使用的排序算法称为Timsort。它是一种基于插入排序和合并排序的混合排序算法，在许多现实生活中都能提供出色的性能。以下是如何使用这两个函数和方法的示例：

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

登录后复制

您可能会注意到上述代码中的一些情况。sorted()函数返回一个新的已排序列表，而不会更改原始列表marks_a。但是，原始列表保持不变。另一方面，当我们在marks_b上调用sort()方法时，它返回None。

您可以传递一些参数来修改排序行为。例如，将一个函数传递给reverse参数，sorted()函数在没有任何参数的情况下按字母顺序对我们的单词列表进行排序。在第二种情况下，我们使用reverse=True来反转已排序单词的顺序。

选择排序算法

选择排序算法基于最小值或最大值的连续选择。假设我们有一个列表，我们希望按升序（从小到大）对其进行排序。最小的元素将位于列表的开头，最大的元素将位于列表的结尾。

假设原始列表如下所示：

| 7 | 5 | 3.5 | 4 | 3.1 |

我们首先要做的是找到列表中的最小值，在本例中是3.1。

找到最小值后，将该最小值与列表中的第一个元素交换。也就是说，将3.1与7交换。列表现在将如下所示：

| 3.1 | 5 | 3.5 | 4 | 7 |

现在我们确定第一个元素在列表中的正确位置，我们从列表的第二个元素开始重复上述步骤（查找最小值）。我们可以发现列表中（从第二个元素开始）的最小值是3.5。因此，我们现在将3.5与5交换。列表现在变为：

| 3.1 | 3.5 | 5 | 4 | 7 |

此时，我们确定第一个元素和第二个元素都在其正确的位置。

现在，我们检查列表其余部分中的最小值，即从第三个元素5开始。列表其余部分中的最小值是4，我们现在将其与5交换。因此，列表变为：

| 3.1 | 3.5 | 4 | 5 | 7 |

因此，我们现在确定前三个元素位于正确的位置，并且该过程以此方式继续。

让我们看看如何在Python中实现选择排序算法（基于Isai Damier）：

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

登录后复制

让我们通过在上述脚本的末尾添加以下语句来测试该算法：

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k

        swap(aList, least, i)

def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

登录后复制

在这种情况下，您应该得到以下输出：

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

线性搜索算法

线性搜索算法是一个简单的算法，其中检查列表中的每个项目（从第一个项目开始），直到找到所需的项目或到达列表的末尾。

线性搜索算法在Python中的实现如下（基于Python School）：

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print(my_list)

登录后复制

让我们测试代码。在上面的Python脚本的末尾输入以下语句：

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found

登录后复制

输入input时，确保它位于单引号或双引号之间（即'pencil'）。例如，如果您输入'pencil'，则应该得到以下输出：

Yes, the item is in the bag

而如果您输入'ruler'作为输入，则将得到以下输出：

Oops, your item seems not to be in the bag