排序与查找
| 算法 | 复杂度 | 其他 |
|---|---|---|
| 冒泡、选择、插入 | o(n^2) | |
| 谢尔排序 | o(n)-o(n^2) | 对于插入排序的改进 |
| 归并排序 | o(nlogn) | 但需要额外存储空间 |
| 快速排序 | 最好为o(nlogn)，分裂点偏离中心时o(n^2) | 不需要额外存储空间 |
总结：需要针对数据情况（比如随机性）来判断选择哪种算法~
顺序查找
按照下标增长逐个比对复杂度o(n)
二分查找
算法复杂度o(logn)
## 将代码块运行结果全部输出，而不是只输出最后的，适用于全文
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
# 有序表顺序查找
def orderedSearch(alist, item):
found = False
stop = False
i=0
while i < len(alist) and not found and not stop:
i = i+1
if item < alist[i]:
stop = True
elif item==alist[i]:
found = True
return found
orderedSearch([1,4,5,7,8,22,34,76,90,105],23)
### 二分查找的递归算法
### 如果只剩下1个数字，直接对比，如果不是则不存在
def binarySearch(alist,item):
found = False
# 结束条件：
if not len(alist)==0:
# 找到中间
mid = len(alist)//2
if item==alist[mid]: found = True
if item<alist[mid]: found = binarySearch(alist[:mid],item)
if item>alist[mid]: found = binarySearch(alist[mid+1:],item)
print(alist)
return found
binarySearch([1,4,5,7,8,16,22,34,66,73,89,90,101,105],5)
[5]
[1, 4, 5]
[1, 4, 5, 7, 8, 16, 22]
[1, 4, 5, 7, 8, 16, 22, 34, 66, 73, 89, 90, 101, 105]
True
冒泡排序
-
对无序表多躺比较，每趟多次相邻对比交换，并交换。第i躺排序第i大的项。
-
时间复杂度为o(n^2)
-
改进，加入这一趟是否有exchange
alist = [34,82,66,14,56,80,9,44,69,21]
## 冒泡排序
for j in range(len(alist)-1):
for i in range(len(alist)-j-1):
if (alist[i]>alist[i+1]): # 相邻对比交换
alist[i],alist[i+1]=alist[i+1],alist[i] # py支持直接交换，不用在写temp
print(j+1, alist)
### 如何改进：如果某一趟没有任何改变，就不再继续了
alist = [34,82,66,14,56,80,9,44,69,21]
print("\n")
exchange=1
j=0
while j<len(alist)-1 and exchange>0:
exchange=0
j=j+1
for i in range(len(alist)-j-1):
if (alist[i]>alist[i+1]): # 相邻对比交换
alist[i],alist[i+1]=alist[i+1],alist[i] # py支持直接交换，不用在写temp
exchange+=1
print(j, alist)
1 [34, 66, 14, 56, 80, 9, 44, 69, 21, 82]
2 [34, 14, 56, 66, 9, 44, 69, 21, 80, 82]
3 [14, 34, 56, 9, 44, 66, 21, 69, 80, 82]
4 [14, 34, 9, 44, 56, 21, 66, 69, 80, 82]
5 [14, 9, 34, 44, 21, 56, 66, 69, 80, 82]
6 [9, 14, 34, 21, 44, 56, 66, 69, 80, 82]
7 [9, 14, 21, 34, 44, 56, 66, 69, 80, 82]
8 [9, 14, 21, 34, 44, 56, 66, 69, 80, 82]
9 [9, 14, 21, 34, 44, 56, 66, 69, 80, 82]
1 [34, 66, 14, 56, 80, 9, 44, 69, 82, 21]
2 [34, 14, 56, 66, 9, 44, 69, 80, 82, 21]
3 [14, 34, 56, 9, 44, 66, 69, 80, 82, 21]
4 [14, 34, 9, 44, 56, 66, 69, 80, 82, 21]
5 [14, 9, 34, 44, 56, 66, 69, 80, 82, 21]
6 [9, 14, 34, 44, 56, 66, 69, 80, 82, 21]
7 [9, 14, 34, 44, 56, 66, 69, 80, 82, 21]
选择排序
复杂度仍然是o(n^2)，但是性能优于冒牌。
alist = [34,82,66,14,56,80,9,44,69,21]
for i in range(1,len(alist)):
if len(alist[i:])>=1:
tmp = alist[i]
j=1
while j <= i and alist[i-j]>tmp: # 如果比前一个大，前一个往后挪
alist[i-j+1]=alist[i-j]
j = j+1
alist[i-j+1]=tmp # 挪出来的空位插入
print(alist)
[34, 82, 66, 14, 56, 80, 9, 44, 69, 21]
[34, 66, 82, 14, 56, 80, 9, 44, 69, 21]
[14, 34, 66, 82, 56, 80, 9, 44, 69, 21]
[14, 34, 56, 66, 82, 80, 9, 44, 69, 21]
[14, 34, 56, 66, 80, 82, 9, 44, 69, 21]
[9, 14, 34, 56, 66, 80, 82, 44, 69, 21]
[9, 14, 34, 44, 56, 66, 80, 82, 69, 21]
[9, 14, 34, 44, 56, 66, 69, 80, 82, 21]
[9, 14, 21, 34, 44, 56, 66, 69, 80, 82]
谢尔排序
- 按照间隔划分子列表，分别插入排序后，整体更加接近有序。
- 间隔越来越小，最后间隔为1时进行的插入排序，复杂度和对无序进行插入排序完全不同。
- 复杂度为o(n^1.5)
def shellsort(alist):
mid = len(alist)//2 # 初始间隔为n/2
while mid>0:
for i in range(mid):
gapsort(alist,i,mid)
print(mid,alist)
mid = mid//2 # 间隔缩小一半
def gapsort(alist,start,gap):
for i in range(start+gap,len(alist),gap): # 按照间隔提取子列
current = alist[i]
j=i
while j>=gap and alist[j-gap]>current:
alist[j]=alist[j-gap]
j=j-gap
alist[j]=current
alist = [34,5,82,0,66,-2,14,56,80,9,23,87,100,42,33,51,44,69,21]
shellsort(alist)
9 [9, 5, 82, 0, 42, -2, 14, 44, 69, 21, 23, 87, 100, 66, 33, 51, 56, 80, 34]
4 [9, -2, 14, 0, 42, 5, 23, 44, 56, 21, 33, 51, 69, 66, 34, 87, 100, 80, 82]
2 [9, -2, 14, 0, 23, 5, 33, 21, 34, 44, 42, 51, 56, 66, 69, 80, 82, 87, 100]
1 [-2, 0, 5, 9, 14, 21, 23, 33, 34, 42, 44, 51, 56, 66, 69, 80, 82, 87, 100]
归并排序
from IPython.display import Image
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Image(filename = 'Desktop/快乐研一/python/guibin.jpg', width=400, height=400)
def mergesort(alist):
# 结束条件：
if len(alist)<=1: return alist
# 划分两半
mid = len(alist)//2
left = mergesort(alist[:mid]) # 递归调用
right = mergesort(alist[mid:])
# 如何合并？
merged = []
while left and right: # 如果两边都有数据
if left[0]<=right[0]: merged.append(left.pop(0)) # 从前往后一次对比大小
else: merged.append(right.pop(0))
merged.extend(right if right else left) # 如果某一边有剩，接上
return merged
alist = [34,5,82,0,66,-2,14,56,80,9,23,87,34,100,42,33,51,44,69,21]
mergesort(alist)
[-2, 0, 5, 9, 14, 21, 23, 33, 34, 34, 42, 44, 51, 56, 66, 69, 80, 82, 87, 100]
快速排序
def fastsort(alist):
# 结束条件
if len(alist)<=1: return alist
# 按照第一个数字作为对比中间值，设置左右两个mark分别对比，交换
leftmark = 1
rightmark = len(alist)-1
while leftmark<rightmark: # 左标向右移动，右标向左移动， 直到错开
if alist[leftmark]>alist[0] and alist[rightmark]<alist[0]:
alist[leftmark],alist[rightmark] = alist[rightmark],alist[leftmark]
else:
if alist[leftmark]<=alist[0]: # 左标向右移动，直到遇见大于list[0]的
leftmark+=1
if alist[rightmark]>=alist[0]: # 右标向左移动，直到遇见小于list[0]的
rightmark-=1
if alist[rightmark]<alist[0]:
alist[rightmark],alist[0]=alist[0],alist[rightmark]
print(alist)
# 递归调用前后两部分
left = fastsort(alist[:rightmark])
right = fastsort(alist[rightmark:])
return left+right
alist = [90,34,5,82,0,66,-2,14,56,80,9,23,87,34,100,42,51,44,69,21]
fastsort(alist)
[69, 34, 5, 82, 0, 66, -2, 14, 56, 80, 9, 23, 87, 34, 21, 42, 51, 44, 90, 100]
[21, 34, 5, 44, 0, 66, -2, 14, 56, 51, 9, 23, 42, 34, 69, 87, 80, 82]
[-2, 9, 5, 14, 0, 21, 66, 44, 56, 51, 34, 23, 42, 34]
[-2, 9, 5, 14, 0]
[0, 5, 9, 14]
[0, 5]
[9, 14]
[21, 66, 44, 56, 51, 34, 23, 42, 34]
[34, 44, 56, 51, 34, 23, 42, 66]
[34, 23, 56, 51, 34, 44, 42]
[23, 34]
[42, 51, 34, 44, 56]
[34, 42, 51, 44]
[42, 51, 44]
[44, 51]
[69, 87, 80, 82]
[82, 80, 87]
[80, 82]
[90, 100]
[-2, 0, 5, 9, 14, 21, 23, 34, 34, 42, 44, 51, 56, 66, 69, 80, 82, 87, 90, 100]
练习题目：寻找list中k个最小的数，用快速排序实现
def kmin(alist,k):
if len(alist)==k:
return alist
leftmark = 1
rightmark = len(alist)-1
while leftmark<rightmark:
if alist[leftmark]>alist[0] and alist[rightmark]<alist[0]:
alist[leftmark],alist[rightmark] = alist[rightmark],alist[leftmark]
else:
if alist[leftmark]<=alist[0]: # 左标向右移动，直到遇见大于list[0]的
leftmark+=1
if alist[rightmark]>=alist[0]: # 右标向左移动，直到遇见小于list[0]的
rightmark-=1
if alist[rightmark]<alist[0]:
alist[rightmark],alist[0]=alist[0],alist[rightmark]
if rightmark>=k:
return kmin(alist[:rightmark], k)
else:
return alist[:rightmark]+kmin(alist[rightmark:], k-rightmark)
alist
kmin(alist,5)
[-2, 9, 5, 14, 0, 21, 66, 44, 56, 51, 34, 23, 42, 34, 69, 87, 80, 82, 90, 100]
[-2, 0, 5, 9, 14]
散列 Hashing
- 需要对于数据项的位置更加精准，有利于快速存储。
- 用名称key来标识槽slot，用于保存数据项。
散列函数
- 常用的散列方法——求余数，对于11求余数，结果一定是0-10~存在不同的槽里面
- 完美散列函数：把每个数据项映射到不同的槽。特点：
- 压缩性、易计算、抗修改、抗冲突
- 如MD5 SHA，python中的散列函数库：hashlib
区块链技术（分布式数据库）
- 核心问题：在没有控制中心的情况下，如果防止篡改和破坏
- 区块链由区块block组成，block由head（记录生成时间、前一个区块的散列值等）和body（记录实际数据）组成。
- 对于某个区块数据的改动，将会引起后续所有区块的变动，比如更新会比集中数据库慢很多。
比特币平均10分钟生成一个区块
散列函数的设计
- 折叠法
- 平方取中（最后都是对11求余数）
冲突解决
映射
字典dict：键值关联，能够快速查找
排序与查找
| 算法 | 复杂度 | 其他 |
|---|---|---|
| 冒泡、选择、插入 | o(n^2) | |
| 谢尔排序 | o(n)-o(n^2) | 对于插入排序的改进 |
| 归并排序 | o(nlogn) | 但需要额外存储空间 |
| 快速排序 | 最好为o(nlogn)，分裂点偏离中心时o(n^2) | 不需要额外存储空间 |
总结：需要针对数据情况（比如随机性）来判断选择哪种算法~
快速排序
## 将代码块运行结果全部输出，而不是只输出最后的，适用于全文
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
def fastsort(alist):
# 结束条件
if len(alist)<=1: return alist
# 按照第一个数字作为对比中间值，设置左右两个mark分别对比，交换
leftmark = 1
rightmark = len(alist)-1
while leftmark<rightmark: # 左标向右移动，右标向左移动， 直到错开
if alist[leftmark]>alist[0] and alist[rightmark]<alist[0]:
alist[leftmark],alist[rightmark] = alist[rightmark],alist[leftmark]
else:
if alist[leftmark]<=alist[0]: # 左标向右移动，直到遇见大于list[0]的
leftmark+=1
if alist[rightmark]>=alist[0]: # 右标向左移动，直到遇见小于list[0]的
rightmark-=1
if alist[rightmark]<alist[0]:
alist[rightmark],alist[0]=alist[0],alist[rightmark]
print(alist)
# 递归调用前后两部分
left = fastsort(alist[:rightmark])
right = fastsort(alist[rightmark:])
return left+right
alist = [90,34,5,82,0,66,-2,14,56,80,9,23,87,34,100,42,51,44,69,21]
fastsort(alist)
[69, 34, 5, 82, 0, 66, -2, 14, 56, 80, 9, 23, 87, 34, 21, 42, 51, 44, 90, 100]
[21, 34, 5, 44, 0, 66, -2, 14, 56, 51, 9, 23, 42, 34, 69, 87, 80, 82]
[-2, 9, 5, 14, 0, 21, 66, 44, 56, 51, 34, 23, 42, 34]
[-2, 9, 5, 14, 0]
[0, 5, 9, 14]
[0, 5]
[9, 14]
[21, 66, 44, 56, 51, 34, 23, 42, 34]
[34, 44, 56, 51, 34, 23, 42, 66]
[34, 23, 56, 51, 34, 44, 42]
[23, 34]
[42, 51, 34, 44, 56]
[34, 42, 51, 44]
[42, 51, 44]
[44, 51]
[69, 87, 80, 82]
[82, 80, 87]
[80, 82]
[90, 100]
[-2, 0, 5, 9, 14, 21, 23, 34, 34, 42, 44, 51, 56, 66, 69, 80, 82, 87, 90, 100]
####练习题目：
#寻找list中k个最小的数，用快速排序实现
def kmin(alist,k):
if len(alist)==k:
return alist
leftmark = 1
rightmark = len(alist)-1
while leftmark<rightmark:
if alist[leftmark]>alist[0] and alist[rightmark]<alist[0]:
alist[leftmark],alist[rightmark] = alist[rightmark],alist[leftmark]
else:
if alist[leftmark]<=alist[0]: # 左标向右移动，直到遇见大于list[0]的
leftmark+=1
if alist[rightmark]>=alist[0]: # 右标向左移动，直到遇见小于list[0]的
rightmark-=1
if alist[rightmark]<alist[0]:
alist[rightmark],alist[0]=alist[0],alist[rightmark]
if rightmark>=k:
return kmin(alist[:rightmark], k)
else:
return alist[:rightmark]+kmin(alist[rightmark:], k-rightmark)
alist = [90,34,5,82,0,66,-2,14,56,80,9,23,87,34,100,42,51,44,69,21]
alist
kmin(alist,5)
[90, 34, 5, 82, 0, 66, -2, 14, 56, 80, 9, 23, 87, 34, 100, 42, 51, 44, 69, 21]
[-2, 9, 5, 14, 0]