本文主要研究Python常用的算法，Python常用的排序算法。本文中的示例代码非常详细，具有一定的参考价值。感兴趣的朋友可以参考一个。

本文分享Python常用算法的具体代码，供大家参考。具体内容如下

1.算法定义

算法是指对解题方案准确完整的描述，是一系列解决问题的明确指令。算法代表了一种描述解决问题的策略机制的系统方法。也就是说，对于某一标准输入，可以在有限的时间内获得所需的输出。如果一个算法有缺陷或者不适合某个问题，执行这个算法并不能解决问题。不同的算法可能使用不同的时间、空间或效率来完成相同的任务。算法的好坏可以用空间复杂度和时间复杂度来衡量。

一个算法应该具有以下七个重要特征：

有限性：算法的有限性是指算法必须能够在有限步数后终止；

准确性：算法的每一步都要有确切的定义；

输入：一个算法有0个或多个输入，用来描述运算对象的初始情况。所谓0输入，是指算法本身已经设定了初始条件；

输出：一个算法有一个或多个输出，反映输入数据的处理结果。没有输出的算法是没有意义的；

有效性：算法中进行的任何计算步骤都可以分解成基本的可执行操作步骤，即每个计算步骤都可以在有限的时间内完成(也叫有效性)；

高效：执行速度快，资源占用少；

稳健性：对数据反应正确。

2. 时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量地描述了算法的运行时间。大O符号是一个数学符号，用于描述函数的渐进行为。更具体地说，它使用另一个(通常更简单的)函数来描述一个函数的数量级的渐近上界。在数学上，一般用来描述截断无穷级数的余项，尤其是渐近级数；在计算机科学中，它在分析算法的复杂性方面非常有用。)，这样时间复杂度可以说是渐近的，考察的是输入值趋近于无穷大时的情况。

大O，简而言之可以认为它的含义是“order of”（大约是）。

渐近线的

o符号在分析算法效率时非常有用。例如，求解一个规模为N的问题所需的时间(或所需的步骤数)可以求出：t (n)=4N2-2N2。

当n增加时，n ^ 2；项将开始占主导地位，而其他项可以忽略不计。3354例如：当n=500时，4n^2；是2n项的1000倍，所以在大多数情况下，省略后者对表达式值的影响将可以忽略不计。

数学素养粘贴python算法表示概念素养课程

一、计算方法

1.一个算法执行的时间理论上是无法计算的，必须在电脑上运行测试才能知道。但是我们不能也不需要在电脑上测试每一个算法。我们只需要知道哪个算法花的时间多，哪个算法花的时间少。而且一个算法花费的时间和算法中语句的执行次数成正比，在哪个算法中执行的语句越多，花费的时间就越多。

一个算法中执行的语句数量称为语句频率或时间频率。写为T(n)。

2.一般算法基本运算重复的次数是模n的某个函数f(n)，因此算法的时间复杂度记为：T(n)=O(f(n))。随着模数n的增加，算法执行时间的增长率与f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。

计算时间复杂度时，先找出算法的基本运算，然后根据相应的语句确定其执行次数，再找出T(n)的同一个数量级(其同一个数量级如下：1，Log2n，n，nLog2n，n的平方，n的三次方，2的n次方，n！)，查了一下，f(n)=这个数量级。如果T(n)/f(n)的极限可以得到一个常数C，那么时间复杂度T(n)=O(f(n))。

3.公共时间复杂度

按照数量级，常见的时间复杂性有：

常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶o (n 2)，三次阶o (n 3)，k阶o (n k)，指数阶o (2 n)。

其中，

1.O(n)，o(n ^ 2)，三次o(n ^ 3)，k阶o (n k)为多项式时间复杂度，分别称为一阶时间复杂度和二阶时间复杂度。

2.O (2 n)，指数时间复杂度，不实用。

3.除常数阶外，对数阶O(log2n)和线性对数阶O(nlog2n)的效率最高。

示例：算法：

for(I=1；I=n；我)

{

for(j=1；j=n；j)

{

c[I][j]=0；//这一步属于基本操作执行次数：n 2

for(k=1；k=n；k)

c[I][j]=a[I][k]* b[k][j]；//这一步属于基本操作执行次数：n ^ 3

}

}

然后就是T(n)=n ^ 2n ^ 3。根据上面括号中的同一个数量级，我们可以确定n 3与t (n)同一个数量级

那么f(n)=n ^ 3，然后根据T(n)/f(n)求极限就可以得到常数c

那么算法的时间复杂度：T(n)=O(n ^ 3)

四、定义：如果一个问题的规模是n，那么一个算法求解这个问题所需的时间是T(n)，它是n的函数，T(n)称为这个算法的“时间复杂度”。

当输入量N逐渐增加时，时间复杂度的极限情况称为算法的“渐近时间复杂度”。

我们经常用大O符号来表示时间复杂度。注意是算法的时间复杂度。o表示有一个上界。根据定义，如果f(n)=O(n)，显然就成立f(n)=O(n ^ 2)。它给了你一个上界，但不是上界，只是人们普遍习惯于表达前者。

另外，一个问题本身也有它的复杂性。如果一个算法的复杂度达到了这个问题复杂度的下界，就称为最佳算法。

“大O记法”:该描述中使用的基本参数是n，即问题实例的规模，复杂度或运行时间表示为n的函数，这里“O”表示顺序，例如“二分搜索法为O(logn)”，表示需要“通过logn的步数搜索一个大小为n的数组”。O (f(n))表示当n增加时，运行时间最多以与f(n)成正比的速率增加。

这种渐进的估计对于理论分析和算法的近似比较非常有价值，但细节也可能造成实践中的差异。例如，当n较小时，具有低附加成本的O(n2)算法可能比具有高附加成本的O(nlogn)算法运行得更快。当然，当n足够大时，上升函数较慢的算法会工作得更快。

O(1)

temp=I；I=j；j=温度；

上述三个单语句出现的频率为1，这个程序段的执行时间是一个与问题规模n无关的常数，算法的时间复杂度是一个常数阶，记为T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增加，那么即使算法中有上千条语句，它的执行时间也只是一个很大的常数。该算法的时间复杂度为O(1)。

O(n^2)

2.1. 交换i和j的内容

sum=0；(一次)

for(I=1；I=n；I) (n次)

for(j=1；j=n；j)(n ^ 2次)

总和；(n ^ 2次)

解：T(n)=2n 2 n1=O(n ^ 2)

2.2.

for(I=1；在；我)

{

y=y ^ 1；

for(j=0；j=(2 * n)；j)

x；

}

解：语句1的频率是n-1。

2语句出现的频率为(n-1)*(2 n1)=2n ^ 2-n-1。

f(n)=2n^2-n-1 (n-1)=2n^2-2

程序的时间复杂度T(n)=O(n ^ 2)。

O(n)

2.3.

a=0；

b=1；

for(I=1；I=n；i )

{

s=a b；

b=a；

a=s；

}

解决方案：语句频率1: 2，

2个语句的频率：n，

发言频率：n-1，

4个语句的频率：n-1，

5项陈述的频率：n-1，

T(n)=2 n 3(n-1)=4n-1=O(n)。

O(log2n)

2.4.

I=1；

while (i=n)

I=I * 2；

解决方案：语句1的频率是1，

设语句2的频率为f(n)，则：2f(n)=n；f(n)=log2n

取最大值f(n)=log2n，

T(n)=O(log2n)

O(n^3)

2.5.

for(I=0；在；我)

{

for(j=0；纪；j)

{

for(k=0；kj；k)

x=x ^ 2；

}

}

解法：当i=m，j=k时，内环数为k .当i=m时，J可取0，1，m-1，所以这里最里面的循环已经过了0 1.m-1=(m-1)m/2次。所以，当I从0取n时，循环经过：0(

我们还应该区分最坏情况的行为和算法的预期行为。例如，快速排序的最坏情况运行时间是O(n ^ 2)，但期望时间是O(nlogn)。通过每次仔细选择参考值，有可能将平方情况(即O (n 2)情况)的概率降低到几乎为零。实际上，精心实现的快速排序通常可以在O(nlogn)时间内运行。

下面是一些常用的记法：

访问数组中的元素是一个常数时间操作，或O(1)操作。如果一个算法能在每一步去掉一半的数据元素，比如二分搜索法，通常需要O(logn)时间。用strcmp比较两个n字符的字符串需要O(n)时间。常规的矩阵乘法算法是O(N ^ 3)，因为计算每个元素需要N对元素相乘并相加在一起，所有元素的个数是N ^ 2。

指数时间算法通常来源于寻找所有可能结果的需要。比如n个元素的集合中有2n个子集，那么要求所有子集的算法将是O(2n)。一般来说，指数算法太复杂了，除非n的值很小，因为这个问题增加一个元素，运行时间会增加一倍。可惜问题很多(比如著名的“旅行推销员问题”)，目前找到的算法都是指数级的。如果真的遇到这种情况，通常应该用一个算法来代替，找到近似的最佳结果。

常用排序

冒泡排序（Bubble Sort）

冒泡排序是计算机科学领域中一种简单的排序算法。

它反复访问要排序的序列，一次比较两个元素，如果它们的顺序不对，就切换它们。访问序列的工作一直重复到不需要交换为止，也就是说序列已经排序了。

这种算法的名字来源于较大的元素会通过交换慢慢“浮”到序列的顶端，因此得名。

数据集=[ 9，1，22，31，45，3，6，2，11 ]

loop_count=0

对于范围内的j(len(data _ set)):

对于I in range(len(data _ set)-j-1):#-1是因为我每次和i 1比较，如果不减1，最后一次比较就会超出列表获取的范围。-j是因为每次大循环都意味着一个最大值已经排序并放在了列表的后面，所以下次循环就不用计算排序后的值了。

if数据组[i]数据组[I 1]:#开关

tmp=data_set[i]

数据集[i]=数据集[i 1]

data_set[i 1]=tmp

loop_count=1

打印(数据集)

打印(数据集)

打印(“循环次数”，循环计数)

选择排序

该算法的工作原理是选择最小的未排序项目，然后将其与下一个待填充位置的项目进行交换。

选择排序的工作方式如下：在整个数组中寻找最小的元素，一旦找到，就用数组的第一个元素替换它(最小的元素)。然后在剩下的数组(没有第一个元素的数组)中寻找最小的元素，并与第二个元素交换。然后在剩下的数组(没有第一个和第二个元素的数组)中寻找最小的元素，并与第三个元素交换，依此类推。这里有一个例子，

数据集=[ 9，1，22，31，45，3，6，2，11 ]

minimum _ num _ index=0 #初始列表的最小值，默认为第一个。

loop_count=0

对于范围内的j(len(data _ set)):

对于范围内的I(j，len(data_set)):

if _ set[I]data _ set[small _ num _ index]:#当前值小于之前选择的最小值，所以改成最小值。

最小数量索引=i

loop_count=1

否则：

print('最小数是'，数据集[最小数索引])

tmp=数据集[最小数量索引]

数据集[最小数量索引]=数据集[j]

data_set[j]=tmp

打印(数据集)

打印(“循环次数”，循环计数)

最坏情况下的运行时间复杂度是O(n2)。

插入排序(Insertion Sort)

插入排序的基本思想是：将列表分为两部分，排序的部分在左边，未排序的部分在右边，循环整个列表。每次，将一条要排序的记录插入到之前根据关键字大小排序过的子序列中的适当位置，直到插入所有记录。

插入排序与整张扑克牌非常相似。

当你开始摸牌时，你的左手是空的，牌面朝下放在桌子上。然后，从桌子上一次拿起一张卡片，将它插入左手卡片的正确位置。为了找到这张牌的正确位置，从右到左与你手中现有的牌进行比较。无论何时，左手的牌都是有序的。

也许你没有意识到，但其实你的思维过程是这样的：现在抓一个7，从右到左和你手里的牌对比。7比10小，应该再往左边插。7比5大。好的，就插在这里。为什么可以通过10和5的对比来确定7的位置？为什么不对比一下左边的4和2呢？因为这里有一个重要的前提：手里的牌已经有顺序了。现在我插7后，手里的牌还是按顺序的，下次抓到的牌可以用这种方法插。对数组编程进行插入和排序也是如此，但与插入扑克牌有一点不同。不可能在两个相邻的存储单元之间插入另一个单元，所以插入点之后的数据要依次后移一个单元。

来源=[92，77，67，8，6，84，55，85，43，67]

对于范围内的索引(1，len(source)):

Current_val=source[index] #记下你在每个大循环中去的元素的值。

位置=索引

而position 0和source[position-1]current _ val:#当前元素左边的下一个元素比它大。将左边的元素一个一个向右移动，将当前值插入左边并移出一个位置。

source[position]=source[position-1]#将左边的一个元素移到右边。

Position -=1 #只有一次左移只能将当前元素移动一个位置，你要继续左移，直到这个元素被放到排序列表的合适位置。

Source[position]=current_val #在左边的排序列表中找到了不小于current_val的元素的位置。将current_val放在这里。

打印(来源)

结果：

[77, 92, 67, 8, 6, 84, 55, 85, 43, 67]

[67, 77, 92, 8, 6, 84, 55, 85, 43, 67]

[8, 67, 77, 92, 6, 84, 55, 85, 43, 67]

[6, 8, 67, 77, 92, 84, 55, 85, 43, 67]

[6, 8, 67, 77, 84, 92, 55, 85, 43, 67]

[6, 8, 55, 67, 77, 84, 92, 85, 43, 67]

[6, 8, 55, 67, 77, 84, 85, 92, 43, 67]

[6, 8, 43, 55, 67, 77, 84, 85, 92, 67]

[6, 8, 43, 55, 67, 67, 77, 84, 85, 92]

#更容易理解的版本

data_set=[ 9，1，22，9，31，-5，45，3，6，2，11 ]

对于范围内的I(len(data _ set)):

#position=i

而i0和data _ set [I] data _ set [I-1]: #右边小于左边的相邻值。

tmp=data_set[i]

数据集[i]=数据集[i-1]

data_set[i-1]=tmp

i -=1

# position=i

# while position 0和data _ set[position]data _ set[position-1]:#右侧小于左侧相邻值。

# tmp=数据集合[位置]

#数据集合[位置]=数据集合[位置-1]

# data _ set[位置1]=tmp

#位置-=1

快速排序（quick sort）

设要排序的数组是A [0] … A [n-1]。首先，任意选择一个数据(通常是数组的第一个数)作为关键数据，然后将所有小于它的数放在它的前面，所有大于它的数放在它的后面。这个过程被称为快速排序。值得注意的是，快速排序并不是一种稳定的排序算法，也就是说，多个相同值的相对位置在算法结束时可能会发生变化。

注：在待排序的文件中，如果有多条相同关键字的记录，排序后这些相同关键字的记录之间的相对顺序保持不变，排序方式稳定；如果具有相同关键字的记录之间的相对顺序发生变化，这种排序方法就称为不稳定。

注意，排序算法的稳定性是针对所有输入实例的。即在所有可能的输入实例中，只要有一个实例使算法不满足稳定性要求，排序算法就是不稳定的。

排序演示

例子

假设用户输入以下数组：

创建变量i=0(指向第一个数据)，j=5(指向最后一个数据)，k=6(赋值为第一个数据的值)。

我们要把所有小于k的数都移到k的左边，这样就可以开始寻找小于6的数，从j开始，从右向左看，不断减小变量j的值，我们发现第一个下标3的数据小于6，于是我们把data 3移到下标0的位置，下标0的data 6移到下标3，完成第一次比较：

i=0 j=3 k=6

然后，开始第二次对比，这次要比K大，而且是从前到后。通过添加变量I，发现下标2的数据是大于k的第一个，于是J指向的下标2的7和下标3的6互换，数据状态变成下表：

i=2 j=3 k=6

把以上两个对比称为一个循环。

然后，减少变量j，重复上述循环比较。

在这个例子中，我们做了一个循环，发现I和J“相遇”:它们都指向下标2。所以，第一次对比就结束了。结果如下：k(=6)左边所有的数都比它小，k右边所有的数都比它大：

如果I和J不满足，就加I找大的。如果不是，就减J找小的，以此类推。判断和搜索同时进行。

然后，将K两侧的数据分组，并分别执行上述过程，直到不能再分组为止。

注意：第一次快速排序不会直接得到最终结果，只会把大于k和小于k的数分在k的两边，为了得到最终结果，需要对下标2两边的数组再次执行这一步，然后分解数组，直到数组不能再分解了(只有一个数据)，才能得到正确的结果。

# _ * _编码：utf-8_*_

__作者__='李北岳'

def quick_sort(array，left，right):

'''

:参数数组：

:param left:列表的第一个索引。

:param right:列表中最后一个元素的索引

:返回：

'''

如果左=右：

返回

低=左

高=右

Key=array[low] #第一个值

而低高：#只要不满足左右。

while low high and array[high]key:#直到在列表右侧找到一个大于key的值。

高=1

#此时直接用比它大的array[high]交换key(array[low])。

数组[低]=数组[高]

数组[高]=键

while low high and array[low]=key:#查找key左侧大于key的值。为什么是=而不是？你必须思考。

低=1

#array[low]=

#找到左边大于k的值，用这个大于key的array[low]交换array[high](此时应该刚存为key)。

数组[高]=数组[低]

array[low]=key

Quick_sort(array，left，low-1) #最后，用同样的方法对分割后的左组做同样的操作。

Quick_sort(array，low 1，right)#用同样的方法对分割后的右组做同样的操作。

if __name__=='__main__ ':

array=[96，14，10，9，6，99，16，5，1，3，2，4，1，13，26，18，2，45，34，23，1，7，3，22，19，2]

#array=[8，4，1，14，6，2，3，9，5，13，7，1，8，10，12]

print('排序前：'，数组)

quick_sort(array，0，len(array)-1)

打印('-最终-')

打印(数组)

二叉树

树的特征和定义

树是一种重要的非线性数据结构。直观地说，它是一种根据分支关系组织数据元素(称为树中的节点)的结构，很像自然界中的树。树木广泛存在于客观世界中。比如人类社会和各种社会组织的谱系，都可以用树来表示。树也广泛应用于计算机领域。例如，在编译源程序时，可以用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息组织的重要形式之一。所有有层次关系的问题都可以用树来描述。

树是元素的集合。我们先用更直观的方式介绍一下树。下面的数据结构是一棵树：

该树有多个节点来存储元素。有些节点有一定的关系，用连接线来表示，连接线叫边。边的上层节点称为父节点，下层节点称为子节点。这棵树就像一个不断分枝的根。

每个节点可以有多个子节点，并且该节点是相应子节点的父节点。比如3，5是6的子节点，6是3，5的父节点；1，8，7是3的子节点，3是1，8，7的父节点。树有一个没有父节点的节点，称为根节点(root)，如图6所示。没有子节点的节点称为叶节点，如图中的节点1、8、9、5。从图中也可以看出，上面的树一共四层，第一层6层，第四层9层。树中节点的最高级别称为深度。也就是树的深度是4。

如果从节点3往下看，忽略其他部分。所以我们看到的是一个以节点3为根节点的树：

三角形代表一棵树。

此外，如果我们定义一个孤立的节点也是一棵树，则原始树可以表示为根节点与子树之间的关系：

上面的观察实际上给了我们一个定义树的严格方法：

1.树是元素的集合。

2.集合可以是空的。此时，树中没有元素，所以我们称之为空树。

3.如果集合不为空，则集合有一个根节点和0个或更多的子树。根节点通过一条边与其子树的根节点相连。

上面第三点是递归定义树，即在定义树的过程中使用树本身(子树)。由于树的递归特性，许多与树相关的操作也可以通过递归方便地实现。我们以后再看。

树的实现

树的示意图给出了树的内存实现：每个节点存储元素和多个指向子节点的指针。然而，子节点的数量是不确定的。一个父节点可能有大量子节点，而另一个父节点可能只有一个子节点，在树中添加或删除节点会进一步改变子节点的数量。这种不确定性可能会带来很多内存相关的操作，很容易浪费内存。

一个经典的实现方法如下：

树的内存实现

具有相同父节点的两个节点彼此是兄弟节点。在上图的实现中，每个节点都包含一个指向第一个子节点的指针和另一个指向其下一个兄弟节点的指针。这样，我们就可以用一个统一明确的结构来表示每个节点。

计算机的文件系统是树形结构，比如Linux文件管理的背景知识。在UNIX文件系统中，每个文件(文件夹也是文件的一种)都可以看作一个节点。不是文件夹的文件存储在叶节点中。文件夹中有指向父节点和子节点的指针(在UNIX中，文件夹也包含指向自身的指针，这与我们上面看到的树不同)。在git中，有类似的树形结构来表达整个文件系统的版本变化(参考版本管理三国志)。

二叉树：

二叉树是n(n0)个节点的有限集，每个节点最多有两个子树。它要么是一个空集，要么由一个根和两个不相交的二叉树组成，这两个二叉树被称为左右子树。

特点：

(1)二叉树是有序树。即使只有一个子树，也必须区分左右子树；

(2)二叉树每个节点的度不能大于2，只能取0、1、2中的一个；

(3)二叉树中有五种节点：空节点、没有左右子树的节点、只有左子树的节点、只有右子树的节点和有左右子树的节点。

二叉树是一种特殊的树。二叉树的每个节点最多只能有2个子节点：

二叉树

因为二叉树的子节点数是确定的，所以可以按照上面所示的方式直接在内存中实现。每个节点都有一个左子节点(左子节点)和一个右子节点(右子节点)。左侧子节点是左侧子树的根节点，右侧子节点是右侧子树的根节点。

如果我们给二叉树添加一个附加条件，我们可以得到一个特殊的二叉树，叫做二叉查找树。二叉查找树要求每个节点不小于其左子树的任何元素，也不大于其右子树的任何元素。

(如果我们假设树中没有重复的元素，那么上述要求可以写成：每个节点大于其左子树中的任何节点，小于其右子树中的任何节点)

二叉查找树，注意树中元素的大小。

二叉查找树可以方便地实现搜索算法。当搜索元素X时，我们可以将X与根节点进行比较：

1.如果X等于根节点，那么找到X并停止搜索(终止条件)

2.如果x小于根节点，则搜索左边的子树。

3.如果x大于根节点，则搜索右边的子树

搜索二叉树所需的操作次数最多等于树的深度。n个节点的二叉查找树的深度至多为n，至少为log(n)。

二叉树的遍历

也就是说，遍历树的所有节点只被访问一次。根据根节点的位置，可以分为前序遍历、中序遍历和后序遍历。

预排序遍历：根节点-左子树-右子树

中序遍历：左子树-根节点-右子树

后序遍历：左子树-右子树-根节点

例如，找到以下树的三种遍历。

前序遍历：abdefgc

中序遍历：debgfac

后序遍历：edgfbca

二叉树的类型

(1)完全二叉树3354如果二叉树的高度为H，除H层外，其他所有层(1 ~ h-1)的节点数达到最大，H层有叶节点，叶节点从左到右依次排列，为完全二叉树。

(2)全二叉树3354除叶节点外，每个节点都有左右子叶，叶节点在底部。

(3)平衡二叉树3354平衡二叉树也叫AVL树(不同于AVL算法)。它是一棵二叉排序树，具有以下性质：它是一棵空树或其左右子树高度差的绝对值小于1，左右子树都是平衡二叉树。

如何判断一棵树是不是完全二叉树？本质上

根据教科书，深度为k且节点数为2^k-1的二叉树是完全二叉树。这个概念很好理解，就是深度为K且没有空位的树。

首先，按照广度优先遍历的顺序(从左到右)对完整的二叉树进行编号。

深度为k的二叉树有n个节点。然后，树也被编号。如果所有的数字都对应于完全二叉树，那么该树就是完全二叉树。

如何判断平衡二叉树？

(b)左图的左子树的高度是3，右子树的高度是1，大于1。

(b)右边图-2左子树的高度为0，右边子树的高度为2，相差超过1。

二叉树遍历实现

类TreeNode(对象):

def __init__(self，data=0，left=0，right=0):

self.data=数据

self.left=left

self.right=右

BTree类(对象):

def __init__(self，root=0):

self.root=root

定义预订(自身，treenode):

如果treenode为0:

返回

打印(treenode.data)

self.preOrder(treenode.left)

self.preOrder(treenode.right)

def inOrder(self，treenode):

如果treenode为0:

返回

self.inOrder(treenode.left)

打印(treenode.data)

self.inOrder(treenode.right)

def postOrder(self，treenode):

如果treenode为0:

返回

self.postOrder(treenode.left)

self.postOrder(treenode.right)

打印(treenode.data)

if __name__=='__main__ ':

n1=TreeNode(数据=1)

n2=TreeNode(2，n1，0)

n3=TreeNode(3)

n4=TreeNode(4)

n5=TreeNode(5，n3，n4)

n6=TreeNode(6，n2，n5)

n7=TreeNode(7，n6，0)

n8=TreeNode(8)

root=TreeNode('root '，n7，n8)

bt=BTree(根)

打印(“预订”)。中心(50，'-'))

print(bt.preOrder(bt.root))

打印('订单')。中心(50，'-'))

print (bt.inOrder(bt.root))

打印(“邮购”)。中心(50，'-'))

print (bt.postOrder(bt.root))

堆排序

堆排序，顾名思义，是基于堆的。所以我们先介绍一下堆的概念。

堆分为最大堆和最小堆，其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子，最小堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求，其实很好理解。有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。

堆排序就是把堆顶的最大数取出，

将剩余的堆继续调整为最大堆，具体过程在第二块有介绍，以递归实现

剩余部分调整为最大堆后，再次将堆顶的最大数取出，再将剩余部分调整为最大堆，这个过程持续到剩余数只有一个时结束

# _ * _编码：utf-8_*_

__作者__='李北岳'

导入时间，随机

def sift_down(arr，node，end):

根=节点

#print(root，2*root 1，end)

虽然正确：

# 从根开始对最大堆调整

child=2 * root 1 #left child

如果子端：

#print('break '，)

破裂

打印(' v:'，根，arr[根]，子，arr[子])

打印（排列)

# 找出两个儿童中交大的一个

if child 1=end and arr[child]arr[child 1]:#如果左边小于右边

子代=1 #设置右边为大

if arr[root] arr[child]:

# 最大堆小于较大的孩子，交换顺序

tmp=arr[root]

arr[root]=arr[child]

arr[child]=tmp

# 正在调整的节点设置为根

#print('less1:'，arr[root]，arr[child]，root，child)

root=child #

#[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]

#print('less2:'，arr[root]，arr[child]，root，child)

否则：

# 无需调整的时候，退出

破裂

#打印（排列)

打印('-')

极好的堆排序(arr):

# 从最后一个有子节点的孩子还是调整最大堆

first=len(arr) //2 -1

对于范围内的我(第一个，-1,-1):

sift_down(arr，I，len(arr) - 1)

#[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]

打印('- end -'，arr)

# 将最大的放到堆的最后一个，堆-1, 继续调整排序

对于范围内结束(len(arr) -1，0，-1):

数组[0],数组[结束]=数组[结束],数组[0]

sift_down(arr，0，end - 1)

#打印（排列)

def main():

# [7, 95, 73, 65, 60, 77, 28, 62, 43]

# [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]

#l=[3，1，4，9，6，7，5，8，2，10]

#l=[16，9，21，13，4，11，3，22，8，7，15，27，0

array=[16，9，21，13，4，11，3，22，8，7，15，29]

#array=[]

#对于范围内的我(25000):

# #打印（一)

#数组。追加(随机。兰德范围(1，I))

打印（数组)

start_t=time.time()

堆排序（数组)

end_t=time.time()

打印('成本：'，end_t -start_t)

打印（数组)

#打印（左)

#堆排序(l)

#打印（左)

if __name__=='__main__ ':

主()

人类能理解的版本

数据集=[16,9,21,3,13,14,23,6,4,11,3,15,99,8,22]

对于范围内的I(len(dataset)-1，0，-1):

print(' -'，dataset[0:i 1]，len(dataset)，I)

# for index in range(int(len(dataset)/2)，0，-1):

对于范围内的索引(int((I ^ 1)/2)，0，-1):

打印（索引)

p_index=索引

l_child_index=p_index *2 - 1

r_child_index=p_index *2

打印(' l索引，l_child_index，' r索引，r_child_index)

p_node=数据集[p_index-1]

left_child=数据集[l _儿童索引]

if p _ node left _ child:# switch p _ node with left child

数据集[p_index - 1]，数据集[l_child_index]=左_child，p_node

#重新定义p节点切换后，需要调用下面这个英国压力单位

p_node=数据集[p_index - 1]

if r _ child _ index len(dataset[0:I 1]):#避免右移出列表索引范围

# if r _ child _ index len(dataset[0:I]): #避免右移出列表索引范围

#打印（左_子)

right_child=数据集[r _子索引]

print(p_index，p_node，left_child，right_child)

# if p _ node left _ child:# switch p _ node with left child

#数据集[p_index - 1]，数据集[l_child_index]=左_child，p_node

# #切换后重新定义p_node下面需要调用这个英国压力单位

# p_node=数据集[p_index - 1]

#

if p _ node right _ child:# switch p _ node with right child

数据集[p_index - 1]，数据集[r_child_index]=右_child，p_node

#重新定义p节点切换后，需要调用下面这个英国压力单位

p_node=数据集[p_index - 1]

否则：

打印(' p节点[%s]没有正确的子节点% p _ node’)

#最后，这个列表的第一个值是最大堆的值。把这个最大值放在列表的最后，把剩下的神列表重新调整到最大堆。

print('开关I索引'，I，数据集[0]，数据集[i])

打印(“切换前”，数据集[0:i 1])

数据集[0]，数据集[i]=数据集[i]，数据集[0]

打印(数据集)

希尔排序（shell sort）

外壳排序是插入排序的一种。也称为减少增量排序，它是直接插入排序算法的一个更有效的改进版本。该方法的基本思想是：首先将整个待排序元素序列分成若干子序列(由相隔一定增量的元素组成)进行直接插入排序，然后在排序前依次递减增量。当整个序列中的元素基本有序(增量足够小)时，直接插入所有元素，重新排序。因为直接插入排序在元素基本有序时效率很高(接近最佳情况)，所以Hill排序在时间上比直接插入排序效率高得多。

首先要明确一下增量的取法：

第一次增量的方法是：d=count/2；

第二次增量的方法是：d=(count/2)/2；

最后：d=1；

看上图观测的现象为：

d=3时：比较40和50，因为50更大，所以不会交换。

??????????????将80跟60比，因60小，交换。

d=2时：将40跟60比，不交换，拿60跟30比交换，此时交换后的30又比前面的40小，又要将40和30交换，如上图。

????????????? 将20跟50比，不交换，继续将50跟80比，不交换。

d=1时：这时就是前面讲的插入排序了，不过此时的序列已经差不多有序了，所以给插入排序带来了很大的性能提高。

希尔排序代码

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。