Python数据结构与算法笔记（4）

problem-solving-with-algorithms-and-data-structure-using-python 中文版 5 排序和搜索

顺序查找

当数据项存储在诸如列表的集合中时，我们说它们具有线性或顺序关系。每个数据项都存储在相对与其他数据项的位置。在Python列表中，这些相对位置是单个项的索引值。由于这些索引值是有序的，我们可以按顺序访问它们。这个过产生了顺序查找。

二分查找

二分查找从中间项开始，而不是按照顺序查找列表。

5.4.äºåæ¥æ¾.figure3

Hash查找

哈希表是以一种容易找到它们的方式存储项的集合，哈希表的每个位置，通常称为一个槽，可以容纳一个项，并且从0开始的整数值命名。并且从0开始的整数值命名。

项和该项在散列表中所属的槽之间的映射被称为hash函数。hash函数将接收集合中的任何项，并在槽名范围内（0和m-1之间）返回一个整数。

负载因子，lambda=项数/表大小，下面这个例子中，为6/11

5.5.Hashæ¥æ¾.figure5

现在，要搜索一个项时，我们只需使用哈希函数来计算项的槽名称，然后检查哈希表以查看它是否存在。

根据散列函数，两个或者更多项将需要在同一槽中，这种现象被称为碰撞（也被称为冲突）。

目标是创建一个散列函数，最大限度地减少冲突数，易于计算，并均匀分布在哈希表中的项。

• 分组求和法将项划分为相等大小的块（最后一块可能不是相等大小）。然后将这些块加载一起求出散列值
• 用于构造散列函数的另一数值技术被称为平方取中法。首先对该项平方，然后提取一部分数字结果。
• 还可以基于字符的项（如字符串）创建哈希函数

哈希函数必须是高效的，以便他不会称为存储和搜索过程的主要部分。如果哈希函数太复杂，则计算槽名称的程序要比之前所述的简单地进行基本的顺序或二分搜索更耗时。这将打破散列的目的。

当两个散列项列到同一个槽时，必须有一个系统的方法将第二个项放在散列表中，这个过程称为冲突解决。

解决冲突的一种方法是查找散列表，尝试查找到另一个空槽以保存导致冲突的项。一个简单的方法是从原始哈希值位置开始，然后以顺序方式移动槽，直到遇到第一个空槽。注意，可能需要回到第一个槽（循环）以查找整个散列表。这种冲突解决过程被称为开放寻址，因为它试图在散列表中找到下一个空槽或地址。通过系统地一次访问每个槽，我们执行称为线性探测的开放寻址技术。

线性探测的缺点是聚集的趋势，项在表中聚集，这意味着如果在相同的散列值处发生很多冲突，则将通过线性探测来填充多个周边槽。这将影响正在插入的其它项。

处理聚集的一种方式是扩展线性探测技术，使得不是顺序地查找下一个开放槽，而是跳过槽，从而更均匀地分布已经引起冲突的项，这将潜在地减少发生的聚集。

在冲突后寻找另一个槽的过程叫做重新散列。需要注意的是，跳过的大小，必须使得表中的所有槽最终都被访问。否则，表的一部分将不被使用，为了确保这一点，通过建议表大小是素数。

线性探测思想的一个变种称为二次探测，代替使用常量跳过值。

用于处理冲突问题的替代方法是允许每个槽保持对项的集合（或链）的引用。链接允许许多项存在于哈希表中的相同位置。当发生冲突时，项仍然放在散列表的正确槽中。随着越来越多的项哈希到相同的位置，搜索集合中项的难度增加。

5.5.Hashæ¥æ¾.figure12

实现map抽象数据类型：

字典是一种关联数据类型，可以在其中存储键值对，该键用于查找关联的值。经常把这个想法称为map。

map抽象数据类型定于如下，该结构是键与值之间的关联的无序集合。map中的键都是唯一的，因此键和值之间存在一对一的关系。操作如下：

• Map()创建一个新的map，返回一个空的map集合
• put(key,val)向map中添加一个新的键值对。如果键已经在map中，那么用新值替换旧值
• get(key)给定一个键，返回存储在map中的值或None
• del使用del map[key]形式的语句从map中删除键值对
• len()返回存储在map中的键值对的数量
• in返回True对于key in map语句，如果给定的键在map中，否则为False

字典的一个很大的好处是，给定一个键，我们可以非常快速地查找相关的值。为了提供这种快速查找的能力，需要一个支持高校搜索的实现。我们可以使用具有顺序或二分查找的列表，但是使用哪个哈希表更好，因为查找哈希表中的项可以接近O(1)性能

hash法分析

分析散列表的使用最重要的信息是负载因子lambda。如果lambda小，则碰撞机会较低，这意味着项更可能在它们所属的槽中。如果lambda大，意味着表正在填满，则存在越来越多的冲突。这意味着冲突解决更困难，需要更多的比较来找到一个空槽。使用链接，增加的碰撞意味着每个链上的项数量增加。

搜索有成功的和不成功的。对于使用具有线性探测的开放寻址的成功搜索，平均比较数大约为1/2(1+1/(1-lambda))，不成功的搜索为1/2(1+(1/1-lambda)^2)。如果使用链接，成功的情况，平均比较数目是1+lambda/2，如果搜索不成功，则简单地是lambda比较次数。

排序

冒泡排序

冒泡排序需要多次遍历列表。它比较相邻的项并交换那些无序的项。每次遍历表将下一个最大的值放在其正确的位置。

选择排序

选择排序改进了冒泡排序，每次遍历列表只做一次交换，为了做到这一点，一个选择排序在遍历时寻找最大值，并在遍历完成之后，将其放在正确的位置。

选择排序与冒泡排序有相同数量的比较，也是O（n^2），但是由于交换数量的减少，选择排序通常在基准研究中执行更快。

插入排序

插入排序仍然是O（n^2），工作方式略有不同，始终在列表较低的位置维护一个排序的子列表。然后将每个新项插入之前的子列表，使得排序的子列表成为较大的一个项。

希尔排序

希尔排序，有时也称为递减递增排序，通过将原始列表分解为多个较小的子列表来改进插入排序，每个子列表使用插入排序进行排序。选择这些子列表的方式是希尔排序的关键。不是将列表拆分为连续项的子列表，希尔排序使用增量i，有时也称为gap，通过选择i个项的所有项来创建子列表。

5.10.å¸å°æåº.figure6

乍一看，可能认为希尔排序不会比插入排序更好，因为他最后一步执行了完整的插入排序。然后，因为最终的插入排序不需要非常多的比较（或移位），因为该列表已经被较早的增量插入排序预排序，换句话说，每个遍历产生比前一个更有序的列表。使得最终遍历非常有效。

归并排序

使用分而治之策略作为提高排序算法性能的一种方法。归并排序是一种递归算法，不断将列表拆分为一般。如果列表为空或有一个项，则按定义进行排序。如果列表有多个项，分割列表并递归调用两个半部分的合并排序。一旦对这两个部分排序完成，就执行称为合并的基本操作。合并是获取两个较小的排序列表并将它们组合成单个排序的新列表的过程。

5.11.å½å¹¶æåº.figure10

5.11.å½å¹¶æåº.figure11

快速排序

快速排序使用分而治之来获得与归并排序相同的优点，而不使用额外的存储。

快速排序首先选择一个值，该值称为枢轴值。枢轴值得作用是帮助拆分列表。枢轴值术语最终排序列表（拆分点）的实际位置，将用于将列表划分为快速排序的后续调用。

总结

• 对于有序和无序列表，顺序搜索是 O(n)。
• 在最坏的情况下，有序列表的二分查找是 O(log^n )。
• 哈希表可以提供恒定时间搜索。
• 冒泡排序，选择排序和插入排序是 O(n^2 )算法。
• shell排序通过排序增量子列表来改进插入排序。它落在 O(n) 和 O(n^2 ) 之间。
• 归并排序是 O(nlog^n ），但是合并过程需要额外的空间。
• 快速排序是 O(nlog^n ），但如果分割点不在列表中间附近，可能会降级到O(n^2 ) 。它不需要额外的空间。