Python 数据结构和算法实用指南（一）（1）

原文：zh.annas-archive.org/md5/66ae3d5970b9b38c5ad770b42fec806d

译者：飞龙

协议：CC BY-NC-SA 4.0

前言

数据结构和算法是信息技术和计算机科学工程学习中最重要的核心学科之一。本书旨在提供数据结构和算法的深入知识，以及编程实现经验。它专为初学者和中级水平的研究 Python 编程的研究生和本科生设计，并通过示例解释复杂的算法。

在这本书中，您将学习基本的 Python 数据结构和最常见的算法。本书将提供 Python 的基本知识，并让读者深入了解数据算法。在书中，我们提供 Python 实现，并解释它们与几乎每个重要和流行的数据结构算法的关系。我们将研究提供数据分析中最常见问题的解决方案的算法，包括搜索和排序数据，以及能够从数据中提取重要统计信息。通过这本易于阅读的书，您将学习如何创建复杂的数据结构，如链表、栈、堆和队列，以及排序算法，包括冒泡排序、插入排序、堆排序和快速排序。我们还描述了各种选择算法，包括随机选择和确定性选择。我们详细讨论了各种数据结构算法和设计范例，如贪婪算法、分治算法和动态规划，以及它们如何在实时应用中使用。此外，我们使用直观的图示例解释了树和图等复杂数据结构的概念。您还将学习各种重要的字符串处理和模式匹配算法，如 KMP 和 Boyer-Moore 算法，以及它们在 Python 中的简单实现。您将学习在预处理、建模和转换数据等任务中使用的常见技术和结构。

拥有对数据结构和算法的深入理解的重要性不言而喻。这是一个重要的武器库，可以帮助您理解新问题并找到优雅的解决方案。通过更深入地了解算法和数据结构，您可能会发现它们的用途远远超出最初的意图。您将开始考虑您编写的代码以及它对内存量的影响。Python 进一步打开了许多专业人士和学生欣赏编程的大门。这种语言很有趣，而且在描述问题时非常简洁。我们利用这种语言的大众吸引力来研究许多广泛研究和标准化的数据结构和算法。本书以简洁地介绍 Python 编程语言开始。因此，在阅读本书之前并不需要您了解 Python。

本书的读者对象

本书适用于正在学习初级或中级数据结构和算法课程的 Python 开发人员。本书还适用于所有那些参加或曾参加数据结构和算法课程的本科和研究生工程学生，因为它涵盖了几乎所有在这门课程中学习的算法、概念和设计。因此，本书也可以作为数据结构和算法课程的教材。本书还是一种对于希望使用特定数据结构部署各种应用程序的通用软件开发人员的有用工具，因为它提供了存储相关数据的有效方式。它还提供了学习复杂算法的实用和简单的方法。

假设读者具有一些 Python 的基本知识。但是，这并不是强制性的，因为本书在快速概述 Python 及其面向对象的概念。本书不需要读者具有任何与计算机相关的概念的先验知识，因为所有的概念和算法都有足够详细的解释，配有大量的例子和图示。大多数概念都是通过日常场景来解释，以便更容易理解概念和算法。

充分利用本书

1. 本书中的代码需要在 Python 3.7 或更高版本上运行。
   
2. Python 交互环境也可以用来运行代码片段。
   
3. 建议读者通过执行本书中提供的代码来学习算法和概念，以便更好地理解算法。
   
4. 本书旨在给读者提供实际的经验，因此建议您为所有的算法进行编程，以便充分利用本书。
   

下载示例代码文件

您可以从您在www.packt.com的账户中下载本书的示例代码文件。如果您在其他地方购买了本书，您可以访问www.packt.com/support并注册，文件将直接发送到您的邮箱。

您可以按照以下步骤下载代码文件：

1. 在www.packt.com上登录或注册。
   
2. 选择“支持”选项卡。
   
3. 点击“下载代码和勘误”。
   
4. 在搜索框中输入书名，然后按照屏幕上的说明操作。
   

下载文件后，请确保使用最新版本的以下软件解压或提取文件夹：

• WinRAR/7-Zip for Windows
  
• Zipeg/iZip/UnRarX for Mac
  
• 7-Zip/PeaZip for Linux
  

本书的代码包也托管在 GitHub 上，网址为github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition。如果代码有更新，将在现有的 GitHub 存储库上进行更新。

我们还提供了来自我们丰富书籍和视频目录的其他代码包，可在github.com/PacktPublishing/上找到。去看看吧！

下载彩色图片

我们还提供了一个 PDF 文件，其中包含本书中使用的屏幕截图/图表的彩色图片。您可以在这里下载：www.packtpub.com/sites/default/files/downloads/9781788995573_ColorImages.pdf

使用的约定

本书中使用了许多文本约定。

CodeInText：表示文本中的代码词、数据库表名、文件夹名、文件名、文件扩展名、路径名、虚拟 URL、用户输入和 Twitter 用户名。这是一个例子：“我们实例化CountVectorizer类，并将training_data.data传递给count_vect对象的fit_transform方法。”

代码块设置如下：

class Node: 
    def __init__(self, data=None): 
        self.data = data 
        self.next = None

当我们希望引起您对代码块的特定部分的注意时，相关行或项目将以粗体显示：

def dequeue(self):  
    if not self.outbound_stack: 
        while self.inbound_stack: 
            self.outbound_stack.append(self.inbound_stack.pop()) 
    return self.outbound_stack.pop()

任何命令行输入或输出都以以下形式书写：

0     1      2
0   4.0  45.0  984.0
1   0.1   0.1    5.0
2  94.0  23.0   55.0

粗体：表示一个新术语、一个重要词或屏幕上看到的词。

警告或重要提示会以这种形式出现。提示和技巧会以这种形式出现。

第一章：Python 对象、类型和表达式

数据结构和算法是一个大型复杂软件项目的核心要素之一。它们是一种系统化的方式，用于在软件中存储和组织数据，以便能够高效地使用。Python 具有高效的高级数据结构和有效的面向对象编程语言。Python 是许多高级数据任务的首选语言，原因很充分。它是最容易学习的高级编程语言之一。直观的结构和语义意味着对于那些不是计算机科学家，但可能是生物学家、统计学家或初创公司的负责人来说，Python 是执行各种数据任务的简单方式。它不仅仅是一种脚本语言，而是一种功能齐全的面向对象的编程语言。

在 Python 中，有许多有用的数据结构和算法内置在语言中。此外，由于 Python 是一种基于对象的语言，相对容易创建自定义数据对象。在本书中，我们将研究 Python 的内部库和一些外部库，并学习如何从头开始构建自己的数据对象。

在本章中，我们将讨论以下主题：

• 获得对数据结构和算法的一般工作知识
  
• 理解核心数据类型及其功能
  
• 探索 Python 编程语言的面向对象的方面
  

技术要求

本书使用 Python 编程语言（版本 3.7）介绍数据结构和算法。本书假设您已经了解 Python。但是，如果您有点生疏，来自其他语言，或者根本不了解 Python，不用担心 - 这一章应该能让您迅速掌握。

以下是 GitHub 链接：github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter01。

如果您对 Python 不熟悉，请访问docs.python.org/3/tutorial/index.html，您也可以在www.python.org/doc/找到文档。这些都是很好的资源，可以轻松学习这种编程语言。

安装 Python

要安装 Python，我们使用以下方法。

Python 是一种解释性语言，语句是逐行执行的。程序员通常可以将一系列命令写在源代码文件中。对于 Python，源代码存储在一个带有.py文件扩展名的文件中。

Python 通常已经完全集成并安装在大多数 Linux 和 Mac 操作系统上。通常，预安装的 Python 版本是 2.7。您可以使用以下命令检查系统上安装的版本：

>>> import sys
>>> print(sys.version)
3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:06:47) [MSC v.1914 32 bit (Intel)]

您还可以使用以下命令在 Linux 上安装不同版本的 Python：

1. 打开终端
   
2. sudo apt-get update
   
3. sudo apt-get install -y python3-pip
   
4. pip3 install
   

Python 必须安装在 Windows 操作系统的系统上，因为它不像 Linux/macOS 那样预安装。可以从此链接下载 Python 的任何版本：www.python.org/downloads/。您可以下载软件安装程序并运行它 - 选择为所有用户安装，然后单击下一步。您需要指定要安装软件包的位置，然后单击下一步。之后，在自定义 Python 对话框中选择将 Python 添加到环境变量的选项，然后再次单击下一步进行最终安装。安装完成后，您可以通过打开命令提示符并输入以下命令来确认安装：

python -V

最新的稳定 Python 版本是 Python 3.7.0。可以通过在命令行中输入以下内容来执行 Python 程序：

python <sourcecode_filename>.py

理解数据结构和算法

算法和数据结构是计算机中最基本的概念。它们是构建复杂软件的主要构建模块。理解这些基础概念在软件设计中是非常重要的，这涉及以下三个特征：

• 算法如何操作数据结构中包含的信息
  

1. 数据在内存中的排列方式
2. 特定数据结构的性能特征是什么

在这本书中，我们将从几个角度来审视这个话题。首先，我们将从数据结构和算法的角度来看 Python 编程语言的基础知识。其次，重要的是我们要有正确的数学工具。我们需要理解计算机科学的基本概念，为此我们需要数学。通过采取一种启发式的方法，制定一些指导原则意味着，一般来说，我们不需要比高中数学更多的知识来理解这些关键思想的原则。

另一个重要方面是评估。衡量算法的性能需要理解数据规模的增加如何影响数据的操作。当我们处理大型数据集或实时应用程序时，我们的算法和结构尽可能高效是至关重要的。

最后，我们需要一个强大的实验设计策略。能够将现实世界的问题概念化为编程语言的算法和数据结构，需要能够理解问题的重要元素以及将这些元素映射到编程结构的方法。

为了更好地理解算法思维的重要性，让我们考虑一个现实世界的例子。假设我们在一个陌生的市场，我们被要求购买一些物品。我们假设市场是随机布局的，每个供应商销售一个随机子集的物品，其中一些物品可能在我们的清单上。我们的目标是尽量减少每个购买物品的价格，同时最小化在市场上花费的时间。解决这个问题的一种方法是编写以下类似的算法：

1. 供应商是否有我们清单上的物品，且成本低于该物品的预测成本？
   
2. 如果是，购买并从清单中删除；如果不是，继续下一个供应商。
   
3. 如果没有更多的供应商，结束。
   
4. 如果我们必须使用编程语言来实现这个简单的迭代器，我们需要数据结构来定义和存储我们想要购买的物品清单和供应商正在销售的物品清单。我们需要确定最佳的匹配物品的方式，并且我们需要一些逻辑来决定是否购买。
   

关于这个算法，我们可以做出几点观察。首先，由于成本计算是基于预测的，我们不知道真实成本是多少。因此，我们不会购买物品，因为我们低估了物品的成本，导致我们在市场结束时仍有剩余物品。为了处理这种情况，我们需要一种有效的方式来存储数据，以便我们可以有效地回溯到成本最低的供应商。

此外，我们需要了解比较我们购物清单上的物品与每个供应商出售的物品所花费的时间。这很重要，因为随着我们购物清单上物品的数量或每个供应商出售的物品数量的增加，搜索物品需要更多的时间。我们搜索物品的顺序和数据结构的形状可以对搜索所需的时间产生很大的影响。显然，我们希望安排我们的清单以及我们访问每个供应商的顺序，以便最小化搜索时间。

此外，考虑一下当我们将购买条件更改为以最便宜的价格购买，而不仅仅是低于平均预测价格时会发生什么。这会完全改变问题。我们不再是顺序地从一个供应商到另一个供应商，而是需要遍历市场一次，并且有了这个知识，我们可以根据我们想要访问的供应商对我们的购物清单进行排序。

显然，将现实世界的问题转化为编程语言这样的抽象构造涉及许多微妙之处。例如，随着我们在市场上的进展，我们对产品成本的了解会提高，因此我们预测的平均价格变量会变得更加准确，直到在最后一个摊位，我们对市场的了解是完美的。假设任何形式的回溯算法都会产生成本，我们可以看到有理由重新审视整个策略。高价格波动、数据结构的大小和形状，以及回溯的成本等条件都决定了最合适的解决方案。整个讨论清楚地表明了数据结构和算法在构建复杂解决方案中的重要性。

Python 用于数据

Python 具有几种内置的数据结构，包括列表、字典和集合，我们可以用它们来构建定制对象。此外，还有一些内部库，如 collections 和 math 对象，它们允许我们创建更高级的结构，并对这些结构进行计算。最后，还有像 SciPy 包中发现的外部库。这些库允许我们执行一系列高级数据任务，如逻辑和线性回归、可视化和数学计算，比如矩阵和向量的操作。外部库对于开箱即用的解决方案非常有用。然而，我们也必须意识到，与从头开始构建定制对象相比，通常会有性能损失。通过学习如何自己编写这些对象，我们可以将它们针对特定任务，使它们更有效率。这并不排除外部库的作用，我们将在第十二章《设计技术和策略》中讨论这一点。

首先，我们将概述一些关键的语言特性，这些特性使 Python 成为数据编程的绝佳选择。

Python 环境

由于其可读性和灵活性，Python 是全球最受欢迎和广泛使用的编程语言之一。Python 环境的一个特点是其交互式控制台，允许您将 Python 用作桌面可编程计算器，也可以用作编写和测试代码片段的环境。

控制台的读取...评估...打印循环是与更大代码库交互的非常方便的方式，比如运行函数和方法或创建类的实例。这是 Python 相对于编译语言（如 C/C++或 Java）的主要优势之一，后者的编写...编译...测试...重新编译循环与 Python 的读取...评估...打印循环相比，可以大大增加开发时间。能够输入表达式并立即得到响应可以大大加快数据科学任务的速度。

除了官方的 CPython 版本外，还有一些优秀的 Python 发行版。其中最受欢迎的两个可以在以下网址找到：Anaconda（https://www.continuum.io/downloads）和 Canopy（https://www.enthought.com/products/canopy/）。大多数发行版都带有自己的开发环境。Canopy 和 Anaconda 都包括用于科学、机器学习和其他数据应用的库。大多数发行版都带有编辑器。

除了 CPython 版本外，还有许多 Python 控制台的实现。其中最值得注意的是基于网络的计算环境 IPython/Jupyter 平台。

变量和表达式

要通过算法实现解决现实世界的问题，我们首先必须选择变量，然后对这些变量应用操作。变量是附加到对象的标签。变量不是对象，也不是对象的容器；它们只是作为对象的指针或引用。例如，考虑以下代码：

在这里，我们创建了一个指向列表对象的变量a。我们创建另一个变量b，它指向相同的列表对象。当我们向这个列表对象添加一个元素时，这个变化会反映在a和b中。

在 Python 中，变量名在程序执行期间附加到不同的数据类型；不需要首先声明变量的数据类型。每个值都有一个类型（例如字符串或整数）；然而，指向这个值的变量名没有特定的类型。更具体地说，变量指向一个对象，可以根据分配给它们的值的类型而改变它们的类型。考虑以下例子：

在前面的代码示例中，a的类型从int变为float，具体取决于变量中存储的值。

变量作用域

函数内部变量的作用域规则很重要。每当函数执行时，都会创建一个局部环境（命名空间）。这个局部命名空间包含所有由函数分配的变量和参数名。每当调用函数时，Python 解释器首先查找函数本身的局部命名空间——如果找不到匹配项，然后查找全局命名空间。如果名称仍然找不到，那么它会在内置命名空间中搜索。如果还是找不到，解释器会引发NameError异常。考虑以下代码：

a=15;b=25
def my_function():
  global a 
  a=11;b=21
my_function() 
print(a)  #prints 11 
print(b)  #prints 25

在前面的代码中，我们定义了两个global变量。我们需要使用关键字global告诉解释器，在函数内部我们正在引用一个global变量。当我们将这个变量更改为11时，这些更改会反映在全局范围内。然而，我们将b变量设置为21是函数内部的局部变量，对它进行的任何更改都不会反映在全局范围内。当我们运行函数并打印b时，我们看到它保留了它的全局值。

此外，让我们考虑另一个有趣的例子：

>>> a = 10
>>> def my_function():
...     print(a)
>>> my_function ()
10

代码可以正常工作，并输出10，但看看下面的代码：

>>> a = 10 
>>> def my_function():
...     print(a)
...     a= a+1 
>>> my_function()
 UnboundLocalError: local variable 'a' referenced before assignment

前面的代码出错了，因为在作用域内对变量进行赋值会使该变量成为该作用域的局部变量。在前面的例子中，在my_function()中对变量a进行赋值，编译器会将a视为局部变量，这就是为什么之前的print()函数尝试打印一个未初始化的局部变量a，从而导致错误。可以通过声明为global来访问外部作用域变量来解决这个问题：

>>> a = 10
>>> def my_function():
...     global a
...     print(a)
...     a = a+1
>>> my_function()
10

因此，在 Python 中，函数内部引用的变量隐式地是全局的，如果a变量在函数体内的任何地方被赋值，它会被假定为局部变量，除非显式声明为全局变量。

流程控制和迭代

Python 程序由一系列语句组成。解释器按顺序执行每个语句，直到没有更多的语句为止。这对于作为主程序运行的文件以及通过import加载的文件都是如此。所有语句，包括变量赋值、函数定义、类定义和模块导入，都具有相同的地位。没有比其他更高优先级的特殊语句，每个语句都可以放在程序的任何位置。通常，程序中的所有指令/语句都按顺序执行。然而，控制程序执行流的主要方法有两种——条件语句和循环。

if...else和elif语句控制条件执行语句。一般格式是一系列if和elif语句，后跟最终的else语句：

x='one' 
if x==0:
   print('False')
elif  x==1:
   print('True')
else:  print('Something else')
#prints'Something else'

请注意使用==运算符来比较两个值。如果两个值相等，则返回True；否则返回False。还要注意，将x设置为字符串将返回Something else，而不会像在静态类型的语言中那样生成类型错误。动态类型的语言，如 Python，允许对具有不同类型的对象进行灵活赋值。

控制程序流的另一种方法是使用循环。Python 提供了两种构建循环的方式，如while和for循环语句。while循环重复执行语句，直到布尔条件为真。for循环提供了一种通过一系列元素重复执行循环的方法。下面是一个例子：

在这个例子中，while循环执行语句，直到条件x < 3为真。让我们考虑另一个使用for循环的例子：

>>>words = ['cat', 'dog', 'elephant']
>>> for w in words:
...     print(w)
... 
cat
dog
elephant

在这个例子中，for循环执行对列表中所有项目的迭代。

数据类型和对象概述

Python 包含各种内置数据类型。这些包括四种数值类型（int、float、complex、bool）、四种序列类型（str、list、tuple、range）、一种映射类型（dict）和两种集合类型。还可以创建用户定义的对象，如函数或类。我们将在本章中讨论字符串和列表数据类型，下一章中讨论其余的内置类型。

Python 中的所有数据类型都是对象。实际上，在 Python 中几乎所有的东西都是对象，包括模块、类和函数，以及字面量，如字符串和整数。Python 中的每个对象都有一个类型、一个值和一个标识。当我们写greet= "helloworld"时，我们创建了一个字符串对象的实例，其值为"hello world"，标识为greet。对象的标识充当指向对象在内存中位置的指针。对象的类型，也称为对象的类，描述了对象的内部表示，以及它支持的方法和操作。一旦创建了对象的实例，它的标识和类型就不能被改变。

我们可以使用内置函数id()来获取对象的标识。这将返回一个标识整数，在大多数系统上，这将指向其内存位置，尽管您不应该依赖于这一点在您的任何代码中。

此外，有许多比较对象的方法；例如，参见以下内容：

if a==b:    # a and b have the same value
if a is b:    # if a and b are the same object
if type(a) is type(b):   #a and b are the same type

需要区分可变和不可变对象之间的重要区别。可变对象如列表可以改变其值。它们有insert()或append()等方法，可以改变对象的值。不可变对象如字符串不能改变其值，因此当我们运行它们的方法时，它们只是返回一个值，而不是改变底层对象的值。当然，我们可以通过将其分配给一个变量或将其用作函数中的参数来使用这个值。例如，int类是不可变的——一旦创建了它的实例，它的值就不能改变，但是，引用这个对象的标识符可以被重新分配另一个值。

字符串

字符串是不可变的序列对象，每个字符代表序列中的一个元素。与所有对象一样，我们使用方法来执行操作。字符串是不可变的，不会改变实例；每个方法只是返回一个值。这个值可以存储为另一个变量，或作为参数传递给函数或方法。

以下表格列出了一些最常用的字符串方法及其描述：

像所有序列类型一样，字符串支持索引和切片。我们可以通过使用索引s[i]检索字符串的任何字符。我们可以通过使用s[i:j]检索字符串的一个切片，其中i和j是切片的起点和终点。我们可以通过使用步长返回一个扩展的切片，如下所示—s[i:j:stride]。以下代码应该能说明这一点：

前两个例子非常直接，分别返回索引1处的字符和字符串的前七个字符。请注意，索引从0开始。在第三个例子中，我们使用了步长为2。这导致每隔一个字符被返回。在最后一个例子中，我们省略了结束索引，切片返回整个字符串中每隔一个字符。

只要值是整数，就可以使用任何表达式、变量或运算符作为索引：

另一个常见的操作是使用循环遍历字符串：

鉴于字符串是不可变的，一个常见的问题是如何执行插入值等操作。我们需要想办法为我们需要的结果构建新的字符串对象，而不是改变一个字符串。例如，如果我们想要在问候语中插入一个单词，我们可以将一个变量赋值给以下内容：

正如这段代码所示，我们使用切片操作符在索引位置5处拆分字符串，并使用+进行连接。Python 从不将字符串的内容解释为数字。如果我们需要对字符串执行数学运算，我们需要先将它们转换为数字类型：

列表

列表是最常用的内置数据结构之一，因为它们可以存储任意数量的不同数据类型。它们是对象的简单表示，并且由整数索引，从零开始，如我们在字符串中看到的那样。

下表包含了最常用的列表方法及其描述：

在 Python 中，与其他语言相比，列表的实现是不同的。Python 不会创建变量的多个副本。例如，当我们将一个变量的值分配给另一个变量时，两个变量都指向存储值的相同内存地址。只有在变量改变其值时才会分配一个副本。这个特性使得 Python 在内存上更有效，因为它只在需要时才创建多个副本。

这对于可变的复合对象（如列表）有重要的影响。考虑以下代码：

在上述代码中，list1和list2变量都指向同一内存位置。但是，当我们通过list2将y更改为4时，实际上也更改了list1指向的相同y变量。

list的一个重要特性是它可以包含嵌套结构；也就是说，列表可以包含其他列表。例如，在以下代码中，列表items包含了另外三个列表：

我们可以使用方括号运算符访问列表的值，并且由于列表是可变的，它们是就地复制的。以下示例演示了我们如何使用这一点来更新元素；例如，在这里我们将面粉的价格提高了 20%：

我们可以使用非常常见和直观的方法，即列表推导，从表达式中创建一个列表。它允许我们通过一个表达式直接创建一个列表。考虑以下示例，使用这个表达式创建了一个列表l：

列表推导可以非常灵活；例如，考虑以下代码。它基本上展示了执行函数组合的两种不同方式，其中我们将一个函数（x*4）应用于另一个函数（x*2）。以下代码打印出了两个列表，分别表示f1和f2的函数组合，首先使用 for 循环计算，然后使用列表推导计算：

def f1(x): return x*2 
def f2(x): return x*4
lst=[]
for i in range(16):
   lst.append(f1(f2(i)))
print(lst)
print([f1(x) for x in range(64) if x in [f2(j) for j in range(16)]])

输出的第一行是来自于 for 循环结构。第二行是来自于列表推导表达式：

列表推导也可以用来复制嵌套循环的操作，以更紧凑的形式。例如，我们将list1中的每个元素与彼此相乘：

我们还可以使用列表推导与其他对象（如字符串）一起构建更复杂的结构。例如，以下代码创建了一个单词及其字母计数的列表：

正如我们将看到的，列表构成了我们将要研究的许多数据结构的基础。它们的多功能性、易于创建和使用使它们能够构建更专业化和复杂的数据结构。

函数作为一等对象

在 Python 中，不仅数据类型被视为对象。函数和类都被称为一等对象，允许它们以与内置数据类型相同的方式进行操作。根据定义，一等对象具有以下特点：

• 在运行时创建
  
• 分配为变量或数据结构中
  
• 作为函数的参数传递
  
• 作为函数结果返回
  

在 Python 中，术语一等对象有点不准确，因为它暗示了某种层次结构，而所有 Python 对象本质上都是一等对象。

为了看看这是如何工作的，让我们定义一个简单的函数：

def greeting(language): 
   if language=='eng': 
        return 'hello world'
      if language =='fr'
        return 'Bonjour le monde'
      else: return  'language not supported'

由于用户定义的函数是对象，我们可以将它们包含在其他对象中，比如列表中：

函数也可以作为其他函数的参数使用。例如，我们可以定义以下函数：

在这里，callf()接受一个函数作为参数，将语言变量设置为'eng'，然后调用带有语言变量作为参数的函数。我们可以看到，如果我们想要生成一个以各种语言返回特定句子的程序，这将是有用的。在这里，我们有一个设置语言的中心位置。除了我们的问候函数，我们还可以创建返回不同句子的类似函数。通过在一个地方设置语言，程序逻辑的其余部分不必担心这一点。如果我们想要改变语言，我们只需改变语言变量，其他一切都可以保持不变。

高阶函数

接受其他函数作为参数或返回函数的函数称为高阶函数。Python 3 包含两个内置的高阶函数——filter()和map()。请注意，在 Python 的早期版本中，这些函数返回列表；在 Python 3 中，它们返回一个迭代器，使它们更加高效。map()函数提供了一种简单的方法来将每个项目转换为可迭代对象。例如，这是一种在序列上执行操作的高效、紧凑的方法。请注意使用lambda匿名函数：

同样，我们可以使用内置的 filter 函数来过滤列表中的项目：

请注意，map 和 filter 执行与列表推导可以实现的相同功能。除了在使用内置函数 map 和 filter 时，与列表推导相比，性能特性没有太大的区别，除了在不使用lambda运算符时稍微有一点性能优势。尽管如此，大多数风格指南建议使用列表推导而不是内置函数，可能是因为它们更容易阅读。

创建我们自己的高阶函数是函数式编程风格的一个标志。高阶函数的一个实际例子是以下演示的。在这里，我们将len函数作为 sort 函数的键传递。这样，我们可以按长度对单词列表进行排序：

这是另一个不区分大小写的排序示例：

请注意list.sort()方法和内置的 sorted 函数之间的区别。list.sort()方法是列表对象的一个方法，它对现有的列表实例进行排序而不复制它。这种方法改变了目标对象并返回None。在 Python 中，一个重要的约定是改变对象的函数或方法返回None，以明确表示没有创建新对象并且对象本身已经改变。

另一方面，内置的 sorted 函数返回一个新的列表。它实际上接受任何可迭代对象作为参数，但它总是返回一个列表。list sort和sorted都接受两个可选的关键字参数。

对更复杂的结构进行排序的一个简单方法是使用 lambda 运算符来使用元素的索引进行排序，例如：

在这里，我们按价格对项目进行了排序。

Python 数据结构和算法实用指南（一）（2）https://developer.aliyun.com/article/1507523