搜索（Searching）是在项的集合中寻找特定项的算法程序。搜索返回的结果为布尔值 True 或 False 代表所寻找的项是否存在，当然它也可以返回项所在的位置。
在Python中，利用 in 操作可以非常简单地搜索项是否位于集合内：
8 in [1, 2, 3, 4, 5]False
3 in [1, 2, 3, 4, 5]True
实现搜索有很多方法，我们更加关注于算法的实现和性能。
当数据项排序在诸如列表等集合中，我们称其为线性或顺序关系。每一个数据项排序在相对位置，在Python列表中，索引代表其相对位置，非常便于我们顺序访问，该操作即为顺序搜索（Sequential Search）。
上图所示为顺序（线性）搜索，从列表第一项开始，依次搜索直到找到所要寻找的项，如果走出列表则表明所要寻找的项不存在。该算法的Python表示如下所示，参数为所搜寻的列表和目标项，返回布尔值 True 或者 False 。
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos = pos+1
return foundtestlist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]sequentialSearch(testlist, 0)True
sequentialSearch(testlist, 10)False
在搜索算法中，比较是重复最多的操作，并且因为列表是无序的，所需搜寻的项可以位于列表的任意位置，等价于搜索可以从列表的任意位置开始。如果所要搜寻的项不在列表中，就需要比较完列表中的所有项，也有可能所要搜寻的项位于列表的起首位置，平均下来需要比较$\frac{n}{2}$项，所以算法的复杂度为$\mathcal{O}(n)$。
| 最好情况 | 最坏情况 | 平均 | |
|---|---|---|---|
| 项在列表中 | 1 | n | n/2 |
| 项不在列表中 | n | n | n |
如果列表是有序的呢？因为所要搜寻的项可以位于列表的任意位置，所以该情况下，算法的复杂度仍然为$\mathcal{O}(n)$。但如果所需搜寻的项不在列表中，情况会稍有不同，如下面的图中所示，所需搜寻的项为50，当比较完项54时，我们直到其后任意一项都比它大，所以程序就不用继续往下比较了。
def orderedSequentialSearch(alist, item):
pos = 0
found = False
stop = False
while pos < len(alist) and not found and not stop:
if alist[pos] == item:
found = True
elif alist[pos] > item:
stop = True
else:
pos = pos + 1
return foundtestlist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]orderedSequentialSearch(testlist, 0)False
orderedSequentialSearch(testlist, 5.5)False
| 最好情况 | 最坏情况 | 平均 | |
|---|---|---|---|
| 项在列表中 | 1 | n | n/2 |
| 项不在列表中 | 1 | n | n/2 |
利用上面的顺序查找在有序列表中搜索特定项，比较完第一项之后，没有找到，接下来继续比较n-1项，但是如果用二分查找从比较中间一项开始，如果是所要查找的项，完成搜索，如果没有找到，且所要查找的项大于中间项，删掉中间项连带列表的下半部分，反之，删掉中间项和列表的上半部分，再做查找，重复以上步骤，直到完成查找。
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midPoint = (first + last) // 2
if alist[midPoint] == item:
found = True
elif alist[midPoint] > item:
last = midPoint - 1
else:
first = midPoint + 1
return foundtestlist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]binarySearch(testlist, 3)binarySearch(testlist, 13)分析上面的算法，其采用了分而治之（divide and conquer）的策略，即将一个复杂问题分割为小的部分，先解决小的部分，再重新组合整个问题得出结果。通过上面的描述，我们发现这也是一个递归函数，所以：
def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midPoint = len(alist) // 2
if alist[midPoint] == item:
return True
elif alist[midPoint] > item:
return binarySearch(alist[:midPoint], item)
else:
return binarySearch(alist[midPoint+1:], item)testlist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]binarySearch(testlist, 3)binarySearch(testlist, 13)如果开始有n项，第一次比较后，会去掉一半留下n/2项，第二次会留下n/4项，第三次会留下n/8项，以此类推：
| 比较 | 剩余项的数目 |
|---|---|
| 1 | n/2 |
| 2 | n/4 |
| 3 | n/8 |
| ... | ... |
| i | n/2^i |
当分割足够多的次数，列表中就会留下一项，再比较返回结果完成查找，此即寻找i使$\frac{n}{2^i}=1$，得到$i=\log n$，最多需要比较的次数为列表项数的对数，因此，其复杂度为$\mathcal{O}(\log n)$，需要注意的是在程序的递归调用中我们利用了列表的切片 binarySearch(alist[:midpoint],item) ，来产生列表的左（下）半部分传递到下一次调用中，在Python中切片操作的复杂度为$\mathcal{O}(k)$，所以实际上二分查找的性能并不能达到列表项数的对数，但我们可以先计算切片部分的开始和结束的索引，然后再进行切片。
虽然二分查找通常优于顺序查找，但是对于小的列表长度n并不值得额外的耗费来排序。实际上，我们经常需要考虑排序的额外耗费来获取查找的优势，如果我们排序一次，多次查找，就非常值得牺牲额外的耗费来做排序，当然，对于一个大列表，即使一次排序的耗费就非常大，这样从头开始查找则会是一个相对不错的选择。
下面，我们更进一步来构建一种数据结构，使搜索的复杂度为$\mathcal{O}(1)$，即散列法。它的基本思想是将列表中的项压缩成摘要，使得数据量变小，便于查找，散列表中的每一个位置称为插槽（slot）。例如下图所示，有一个长度为11的散列表，插槽名分别为0，1，2, ...， 10，项与插槽之间的映射关系为散列函数，散列函数将集合中的项映射到0到10的插槽名上。
假设有54，26，93，17，77和31，可以用取余方法作为散列函数，各项除以列表的长度11，余数作为散列值$(h(item)=item%11)$。
| 项 | 散列值 |
|---|---|
| 54 | 10 |
| 26 | 4 |
| 93 | 5 |
| 17 | 6 |
| 77 | 0 |
| 31 | 9 |
项被插入散列值对应的位置，11个插槽的6个位置被占用，装载因子（load factor）为$\lambda = \frac{numberofitemd}{tablesize}=\frac{6}{11}$。
如果想要查找某项，利用散列函数计算出插槽名，查看其是否存在于散列表，该查找操作复杂度为$\mathcal{O}(1)$，因为计算散列值并索引列表的对应位置为常数计算量。但现在还面临一个问题，即如果有一项为44那么取余为0，与77位于同一个插槽，该情况称为冲突（collision/clash）。
如果散列函数能将各项映射到各自独立的插槽中，其为理想散列函数。但对于随机给定的项集合，并没有一个系统的方法构建理想散列函数，但一个不那么理想的散列函数已经非常有效了。
构建理想散列函数的一个办法是增加散列表的长度使其能容纳每一项，这保证了每一项都有一个特定的插槽，但对于大数字的项会遇到困难，例如我们项存下25个学生的15位身份证号，就会浪费掉很多资源。
更为理想的散列函数应该尽可能减小冲突的可能、易于计算且使散列表均匀分布。折叠法（folding method）即将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列值。例如记录10位电话号码436-555-4601，可以将其分为两位数组成的数字组（43, 65, 55, 46, 01），然后相加43+65+55+46+01=210，如果散列表有11个插槽，那么再除11取余210%11=1，或者再反转某一个值43+56+55+64+01=219，再11取余219%11=1。
另外还有一种平方取中法（mid-square method），取关键字平方后的中间几位为散列值，例如项44平方后$44^2=1936$，取中间两位93，除11取余得到5，下表为利用平方取中法得到各项的散列值。
| Item | Remainder | Mid-Square |
|---|---|---|
| 54 | 10 | 3 |
| 26 | 4 | 7 |
| 93 | 5 | 9 |
| 17 | 6 | 8 |
| 77 | 0 | 4 |
| 31 | 9 | 6 |
同样可以对字符串中的字母创建散列函数，字母被视为一系列有序的值,例如单词“cat”。
ord('c')99
ord('a')97
ord('t')116
然后利用有序值相加利用取余法得到单词的散列值：
函数 hash 输入字符串返回0 到 tableSize -1 之间的散列值。
def hash(aString, tablSize):
sum = 0
for pos in range(len(aString)):
sum = sum + ord(aString[pos])
return sum%tableSize考虑到颠倒次序的单词得到和散列值与原单词相同，再以每个字母的位置当作权重相乘:
需要注意的是散列函数不要过于复杂，这样就会舍本逐末，将计算过多的耗费在计算散列值上了。
散列不发生冲突的可能性非常之小，必须有一系统的方法来在散列表放置冲突项，所以通常对冲突进行处理（CollisionResolution）。办法之一是在散列表中寻找另外一个开放的插槽来放置冲突项，比如从其应在在散列表的插槽位置开始向后依次探测，直到遇到第一个空插槽，这种尝试寻址下一个空插槽的方法称为开放定址法（openaddressing），而上述依次访问每一个插槽的方法为线性探测(LinearProbing)，在维基百科上的定义为：
开放定址法（openaddressing）：$hash_i=(hash(key)+d_i)\ mod\ m, i=1,2...k(k\le m-1)$，其中$hash(key)$为散列函数，$m$为散列表长，$d_i$为增量序列，$i$为已发生冲突的次数。增量序列可有下列取法：
$d_i=1,2,3...(m−1)$ 称为线性探测(Linear Probing)；即$d_i=i$，或者为其他线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，把散列地址存放在该空单元。
$d_i=±1^2,±2^2,±3^2...±k^2(k\le m/2)$ 称为平方探测(Quadratic Probing)。相对线性探测，相当于发生冲突时探测间隔$d_i=i62$个单元的位置是否为空，如果为空，将地址存放进去。
$d_i=伪随机数序列$ ，称为伪随机探测(Pseudorandom Probing)
对于整数序列(54,26,93,17,77,31,44,55,20)，当44放到插槽0时，发生冲突，线性探测会依次寻找空插槽，当发现插槽1为空时，将44放进去。然后是55，放到插槽2中，再然后是20访问插槽10，0，1，2最后放到插槽3。
用开放定址和线性探测法生成的散列表，在查找时也应遵循该法则，例如查找93，根据散列值5寻找插槽5，里面为93返回 True ，对于20，散列值9对应的值为31，然后需要在该插槽之后依次查找，直到找到20，返回 True 或者第一个空插槽，返回 False 。
但线性探测的弊端是会产生聚集（Cluster），在函数地址的表中，散列函数的结果不均匀地占据表的单元，在发生冲突的位置周围形成区块。会对其他插入项有影响，例如添加项20时，在散列值0处的聚集使它跳过这些插槽，在之后寻找空插槽。
可以通过“+3”探测法一定程度上避免聚集，以上方法通称为再散列（rehashing），对于简单的线性探测：
对于“+skip”探测：
为了保证所有的插槽都能被寻址，通常选用散列表的长度作为 skip 值。
此外还有平方探测(Quadratic Probing)
此外，另外一个办法是链接（Chaining），将冲突项放到同一个散列值下，当项增多时，会增加搜索的难度。当我们需要搜索项时，找到对应的散列值位置，在该散列值位置下的集合中寻找该项是否存在，这看起来似乎会使搜索更有效，但是实际并不一定。
Python中的字典有着键-值的结构，键用来搜索对应值，此即为映射（map）。映射数据类型的结构为键与值之间联系的无序集合，键-值之间的映射唯一，映射的操作有：
map()创建一个新的空映射，返回一个空映射集合。put(key, val)在映射中添加新的键-值对，如果键已经存在，替换掉旧的值。get(key)给出一个键，返回保存于映射中的值，否则返回None。del在映射中删除键值对，语法为del map[key]。len()返回映射中键值对的数目。in返回Ture如果键位于映射中，语法为key in map，否则返回False。
字典的一个优势是给定键，迅速返回对应的值，利用上述查找复杂度为$\mathcal{O}(1)$的散列表可以实现如此快速的查找。在下面的代码块中，利用两个列表创建 HashTable 类表示映射抽象数据类型，两个列表分别为 slots 和 data ，分别保存键和值。
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.sizehashfunction 表示简单的取余方法，冲突问题的解决方法为利用“+1”再散列函数的线性探测， put 函数假设 self.slots 为空，计算出初始散列值，如果对应的插槽不为空，循环利用 rehash 函数找到空插槽。如果没有空插槽，替换掉旧的值。
def put(self, key, data):
hashValue = self.hashFunction(key, len(self.slots))
if self.slots[hashValue] == None:
self.slots[hashValue] = key
self.data[hashValue] = data
else:
if self.slots[hashValue] == key:
self.data[hashValue] = data
else:
nextSlot = self.rehash(hashValue, len(self.slots))
while self.slots[nextSlot] != None and self.slots[nextSlot] != key:
nextSlot = self.rehash(nextSlot, len(self.slots))
if self.slots[nextSlot] == None:
self.slots[nextSlot] = key
self.data[nextSlot] = data
else:
self.data[nextSlot] = data
def hashFunction(self, key, size):
return key % size
def rehash(self, oldHash, size):
return (oldHash + 1) % size此外，get 函数计算初始散列值，如果该散列值不在初始插槽，用 rehash 函数定位下一个可能的位置。最后的 __getitem__ 和 __setitem__ 方法允许利用“[]”关联。
def get(self, key):
startSlot = self.hashFunction(key, len(self.slots))
data = None
stop = False
found = False
position = startSlot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position, len(self.slots))
if position == startSlot:
stop = True
return data
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)创建一个 HashTable 类的例子：
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self, key, data):
hashValue = self.hashFunction(key, len(self.slots))
if self.slots[hashValue] == None:
self.slots[hashValue] = key
self.data[hashValue] = data
else:
if self.slots[hashValue] == key:
self.data[hashValue] = data
else:
nextSlot = self.rehash(hashValue, len(self.slots))
while self.slots[nextSlot] != None and self.slots[nextSlot] != key:
nextSlot = self.rehash(nextSlot, len(self.slots))
if self.slots[nextSlot] == None:
self.slots[nextSlot] = key
self.data[nextSlot] = data
else:
self.data[nextSlot] = data
def hashFunction(self, key, size):
return key % size
def rehash(self, oldHash, size):
return (oldHash + 1) % size
def get(self, key):
startSlot = self.hashFunction(key, len(self.slots))
data = None
stop = False
found = False
position = startSlot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position, len(self.slots))
if position == startSlot:
stop = True
return data
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)H = HashTable()H[54] = "cat"H[26] = "dog"H[93] = "lion"H[17] = "tiger"H[77] = "bird"H[31] = "cow"H[44] = "goat"H[55] = "pig"H[20] = "chicken"H.slots[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
H.data['bird',
'goat',
'pig',
'chicken',
'dog',
'lion',
'tiger',
None,
None,
'cow',
'cat']
H[20]'chicken'
H[17]'tiger'
H[20] = 'duck'H[20]'duck'
H.data['bird',
'goat',
'pig',
'duck',
'dog',
'lion',
'tiger',
None,
None,
'cow',
'cat']
print(H[99])None
考虑装载因子
对于每一次成功或不成功的查找，其所需要的比较次数分别为
排序即将集合内的元素按照一定的顺序排列。排序是计算机科学的一个重要研究方向，排序大量元素需要消耗巨量的计算资源，因此，需要找到一些改进的方法。在比较各算法的优略之前，我们需要先选定一个标准，首先，排序一个列表需要比较两个元素的大小，因此，比较次数是排序通用的衡量标准，此外，当元素未在正确的位置，需要与其他元素交换位置，交换的次数也是衡量排序算法标准。
冒泡排序多次遍历列表，它比较相邻项并交换错序的项，每一次遍历都将更大的项放到合适的位置，实际上，每个项“冒泡”到所属位置。
上图显示了冒泡排序的第一次遍历，阴影两项做对比，如果列表有n项，一次遍历需要n-1次对比。一旦最大项位于比较对中，就会一直沉淀直到完成该次遍历。当第二次遍历开始时，无序项为n-1个，需要n-2次对比，直到n-1次遍历，最小项位于正确的位置。
def bubbleSort(alist):
for passNum in range(len(alist)-1, 0, -1):
for i in range(passNum):
if alist[i] > alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = tempalist = [2, 5, 1, 3, 6, 9, 8, 7, 0, 4]bubbleSort(alist)alist[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
交换操作称为“swap”，在Python中的表示与其他语言略有不同。通常交换列表中的两项需要额外的缓存：
temp = alist[i]
alist[i] = alist[j]
alist[j] = temp
上面的片段会交换列表中的第i项和第j项，如果没有临时缓存，其中一个值就会被覆盖。但在Python中，可以通过一次同时赋值声明 a, b = b, a 来实现交换操作。
无论列表中n个元素如何排列，冒泡排序都需要经历n-1次遍历重新排列，列表中显示了每一次遍历的比较次数，一次冒泡排序总共比较次数为$\frac{1}{2}n^2-\frac{1}{2}n$次，复杂度为$\mathcal{O}(n^2)$。最理想的情况下，一次交换都不需要，最差是每次比较都需要交换，平均为比较次数的一半。
| 遍历 | 比较 |
|---|---|
| 1 | n-1 |
| 2 | n-2 |
| 3 | n-3 |
| ... | ... |
| n-1 | 1 |
如果排序遍历完一次后，不需要交换，那么列表肯定是有序的，我们就可以提前结束排序程序，这也是冒泡排序的一个优势，相应代码如下：
def shortBubbleSort(alist):
exchanges = True
passNum = len(alist) - 1
while passNum > 0 and exchanges:
exchanges = False
for i in range(passNum):
if alist[i] > alist[i+1]:
exchanges = True
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passNum = passNum - 1alist = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]shortBubbleSort(alist)alist[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
动图显示冒泡排序
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from matplotlib import rc
# equivalent to rcParams['animation.html'] = 'html5'
rc('animation', html='html5')
fig = plt.figure()
plt.title('Bubble Sort')
alist = [2, 5, 1, 3, 6, 9, 8, 7, 4]
color = ['gray']*len(alist)
ims = []
for passNum in range(len(alist)-1, 0, -1):
for i in range(passNum):
color[i] = 'red'
color[i+1] = 'red'
im1 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
plt.xticks([])
plt.yticks([])
ims.append(im1)
if alist[i] > alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
im2 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
plt.xticks([])
plt.yticks([])
ims.append(im2)
color[i] = 'gray'
color[i+1] = 'gray'
ani = animation.ArtistAnimation(fig, ims, interval=50, blit=True, repeat_delay=1000)
ani选择排序在冒泡排序的基础上改进，其一次遍历只做一次交换。在一次遍历中，冒泡排序寻找最大的项，完成遍历后，将其放到合适的位置，接下来是遍历n-1项，将最大的项放到合适的位置，下面图显示了选择排序的过程，
def selectionSort(alist):
for fillSlot in range(len(alist)-1, 0, -1):
positionOfMax = 0
for location in range(1, fillSlot+1):
if alist[location] > alist[positionOfMax]:
positionOfMax = location
temp = alist[fillSlot]
alist[fillSlot] = alist[positionOfMax]
alist[positionOfMax] = tempalist = [2, 5, 1, 3, 6, 9, 8, 7, 0, 4]selectionSort(alist)alist[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
和冒泡排序一样，选择排序的比较次数也为$\mathcal{O}(n^2)$，但是因为交换次数较少了，选择排序通常执行地更快。
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from matplotlib import rc
# equivalent to rcParams['animation.html'] = 'html5'
rc('animation', html='html5')
fig = plt.figure()
plt.title('Selection Sort')
plt.xticks([])
plt.yticks([])
alist = [2, 5, 1, 3, 6, 9, 8, 7, 4]
color = ['gray']*len(alist)
ims = []
for fillslot in range(len(alist)-1,0,-1):
color[fillslot] = 'blue'
positionOfMax = 0
color[positionOfMax] = 'yellow'
im1 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
ims.append(im1)
for location in range(1, fillslot+1):
color[location] = 'red'
im2 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
ims.append(im2)
if alist[location] > alist[positionOfMax]:
color[positionOfMax] = 'gray'
positionOfMax = location
color[positionOfMax] = 'yellow'
im3 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
ims.append(im3)
else:
color[location] = 'gray'
im4 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
ims.append(im4)
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp
color[fillslot] = 'yellow'
color[positionOfMax] = 'gray'
im5 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
ims.append(im5)
color[fillslot] = 'gray'
im6 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
ims.append(im6)
ani = animation.ArtistAnimation(fig, ims, interval=50, blit=True, repeat_delay=1000)
ani插入排序通过将每一个新的比较项插入到之前已经比较并排序过的项列表中合适位置，其复杂度仍然为$\mathcal{O}(n^2)$，下图为插入排序的操作流程，阴影部分表示每次遍历已经比较并排序过的子列表。
开始时，假设0位置第一项为有序子列表，每一次遍历，将当前项与有序子列表中的元素做比较，将比它大的项移到右面，直到遇到较小的项或者子列表的一端，将当前项插入。
比如上图所示，拥有5项的有序子列表内元素为17，26，54，77和93，当前项为31，首先与93比较，93比31大，向右移动，然后是77，54，当遇到26时，其比26大，停止比较并将31插入到当前位置，得到了有6个项的有序子列表。
插入排序仍然需要n-1次遍历来排序n个项，循环从位置1开始，到位置n-1，同时需要移动操作将项向后移动一个位置，为插入项留下空间，其与之前的交换操作有所不同，由于只有一次赋值，因此移动操作仅需交换操作近乎1/3操作。
插入排序所需最大比较次数为前n-1个整数的和，是$\mathcal{O}(n^2)$，最理想的情况为一次比较，即列表已经是有序的。
def insertionSort(alist):
for index in range(1, len(alist)):
currentValue = alist[index]
position = index
while position > 0 and alist[position-1] > currentValue:
alist[position] = alist[position-1]
position = position -1
alist[position] = currentValuealist = [2, 5, 1, 3, 6, 9, 8, 7, 0, 4]insertionSort(alist)alist[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from matplotlib import rc
# equivalent to rcParams['animation.html'] = 'html5'
rc('animation', html='html5')
fig = plt.figure()
plt.title('Insertion Sort')
plt.xticks([])
plt.yticks([])
alist = [2, 5, 1, 3, 6, 9, 8, 7, 4]
color = ['gray']*len(alist)
ims = []
for index in range(1, len(alist)):
for i in range(index):
color[i] = 'black'
currentValue = alist[index]
position = index
color[position] = 'red'
im1 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
#plt.show()
ims.append(im1)
while position > 0 and alist[position-1] > currentValue:
color[position] = 'red'
color[position-1] = 'blue'
im2 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
#plt.show()
ims.append(im2)
alist[position] = alist[position-1]
alist[position-1] = 0
color[position] = 'black'
position = position - 1
color[position] = 'red'
if position > 0:
color[position-1] = 'blue'
im3 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
#plt.show()
ims.append(im3)
color[position-1] = 'black'
alist[position] = currentValue
color[position] = 'red'
im4 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
#plt.show()
ims.append(im4)
for i in range(index+1):
color[i] = 'black'
im5 = plt.bar(np.arange(len(alist)), alist, color=color, animated=True, visible=True)
#plt.show()
ims.append(im5)
ani = animation.ArtistAnimation(fig, ims, interval=50, blit=True, repeat_delay=1000)
ani希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本，将原来的列表拆成几个小的列表，每一个子列表分别用插入排序排序，希尔排序的关键是子列表的选择，相比将列表按相邻的项拆分，希尔排序利用步长（间隔）i，来选取元素构建子列表。
如上图所示，列表含有九个元素，我们用步长3将其分为3个子列表，每一个子列表用插入法排序，当排序完成后，得到的列表如下图所示，尽管列表并不是完全有序排列的，但是我们可以发现，它们离其本应该在的位置更近了。
接下来的一张图显示了最终利用步长为1的插入法（即标准插入排序）将列表排序，在上述操作的基础上，只需要4次移动操作。
希尔排序最主要的特性是其步长的选择，我们可以利用代码来比较选取不同的步长性能，首先，选择$\frac{n}{2}$为步长拆分列表，下一次遍历选择$\frac{n}{4}$为步长拆分列表，直到最终以1为步长的基本插入排序。下图显示了第一次遍历的以$\frac{n}{2}$为步长拆分的子列表。
下面的 shellSort 函数显示了每一个步长拆分下子列表的排序，最后一次排序的步长值为1。
def shellSort(alist):
sublistCount = len(alist) // 2
while sublistCount > 0:
for startPosition in range(sublistCount):
gapInsertionSort(alist, startPosition, sublistCount)
print('After increment of size', sublistCount, 'The list is', alist)
sublistCount = sublistCount // 2
def gapInsertionSort(alist, start, gap):
for i in range(start+gap, len(alist), gap):
currentValue = alist[i]
position = i
while position >= gap and alist[position-gap] > currentValue:
alist[position] = alist[position-gap]
position = position - gap
alist[position] = currentValuealist = [54, 26, 93, 17, 77, 31, 44, 55, 20]shellSort(alist)After increment of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]
After increment of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]
After increment of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from matplotlib import rc
# equivalent to rcParams['animation.html'] = 'html5'
rc('animation', html='html5')
fig = plt.figure()
plt.title('Shell Sort')
plt.xticks([])
plt.yticks([])
alist = [2, 5, 1, 3, 6, 9, 8, 7, 4]
color = ['gray']*len(alist)
ims = []
im1 = plt.bar(np.arange(len(alist)), alist, color=color)
#plt.show()
ims.append(im1)
def gapInsertionSort(alist, start, gap):
for index in range(start+gap, len(alist), gap):
color[start] = 'red'
im2 = plt.bar(np.arange(len(alist)), alist, color=color)
#plt.show()
ims.append(im2)
color[index] = 'red'
im3 = plt.bar(np.arange(len(alist)), alist, color=color)
#plt.show()
ims.append(im3)
currentValue = alist[index]
position = index
while position >= gap and alist[position-gap] > currentValue:
alist[position] = alist[position-gap]
alist[position-gap] = 0
position = position - gap
im4 = plt.bar(np.arange(len(alist)), alist, color=color)
#plt.show()
ims.append(im4)
alist[position] = currentValue
im5 = plt.bar(np.arange(len(alist)), alist, color=color)
#plt.show()
ims.append(im5)
for index in range(start, len(alist), gap):
color[index] = 'gray'
im6 = plt.bar(np.arange(len(alist)), alist, color=color)
#plt.show()
ims.append(im6)
sublistCount = len(alist) // 2
while sublistCount > 0:
for startPosition in range(sublistCount):
gapInsertionSort(alist, startPosition, sublistCount)
sublistCount = sublistCount // 2
ani = animation.ArtistAnimation(fig, ims, interval=50, blit=True, repeat_delay=1000)
ani乍看之下，希尔排序在最后一步做了一次完全插入排序，可能其并不比插入操作表现更好，但是，由于之前的步进插入排序操作将列表初步排序，即该列表相比之下更有序（有点类似熵的概念，熵比较大），因此最后的插入排序不需要过多的比较和移动，操作起来更快。由于步长的选择，希尔排序的复杂度在
归并排序（英语：Merge sort，或mergesort），是建立在归并操作上的一种有效的排序算法，效率为$\mathcal{O}(n\log n)$。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，递归地将列表分为两部分，直到子列表为空，才开始排序，当两个子列表排序完成后，开始归并操作——即将两个小的有序列表结合成一个新的有序列表，下面两张图分别显示了归并排序 mergeSort 的拆分和归并操作。
函数 mergeSort 如下所示，终止条件是子列表的长度小于或等于1，利用Python中的 slice 操作将列表分为左右两部分。
def mergeSort(alist):
# show the contents of the list being sorted at the start of each invocation
print("Splitting", alist)
if len(alist) > 1:
mid = len(alist) // 2
leftHalf = alist[:mid]
rightHalf = alist[mid:]
mergeSort(leftHalf)
mergeSort(rightHalf)
# merging the two smaller sorted lists into a larger sorted list
i, j, k = [0, 0, 0]
while i < len(leftHalf) and j < len(rightHalf):
if leftHalf[i] < rightHalf[j]:
alist[k] = leftHalf[i]
i = i+1
else:
alist[k] = rightHalf[j]
j = j+1
k = k+1
while i < len(leftHalf):
alist[k] = leftHalf[i]
i = i+1
k = k+1
while j < len(rightHalf):
alist[k] = rightHalf[j]
j = j+1
k = k+1
# show the merging process
print('Merging', alist)alist = [54,26,93,17,77,31,44,55,20]mergeSort(alist)Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting [54, 26, 93, 17]
Splitting [54, 26]
Splitting [54]
Merging [54]
Splitting [26]
Merging [26]
Merging [26, 54]
Splitting [93, 17]
Splitting [93]
Merging [93]
Splitting [17]
Merging [17]
Merging [17, 93]
Merging [17, 26, 54, 93]
Splitting [77, 31, 44, 55, 20]
Splitting [77, 31]
Splitting [77]
Merging [77]
Splitting [31]
Merging [31]
Merging [31, 77]
Splitting [44, 55, 20]
Splitting [44]
Merging [44]
Splitting [55, 20]
Splitting [55]
Merging [55]
Splitting [20]
Merging [20]
Merging [20, 55]
Merging [20, 44, 55]
Merging [20, 31, 44, 55, 77]
Merging [17, 20, 26, 31, 44, 54, 55, 77, 93]
分别考虑归并排序的拆分和归并操作，对半拆分长度为n的列表需要操作$\log n$次，归并长度为n的列表需要操作n次，总的操作次数为
另外切记，切片长度为k的列表复杂度为 mergeSort 需要额外的空间存储列表的两半部分，当数据量大的时候，会导致一些问题。
快速排序同样利用分治（divide and conquer）法获取更高的效率，但其无需额外的存储空间，然而代价是列表可能不会对半分拆，这回影响其效率。
快速排序开始先选中一个值，称为关键值，选取关键值有很多方式，我们先以选取第一项为例。关键值的作用是协助分拆列表，其在最终排序好的列表中的位置为拆分点，快速排序调用该点拆分列表。
下面图示的例子中，54作为关键值，其最终的位置在当前31所在位置，然后开始拆分操作，然后将比它小和大的值分别放到其两边。
拆分操作开始先定位两个位置标志， leftmark 和 rightmark ，位于剩下列表的开始和结束位置（图中位置1和8），其目的是将相对于关键值错序的项移动到正确位置（比关键值大或小的位置），同时关键中也趋近于拆分点，如下图所示
递增 leftmark 直到遇到比关键值大的值，然后递增 rightmark 直到遇到比关键值小的值，这两个值相较于拆分点错位，图中的93和20，然后交换它们的位置并继续重复以上操作。
当 rightmake 小于 leftmark 时，终止操作， 当前rightmark 所处的位置即为拆分点，然后与关键值交换位置，现在拆分点左边的项都比关键值小，右边的值都比关键值大，然后，将列表拆分两半，分别递归调用快速排序。
quickSort 函数如下所示，quickSortHelper 为递归函数，与归并排序的终止条件相同，即如果列表的长度小于或等于1，列表为有序的，大于1继续拆分递归排序。patition 函数上述操作的表示。
def quickSort(alist):
quickSortHelper(alist, 0, len(alist)-1)
def quickSortHelper(alist, first, last):
if first < last:
splitPoint = partition(alist, first, last)
quickSortHelper(alist, first, splitPoint-1)
quickSortHelper(alist, splitPoint+1, last)
def partition(alist, first, last):
pivotValue = alist[first]
leftmark = first + 1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotValue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotValue and rightmark >= leftmark:
rightmark = rightmark - 1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmarkalist = [54,26,93,17,77,31,44,55,20]quickSort(alist)alist[17, 20, 26, 31, 44, 54, 55, 77, 93]
分析 quickSort 的效率，对半拆分一个长度为n的列表需要
但在非理想情况下，拆分点并不总是在列表正中间，或靠右，或靠左，会将n个元素的列表分为0项和n-1项，然后将n-1项分为0项和n-2项，如此往复，这些递归总的复杂度为
之前有表，关键值的选取有不同的方法，有一种称为三数取中法（median of three），考虑列表的首尾和中间三项，例如上面列表的54，77和20。取三个数的中位数54作为关键值，该方法对于排序一些“熵”比较大的列表非常有用。
- 对于有序和无序列表，顺序搜索的效率皆为
$\mathcal{O}(n)$ 。 - 二分查找在搜索有序列表时，表现最差，效率为$\mathcal{O}(\log n)$。
- 散列（哈希）表为常数级搜索。
- 冒泡排序、选择排序和插入排序的效率皆为
$\mathcal{O}(n^2)$ 。 - 希尔排序在插入排序的基础上，利用步进子列表改进性能，效率为
$\mathcal{O}(n)$ 与$\mathcal{O}(n^2)$ 之间。 - 归并排序的效率为
$\mathcal{O}(n\log n)$ ，但需要额外的存储空间。 - 快速排序的效率为
$\mathcal{O}(n\log n)$ ，但如果拆分点并不靠近列表的中间会变差为$\mathcal{O}(n^2)$ 。此外其无需额外存储空间。