1.搜索
1.1 顺序搜索
列表中,数据项的位置就是他的下标
#无序列表的顺序搜索
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos += 1
return found
#有序列表的顺序搜索
def orderedSequentialSearch(alist, item):
pos = 0
found = False
stop = False
while pos = len(alsit) and not found and not stop:
if alist[pos] == item:
found = True
else:
if alist[pos] < item:
pos += 1
else:
stop = True
return found
1.2 二分搜索
仅针对有序列表
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
else:
if item > alist[midpoint]:
first = midpoint + 1
else:
last = midpoint -1
return found
递归版本
def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist) // 2
if alist[midpoint] == item:
return True
else:
if item < alist[midpoint]:
return binarySearch(alist[:midpoint, item)
else:
return binarySearch(alist[midpoint+1, item)
1.3 散列
散列函数:
1. 折叠法:将元素切成等长的部分(最后一部分的长度可能不同),然后将这些部分相加,得到散列值
2. 平凡取中法:先将元素取平方,然后提取中间几位数
为字符串构建简单的散列函数
def hash(astring, tablesize):
sum = 0
for pos in range(len(astring)):
sum += ord(astring[pos])
return sum % tablesize
冲突处理
1. 开放定址法
* 线形探测
* 平方探测
2. 链接法
实现映射抽象数据类型
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[hashvale] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
nextslot = self.rehash(hashvalue, len(self.slots))
while self.slots[nextslots] != None and self.slots[nextslots] != 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):
self.put(key,data)
2.排序
2.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] = temp
#递归版本
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]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passnum -= 1
2.2 选择排序
def selectionSort(alist):
for fillslot in range(len(alist)-1, 0, -1):
positionOFMax = 0
for location in range(1, fillsolt+1):
if alist[location] > alist[positionOfMax]:
positionOfMax = location
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp
2.3 插入排序
def insertSort(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 -= 1
alist[position] = currentvalue
2.4 希尔排序
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 gapInsertSort(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] = currentvalue
2.5 归并排序
def mergeSort(alist):
print('Splitting', alist)
if len(alist) > 1:
mid = len(alist) > 1:
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i = 0
j = 0
k = 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[i]
j = j + 1
k = K + 1
print('Merging ',alist)
2.6 快速排序
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):
pivot = alist[first]
leftmark = first + 1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark += 1
while rightmark >= leftmark and alist[rightmark] >= pivotvalue:
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 rightmark