Python中的树你知道吗

树与二叉树

在了解二叉树之前，我们要先了解树的一些概念，方便我们对二叉树的理解。

什么是树？

树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。

它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

每个节点有零个或多个子节点;

没有父节点的节点称为根节点;

每一个非根节点有且只有一个父节点;

除了根节点外,每个子节点可以分为多个不相交的子树;

树的术语：

节点的度: 一个节点含有的子树的个数称为该节点的度;

树的度: 一棵树中,最大的节点的度称为树的度;

根结点： 树的最顶端的节点，继续往下分为子节点

父节点： 子节点的上一层为父节点

兄弟节点： 具有同一个父节点的节点称为兄弟节点

叶子节点/终端节点： 不再有子节点的节点为叶子节点

二叉树：

二叉树是树的特殊一种，具有如下特点：

每个节点最多有两个子树，节点的度最大为2

左子树和右子树是有顺序的，次序不能颠倒

即是某节点只有一个子树，也要区分左右子树

二叉树的性质：

在非空二叉树的第i层，最多有2i-1个节点(i>=1)

在深度为K的二叉树上最多有2k-1个节点(k>1)

对于任意一个非空的二叉树，如果叶子节点个数为n0，度数为2的节点数为n2，则有n0=n2+1

推倒过程：在一棵二叉树中，除了叶子节点（度为0）外，就剩下度为2(n2)和度为1(n1)的节点了。则树的节点总数为T = n0 + n1 + n2；在二叉树中节点总数为T，而连线总数为T-1 = 2n2 + n1，所以就有：n0 + n1 + n2 - 1 = 2 n2 + n1，得到n0=n2+1。

特殊的二叉树

满二叉树

在二叉树中除了叶子节点，其他所有节点的度为2，且所有的叶子节点都在同一层上，这样的二叉树成为满二叉树。

满二叉树的特点：

叶子节点只能出现在最下一层

非叶子节点度数一定为2

在同样深度的二叉树中，满二叉树的节点个数最多，叶子节点数最多

完全二叉树

如果二叉树中除去最后一层叶子节点后为满二叉树，且最后一层的叶子节点依次从左到右分布，则这样的二叉树称为完全二叉树

完全二叉树的特点：

叶子节点一般出现在最下一层，如果倒数第二层出现叶子节点，一定出现在右部连续位置

最下层叶子节点一定集中在左部连续位置

同样节点的二叉树，完全二叉树的深度最小（满二叉树也对）

小例题：

某完全二叉树共有200个节点，该二叉树中共有（）个叶子节点？

解：n0 + n1 + n2 = 200， 其中n0 = n2 + 1，n1 = 0或者1 （n1=1，出现在最下一层节点数为奇数，最下一层节点数为偶数，则n1=0）， 因为n0为整数，所以最后算得n0 = 100。

完全二叉树的性质：

具有n个节点的完全二叉树的深度为log2n+1。log2n结果取整数部分。

如果有一棵有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i(1 <= i <= n)

1 如果i=1，则节点是二叉树的根，无父节点，如果i>1,则其父节点为i/2，向下取整

2 如果21>n，那么节点i没有左孩子，否则其左孩子为2i

3 如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1

验证：

第一条：

当i=1时，为根节点。当i>1时，比如结点为7，他的双亲就是7/2= 3；结点9双亲为4

第二条：

结点6,62 = 12>10，所以结点6无左孩子，是叶子结点。结点5，52 = 10，左孩子是10,结点4，为8

第三条：

结点5，25+1>10,没有右孩子，结点4，则有右孩子。

更多Python相关知识，请移步Python视频教程继续学习！！

在进行网页抓取的时候，分析定位html节点是获取抓取信息的关键，目前我用的是lxml模块(用来分析XML文档结构的，当然也能分析html结构)， 利用其lxmlhtml的xpath对html进行分析，获取抓取信息;以下是关于xpath的一些基本用法:

在介绍XPath的匹配规则之前，我们先来看一些有关XPath的基本概念。首先要说的是XPath数据类型。XPath可分为四种数据类型：

节点集（node-set）

节点集是通过路径匹配返回的符合条件的一组节点的集合。其它类型的数据不能转换为节点集。

布尔值(boolean)

由函数或布尔表达式返回的条件匹配值，与一般语言中的布尔值相同，有true和false两个值。布尔值可以和数值类型、字符串类型相互转换。

字符串(string)

字符串即包含一系列字符的集合，XPath中提供了一系列的字符串函数。字符串可与数值类型、布尔值类型的数据相互转换。

数值(number)

在XPath中数值为浮点数，可以是双精度64位浮点数。另外包括一些数值的特殊描述，如非数值NaN（Not-a-Number）、正无穷大 infinity、负无穷大-infinity、正负0等等。number的整数值可以通过函数取得，另外，数值也可以和布尔类型、字符串类型相互转换。

其中后三种数据类型与其它编程语言中相应的数据类型差不多，只是第一种数据类型是XML文档树的特有产物。另外，由于XPath包含的是对文档结构树的一系列 *** 作，因此搞清楚XPath节点类型也是很必要的。由于XML文档的逻辑结构，一个XML文件可以包含元素、CDATA、注释、处理指令等逻辑要素，其中元素还可以包含属性，并可以利用属性来定义命名空间。相应地，在XPath中，将节点划分为七种节点类型：

根节点（Root Node）

根节点是一棵树的最上层，根节点是唯一的。树上其它所有元素节点都是它的子节点或后代节点。对根节点的处理机制与其它节点相同。在XSLT中对树的匹配总是先从根节点开始。

元素节点（Element Nodes）

元素节点对应于文档中的每一个元素，一个元素节点的子节点可以是元素节点、注释节点、处理指令节点和文本节点。可以为元素节点定义一个唯一的标识id。

元素节点都可以有扩展名，它是由两部分组成的：一部分是命名空间URI，另一部分是本地的命名。

文本节点（Text Nodes）

文本节点包含了一组字符数据，即CDATA中包含的字符。任何一个文本节点都不会有紧邻的兄弟文本节点，而且文本节点没有扩展名。

属性节点（Attribute Nodes）

每一个元素节点有一个相关联的属性节点集合，元素是每个属性节点的父节点，但属性节点却不是其父元素的子节点。这就是说，通过查找元素的子节点可以匹配出元素的属性节点，但反过来不成立，只是单向的。再有，元素的属性节点没有共享性，也就是说不同的元素节点不共有同一个属性节点。

对缺省属性的处理等同于定义了的属性。如果一个属性是在DTD声明的，但声明为#IMPLIED，而该属性没有在元素中定义，则该元素的属性节点集中不包含该属性。

此外，与属性相对应的属性节点都没有命名空间的声明。命名空间属性对应着另一种类型的节点。

命名空间节点（Namespace Nodes）

每一个元素节点都有一个相关的命名空间节点集。在XML文档中，命名空间是通过保留属性声明的，因此，在XPath中，该类节点与属性节点极为相似，它们与父元素之间的关系是单向的，并且不具有共享性。

处理指令节点（Processing Instruction Nodes）

处理指令节点对应于XML文档中的每一条处理指令。它也有扩展名，扩展名的本地命名指向处理对象，而命名空间部分为空。

注释节点（Comment Nodes）

注释节点对应于文档中的注释。下面，我们来构造一棵XML文档树：

<A id=”a1″>

<B id=”b1″>

<C id=”c1″>

<B name=”b”/>

<D id=”d1″/>

<E id=”e1″/>

<E id=”e2″/>

</C>

</B>

<B id=”b2″/>

<C id=”c2″>

<B/>

<D id=”d2″/>

<F/>

</C>

<E/>

</A>

现在，来实现一些利用Xpath使XML中节点匹配的基本方法。

路径匹配

路径匹配与文件路径的表示相仿，比较好理解。有以下几个符号：

符 号

含 义

举 例

匹配结果

/

指示节点路径

/A/C/D

节点”A”的子节点”C”的子节点”D”，即id值为d2的D节点

/

根节点

//

所有路径以”//”后指定的子路径结尾的元素

//E

所有E元素，结果是所有三个E元素

//C/E

所有父节点为C的E元素，结果是id值为e1和e2的两个E元素

路径的通配符

/A/B/C/

A元素→B元素→C元素下的所有子元素，即name值为b的B元素、id值为d1的D元素和id值为e1和e2的两个E元素

///D

上面有两级节点的D元素，匹配结果是id值为d2的D元素

//

所有的元素

|

逻辑或

//B | //C

所有B元素和C元素

位置匹配

对于每一个元素，它的各个子元素是有序的。如：

举 例

含 义

匹配结果

/A/B/C[1]

A元素→B元素→C元素的第一个子元素

name值为b的B元素

/A/B/C[last()]

A元素→B元素→C元素的最后一个子元素

id值为e2的E元素

/A/B/C[position()>1]

A元素→B元素→C元素之下的位置号大于1的元素

id值为d1的D元素和两个具有id值的E元素

属性及属性值

在XPath中可以利用属性及属性值来匹配元素，要注意的是，元素的属性名前要有”@”前缀。例如：

举 例

含 义

匹配结果

//B[@id]

所有具有属性id的B元素

id值为b1和b2的两个B元素

//B[@]

所有具有属性的B元素

两个具有id属性的B元素和一个具有name属性B元素

//B[not(@)]

所有不具有属性的B元素

A元素→C元素下的B元素

//B[@id="b1"]

id值为b1的B元素

A元素下的B元素

亲属关系匹配

XML文档可归结为树型结构，因此任何一个节点都不是孤立的。通常我们把节点之间的归属关系归结为一种亲属关系，如父亲、孩子、祖先、后代、兄弟等等。在对元素进行匹配时，同样可以用到这些概念。例如：

举 例

含 义

匹配结果

//E/parent::

所有E节点的父节点元素

id值为a1的A元素和id值为c1的C元素

//F/ancestor::

所有F元素的祖先节点元素

id值为a1的A元素和id值为c2的C元素

/A/child::

A的子元素

id值为b1、b2的B元素，id值为c2的C元素，以及没有任何属性的E元素

/A/descendant::

A的所有后代元素

除A元素以外的所有其它元素

//F/self::

所有F的自身元素

F元素本身

//F/ancestor-or-self::

所有F元素及它的祖先节点元素

F元素、F元素的父节点C元素和A元素

/A/C/descendant-or-self::

所有A元素→C元素及它们的后代元素

id值为c2的C元素、该元素的子元素B、D、F元素

/A/C/following-sibling::

A元素→C元素的紧邻的后序所有兄弟节点元素

没有任何属性的E元素

/A/C/preceding-sibling::

A元素→C元素的紧邻的前面所有兄弟节点元素

id值为b1和b2的两个B元素

/A/B/C/following::

A元素→B元素→C元素的后序的所有元素

id为b2的B元素、无属性的C元素、无属性的B元素、id为d2的D元素、无属性的F元素、无属性的E元素。

/A/C/preceding::

A元素→C元素的前面的所有元素

id为b2的B元素、id为e2的E元素、id为e1的E元素、id为d1的D元素、name为b的B元素、id为c1的C元素、id为b1的B元素

条件匹配

条件匹配就是利用一些函数的运算结果的布尔值来匹配符合条件的节点。常用于条件匹配的函数有四大类：节点函数、字符串函数、数值函数、布尔函数。例如前面提到的last()、position()等等。这些功能函数可以帮助我们精确寻找需要的节点。

函数功能及作用 ：

count()功能 : 统计计数，返回符合条件的节点的个数

number()功能 : 将属性的值中的文本转换为数值

substring() 功能

语法：substring(value, start, length)

截取字符串

sum()功能 : 求和

这些功能只是XPath语法中的一部分，还有大量的功能函数没有介绍，而且目前XPath的语法仍然在不断发展中。通过这些函数我们可以实现更加复杂的查询和 *** 作。

以上这些匹配方法中，用得最多的还要数路径匹配。依靠给出相对于当前路径的子路径来定位节点的。

了解xpath了，现在就可以分析html了,代码举例：

view source

print

1

import

lxmlhtml

2

html

=

'''

数量: 1

''' doc = lxmlhtmlfromstring(html) numList = docxpath('//td[@style="padding-bottom: 5px;" and @nowrap="" and not(@align="right")]/text()')

xpath的语法中'/'和'//'的区别

/是在它的子结点中查找，而//是在它的所有子结点中查找，包括子结点的子结点等等

比如：

<root>

<lev1>

<lev2>lev2_1</lev2>

</lev1>

<lev2>

lev2_2

</lev2>

</root>

那么如果用lev1/lev2只能得到文本是lev2_2的这个结点，而如果用lev1//lev2，则两个lev2结点都能得到

python有三种方法解析XML，SAX，DOM，以及ElementTree

###1SAX (simple API for XML )

pyhton 标准库包含SAX解析器，SAX是一种典型的极为快速的工具，在解析XML时，不会占用大量内存。

但是这是基于回调机制的，因此在某些数据中，它会调用某些方法进行传递。这意味着必须为数据指定句柄，

以维持自己的状态，这是非常困难的。

###2DOM(Document Object Model)

与SAX比较，DOM典型的缺点是比较慢，消耗更多的内存，因为DOM会将整个XML数读入内存中，并为树

中的第一个节点建立一个对象。使用DOM的好处是你不需要对状态进行追踪，因为每一个节点都知道谁是它的

父节点，谁是子节点。但是DOM用起来有些麻烦。

###3ElementTree(元素树)

ElementTree就像一个轻量级的DOM，具有方便友好的API。代码可用性好，速度快，消耗内存少，这里主要

介绍ElementTree。

具体参看文档，有例子，照着例子做就行了

BeautifulSoup 官方文档 介绍：BeautifulSoup 是一个可以从HTML或XML文件中提取数据的Python库。使用BeautifulSoup更多方便，避免使用正则表达式容易出错，提高效率。

BeautifulSoup支持Python标准库中的HTML解析器,还支持一些第三方的解析器,其中一个是 lxml。以下为BeautifulSoup官方文档对支持的解析器优缺点对比。

推荐使用lxml解释器，效率更高。 注意：不同的解析器返回不同的结果

通过解析器，BeautifulSoup可以传入一段字符串或文件。

Beautiful Soup将复杂HTML文档转换成一个复杂的树形结构,每个节点都是Python对象,所有对象可以归纳为4种: Tag , NavigableString , BeautifulSoup , Comment 。接下来使用以下文档进行说明。

可以看到a点只是返回第一个，如果需要历遍全部则需要用find_all('a')。

tag有多种属性，其中两个最重要的就是name和attributes。name一般返回标签本身（soup返回document）， 注意，tag属性 *** 作方法和字典一样。

上面说到节点选择可以直接利用标签，如<head>标签用souphead，也可通过name和attrs可以直接获取属性， *** 作和字典一样。以上是直接获取的方式，当想要获取标签的子节点、父节点、兄弟节点则需要通过另外的方法。

children 是一个llist生成器，可以对子节点进行历遍循环

descendants 是返回所有子孙节点，比较children和descendants的输出区别

lxml takes all the pain out of XML

Stephan Richter

lxml是Python语言里和XML以及HTML工作的功能最丰富和最容易使用的库。lxml是为libxml2和libxslt库的一个Python化的绑定。它与众不同的地方是它兼顾了这些库的速度和功能完整性，以及纯Python API的简洁性，大部分与熟知的ElementTree API兼容但比之更优越。

安装lxml：

要求：需要Python23或更后的版本

使用easy_install工具，以超级用户或管理员的角色run下面的命令：

easy_install lxml

在windows下，最好指定版本号：easy_install lxml==226

使用lxml进行开发

lxmletree指南

通常使用lxmletree的方式

>>> from lxml import etree

Element类，一个Element是ElementTree API的主要容器类，大部分的XML tree功能都是通过这个类来访问的。Elements可以非常容易地通过Element工厂方法来创建。

>>> root = etreeElement("root")

元素的XML tag名字是通过tag属性来访问的

>>> print roottag # root

Elements是在XML树状结构中组织的，为创建子元素并将它们加到父元素上，可以使用append()方法。

>>> rootappend( etreeElement("child1") )

我们还有更高效的方法：SubElement工厂方法，它使用和Element工厂方法相同的参数，不过额外需要父节点作第一个参数：

>>> child2 = etreeSubElement(root, "child2")

>>> child3 = etreeSubElement(root, "child3")

可以使用tostring()方法来看得到的XML

>>> print etreetostring(root, pretty_print=True)

<root>

<child1/>

<child2/>

<child3/>

</root>

元素是列表

>>> child = root[0]

>>> print childtag

child1

>>> print len(root)

3

>>> rootindex(root[1]) # lxmletree only!

1

打印所有子节点：

>>> children = list(root)

>>> for child in root:

print(childtag)

child1

child2

child3

可以使用insert()方法插入新的子节点：

>>> rootinsert(0, etreeElement("child0"))

删除子节点：

>>> root[0] = root[-1] # this moves the element!

>>> for child in root:

print(childtag)

child3

child1

child2

如果想把一个元素拷贝到不同的地方，需要创建一个独立的deep copy。

>>> from copy import deepcopy

>>> element = etreeElement("neu")

>>> elementappend( deepcopy(root[1]) )

>>> print(element[0]tag)

child1

>>> print([ ctag for c in root ])

[’child3’, ’child1’, ’child2’]

getparent()返回父节点:

>>> root is root[0]getparent() # lxmletree only!

True

元素的兄弟或邻居节点是通过next和previous属性来访问的

The siblings (or neighbours) of an element are accessed as next and previous elements:

>>> root[0] is root[1]getprevious() # lxmletree only!

True

>>> root[1] is root[0]getnext() # lxmletree only!

True

带属性的元素

XML元素支持属性，可以用Element工厂方法直接创建。

>>> root = etreeElement("root", interesting="totally")

>>> etreetostring(root)

b’<root interesting="totally"/>’

可以使用set和get方法访问这些属性：

>>> print rootget("interesting")

totally

>>> rootset("interesting", "somewhat")

>>> print rootget("interesting")

somewhat

也可以使用attrib性质的字典接口

>>> attributes = rootattrib

>>> print(attributes["interesting"])

somewhat

>>> print(attributesget("hello"))

None

>>> attributes["hello"] = "Guten Tag"

>>> print(attributesget("hello"))

Guten Tag

>>> print(rootget("hello"))

Guten Tag

元素可以包含文字：

>>> root = etreeElement("root")

>>> roottext = "TEXT"

>>> print(roottext)

TEXT

>>> etreetostring(root)

’<root>TEXT</root>’

如果XML用在(X)HTML中，文本也可以在不同的元素中显示:

<html><body>Hello<br/>World</body></html>

元素有tail属性，它包含XML 树中元素直接跟的，直到下个元素的文本。

>>> html = etreeElement("html")

>>> body = etreeSubElement(html, "body")

>>> bodytext = "TEXT"

>>> etreetostring(html)

b’<html><body>TEXT</body></html>’

>>> br = etreeSubElement(body, "br")

>>> etreetostring(html)

b’<html><body>TEXT<br/></body></html>’

>>> brtail = "TAIL"

>>> etreetostring(html)

b’<html><body>TEXT<br/>TAIL</body></html>’

该模块提供了堆排序算法的实现。堆是二叉树，最大堆中父节点大于或等于两个子节点，最小堆父节点小于或等于两个子节点。

heapq有两种方式创建堆， 一种是使用一个空列表，然后使用heapqheappush()函数把值加入堆中，另外一种就是使用heapheapify(list)转换列表成为堆结构

heapq 模块还有一个 heapqmerge(iterables) 方法，用于合并多个排序后的序列成一个排序后的序列， 返回排序后的值的迭代器。

类似于 sorted(itertoolschain(iterables)) ，但返回的是可迭代的。

堆创建好后，可以通过`heapqheappop() 函数d出堆中最小值。

如果需要删除堆中最小元素并加入一个元素，可以使用 heapqheaprepalce() 函数

如果需要获取堆中最大或最小的范围值，则可以使用 heapqnlargest() 或 heapqnsmallest() 函数

这两个函数还接受一个key参数，用于dict或其他数据结构类型使用

实现heap堆排序算法

该算法和 sorted(iterable) 类似，但是它是不稳定的。

堆的值可以是元组类型，可以实现对带权值的元素进行排序。

Python3标准库文档

Python堆排序

使用时先安装 lxml 包

开始使用 #

和beautifulsoup类似，首先我们需要得到一个文档树

把文本转换成一个文档树对象

from lxml import etreeif __name__ == '__main__':doc='''

把文件转换成一个文档树对象

fromlxmlimportetree# 读取外部文件 indexhtmlhtml = etreeparse('/indexhtml')result = etreetostring(html, pretty_print=True)#pretty_print=True 会格式化输出print(result)

均会打印出文档内容

节点、元素、属性、内容 #

xpath 的思想是通过 路径表达 去寻找节点。节点包括元素，属性，和内容

元素举例

html --->div --->

这里我们可以看到，这里的元素和html中的标签一个意思。单独的元素是无法表达一个路径的，所以单独的元素不能独立使用

路径表达式 #

/  根节点，节点分隔符，//  任意位置  当前节点  父级节点@  属性

通配符 #

  任意元素@  任意属性node()  任意子节点（元素，属性，内容)

谓语 #

使用中括号来限定元素，称为谓语

//a[n] n为大于零的整数，代表子元素排在第n个位置的 元素//a[last()]  last()  代表子元素排在最后个位置的 元素//a[last()-]  和上面同理，代表倒数第二个//a[position()<3] 位置序号小于3，也就是前两个，这里我们可以看出xpath中的序列是从1开始//a[@href]    拥有href的 元素//a[@href='内置很多函数。更多函数查看 >

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

点击以下查看大图：

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模 k："桶"的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

包含以下内容：

1、冒泡排序 2、选择排序 3、插入排序 4、希尔排序 5、归并排序 6、快速排序 7、堆排序 8、计数排序 9、桶排序 10、基数排序

排序算法包含的相关内容具体如下：

冒泡排序算法

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

选择排序算法

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

插入排序算法

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

希尔排序算法

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

归并排序算法

归并排序（Merge sort）是建立在归并 *** 作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

计数排序算法

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

桶排序算法

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

基数排序算法

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

以上就是关于Python中的树你知道吗全部的内容，包括:Python中的树你知道吗、python xpath怎么用、python解析xml等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！