• 日常搜索
  • 端口查询
  • IP查询
  • 在线工具
  • 搜本站

如何用Python实现选择排序算法和线性搜索算法

如果给你一张纸,上面有 1000 个名字,你被要求找到一些名字,但这个列表不是按字母顺序排列的,那会很令人沮丧,不是吗?将该列表按顺序排列,虽然需要很长时间,但可以使查找名称变得更加容易。因此,让事物井井有条是我们人类的一种自然愿望,搜索这个列表显然比搜索一个无序列表花费更少的精力。 

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

  • 选择排序算法

  • 线性搜索算法

让我们转到计算机世界,可能需要搜索的列表非常庞大,即使使用快速的计算机,性能也可能会受到影响。在这种情况下,拥有合适的排序和搜索算法将是解决此类问题的方法。虽然排序是将值列表按顺序排列,但搜索是在列表中查找值的位置的过程。

为了弄清楚这个问题可能有多重要,让我向您展示美国伟大的计算机科学家唐纳德·克努斯 ( Donald Knuth ) 所说的话:

1960 年代的计算机制造商估计,当考虑到所有客户时,他们计算机上超过 25% 的运行时间都花在了分类上。事实上,在许多安装中,排序任务占据了一半以上的计算时间。从这些统计数据中,我们可以得出以下结论:(i)排序有很多重要的应用,或者(ii)很多人不应该排序,或者(iii)低效的排序算法已经被普遍使用。计算机编程卷。3:排序和搜索,第 3 页

如何用Python实现选择排序算法和线性搜索算法  第1张

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

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

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

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

Python 有一个sorted()函数可以从可迭代对象中创建一个新的排序列表。它还有一个内置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。但是,原名单保持不变。另一方面,该sort()方法None在我们调用它时返回marks_b。这是因为它就地对列表进行了排序。我们可以marks_b在最后打印时看到这一点。

您可以传递一些参数来修改排序行为。例如,将函数传递给key参数将使您能够控制用于对元素进行排序的标准。同样,您可以将reverse参数的值设置为 True 以反转元素的顺序。这是一个例子:






words = ["School", "Ambulance", "Cat", "Banana", "Hotel", "Penguin", "Total", "Lot"]
list.sort(words)
# ['Ambulance', 'Banana', 'Cat', 'Hotel', 'Lot', 'Penguin', 'School', 'Total']
print(words)
list.sort(words, key = lambda word: len(word))
# ['Cat', 'Lot', 'Hotel', 'Total', 'Banana', 'School', 'Penguin', 'Ambulance']
print(words)
list.sort(words, key = lambda word: len(word), reverse=True)
# ['Ambulance', 'Penguin', 'Banana', 'School', 'Hotel', 'Total', 'Cat', 'Lot']
print(words)

简单地调用sort()不带任何参数就可以按字母顺序对我们的单词列表进行排序。在第二种情况下,我们使用key参数告诉 Python 我们想要使用单词的长度作为我们的排序标准。最后,我们将值设置为reversetoTrue以反转排序单词的顺序。

选择排序算法

选择排序算法基于最小值或最大值的连续选择。假设我们有一个要按升序(从小到大的值)排序的列表。最小的元素将位于列表的开头,最大的元素将位于列表的末尾。

假设原始列表如下所示:

| 7 | 5 | 3.5 | 4 | 3.1 |

我们做的第一件事是在列表中找到最小值,在我们的例子中3.1

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

| 3.1 | 5 | 3.5 | 4 | 7 |

现在我们确定第一个元素在列表中的正确位置,我们从列表中的第二个元素开始重复上述步骤(找到最小值)。我们可以发现列表中的最小值(从第二个元素开始)是3.5。因此,我们现在3.55. 现在列表如下:

| 3.1 | 3.5 | 5 | 4 | 7 |

至此,我们可以确定第一个元素和第二个元素的位置是正确的。

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

| 3.1 | 3.5 | 4 | 5 | 7 |

所以我们现在可以确定前三个元素处于正确的位置,并且这个过程继续下去。

让我们看看如何在 Python 中实现选择排序算法(基于Isai Damier):



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

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




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)

在这种情况下,您应该得到以下输出:

[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):









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

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








bag = ['book','pencil','pen','note book','sharpener','rubber']
item = input('What item do you want to check for in the bag?')
itemFound = linearSearch(item,bag)
if itemFound:
print('Yes, the item is in the bag')
else:
print('Oops, your item seems not to be in the bag')

当您输入 时input,请确保它位于单引号或双引号之间(即'pencil')。'pencil'例如,如果您输入,您应该得到以下输出:

Yes, the item is in the bag

然而,如果您输入'ruler'作为输入,您将获得以下输出:

Oops, your item seems not to be in the bag

结论

正如我们所看到的,Python 再次证明自己是一种编程语言,它可以像我们在这里所做的那样轻松编写算法概念,处理排序和搜索算法。

如何用Python实现选择排序算法和线性搜索算法  第2张


文章目录
  • Python 中的内置排序方法和函数
  • 选择排序算法
  • 线性搜索算法
  • 结论
  • 发表评论