如果给你一张纸,上面有 1000 个名字,你被要求找到一些名字,但这个列表不是按字母顺序排列的,那会很令人沮丧,不是吗?将该列表按顺序排列,虽然需要很长时间,但可以使查找名称变得更加容易。因此,让事物井井有条是我们人类的一种自然愿望,搜索这个列表显然比搜索一个无序列表花费更少的精力。
Python 中的内置排序方法和函数
选择排序算法
线性搜索算法
让我们转到计算机世界,可能需要搜索的列表非常庞大,即使使用快速的计算机,性能也可能会受到影响。在这种情况下,拥有合适的排序和搜索算法将是解决此类问题的方法。虽然排序是将值列表按顺序排列,但搜索是在列表中查找值的位置的过程。
为了弄清楚这个问题可能有多重要,让我向您展示美国伟大的计算机科学家唐纳德·克努斯 ( Donald Knuth ) 所说的话:
1960 年代的计算机制造商估计,当考虑到所有客户时,他们计算机上超过 25% 的运行时间都花在了分类上。事实上,在许多安装中,排序任务占据了一半以上的计算时间。从这些统计数据中,我们可以得出以下结论:(i)排序有很多重要的应用,或者(ii)很多人不应该排序,或者(iii)低效的排序算法已经被普遍使用。计算机编程卷。3:排序和搜索,第 3 页
在本教程中,我将向您展示如何实现选择排序算法和线性搜索算法。
但在我们开始之前,如果您只想在 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 我们想要使用单词的长度作为我们的排序标准。最后,我们将值设置为reverse
toTrue
以反转排序单词的顺序。
选择排序算法
选择排序算法基于最小值或最大值的连续选择。假设我们有一个要按升序(从小到大的值)排序的列表。最小的元素将位于列表的开头,最大的元素将位于列表的末尾。
假设原始列表如下所示:
| 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):
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 再次证明自己是一种编程语言,它可以像我们在这里所做的那样轻松编写算法概念,处理排序和搜索算法。
发表评论