个数 search not range clas war 中间 n-1 ice
查找方法 : 顺序查找法 二分查找法
- import time,random
- #时间计算
- def cal_time(func):
- def wrapper(*args,**kwargs):
- time1=time.time()
- n=func(*args,**kwargs)
- time2=time.time()
- print(func.__name__,‘times:‘,time2-time1)
- return n
- return wrapper
- #顺序查找法
- @cal_time
- def linear_search(data_set,val):
- for i in range(range(data_set)):
- if data_set[i]==val:
- return i
- return
- #二分查找法
- @cal_time
- def bin_search(data_set,val,*args,**kwargs):#二分查找
- low=0 #最小下标
- high=len(data_set)-1 #最大下标
- while low <= high: #当最小下标小于或等于最大下标时 进行调用
- mid =(low+high)//2 # 二分计算
- if data_set[mid]==val: #如果中间值等于要查找的值,
- return mid #返回中间下标
- elif data_set[mid]>val: #如果大于中间值
- high=mid-1 #最大下标移到中间值之前一个位置
- else:
- low=mid+1 #最小下标移到中间值之后一个位置
- return
- #@cal_time
- def bin_search_dic(data_set,val):#二分查找 字典
- low=0 #最小下标
- high=len(data_set)-1 #最大下标
- while low <= high: #当最小下标小于或等于最大下标时 进行调用
- mid =(low+high)//2 # 二分计算
- if data_set[mid][‘id‘]==val: #如果中间值等于要查找的值,
- return mid #返回中间下标
- elif data_set[mid][‘id‘]>val: #如果大于中间值
- high=mid-1 #最大下标移到中间值之前一个位置
- else:
- low=mid+1 #最小下标移到中间值之后一个位置
- return
- @cal_time
- def bin_search_dic_two(data_set,val):
- return bin_search(data_set,val)
- #字典生成
- @cal_time
- def random_list(n):
- result=[]#空列表
- ids=list(range(1001,1001+n))#id的列表
- a1=[‘Y‘,‘L‘,‘D‘,‘I‘,‘P‘]
- a2=[‘t‘,‘s‘,‘‘,‘‘,‘e‘,‘o‘]
- a3=[‘s‘,‘n‘,‘x‘,‘r‘]
- for i in range(n):
- temp={}
- id=ids[i] #id有序
- age = random.randint(18,60)#随机生成 18到60之间
- name=random.choice(a1)+random.choice(a2)+random.choice(a3)
- temp={‘id‘:id,‘age‘:age,‘name‘:name}
- result.append(temp)
- return result
- data=list(range(10000000))
- bin_search(data,500)
- name_list=random_list(9)
- #print(name_list)
- dics=bin_search_dic(name_list,1004)
- #print(name_list[dics])
排序的多种算法:
- #冒泡排序
- @cal_time
- def bubble_sort(list):
- for i in range(len(list)-1): #下标
- for j in range(len(list)-i -1):#排序后,下一趟的下标
- if list[j]>list[j+1]: #大于 升序
- list[j],list[j+1]=list[j+1],list[j] #进行交换
- @cal_time
- def bubble_sort_p(list):#冒泡排序 优化
- for i in range(len(list)-1): #下标
- tag=False #交换标志
- for j in range(len(list)-i -1):
- if list[j]>list[j+1]: #大于 升序
- list[j],list[j+1]=list[j+1],list[j] #进行交换
- tag=True
- if not tag:#如果没有产生交换
- break #直接退出
- #选择排序
- def select_sort(li):#选择排序
- for i in range(len(li)-1):#n-1趟
- tag=False #交换标志
- min_loc=i #默认第一个为最小值的下标
- for j in range(i+1,len(li)):
- if li[j]< li[min_loc]:#如果当前下标值小于第一个下标,
- min_loc=j #最小值的下标位置进行更新下标
- tag=True
- if not tag:#如果没有产生交换
- break #直接退出
- else:
- li[i],li[min_loc]=li[min_loc],li[i] #进行对换
- #插入排序
- def insert(li,i):
- tmp=li[i]#取出当前值
- j=i-1 #对比的值的下标 向左对比
- while j>=0 and li[j]> tmp:#对比的下标不为负 ,对比的值大于取出的值,
- li[j+1]=li[j] #进行对换
- j=j-1 #下标左移
- li[j+1]=tmp #对比值比较小的右边 放入取出的值
- #插入排序
- @cal_time
- def insert_sort(li):
- for i in range(1,len(li)):# 当前下标
- insert(li,i)#单次排序
- #快排
- #递归 归位
- def partition(data,left,right):
- tmp =data[left]# 从左边取数
- while left <right: #左右下标不相碰
- while left <right and data[right]>= tmp: #右边的值 大于取出的值时
- right-=1 #右边下标左移一位
- data[left]=data[right]#找到右边小于取出值 ,移到左边空位
- while left < right and data[left] <=tmp:#左边的值 小于取出的值时
- left +=1 #左边右移一位
- data[right]=data[left]#找到左边大于取出值 ,移到右边空位
- data[left]=tmp #当左右下标相遇 取出值 放入空位
- return left #返回左下标
- #快排
- def quick_sort(data,left,right):
- if left <right:
- mid =partition(data,left,right)#进行递归调整
- quick_sort(data,left,mid-1)
- quick_sort(data,mid+1,right)
- 堆排
- #堆排 将堆调整
- def sift_q(data,low,high):
- i= low #根 下标
- j=2*i+1 #对应的 左子节点 下标
- tmp =data[i] #取根下标值
- while j<=high: #如果左节点下标小于等于最大下标
- if j <high and data[j]<data[j+1]: #如果左下标小在最大下标,并且,左了节点的数值小于 右子节点的数值
- j+=1 #下标右移一位
- if tmp < data[j]:#如果根节点的值小于,左子节点
- data[i]=data[j] # 左子节点值,移到根节点
- i=j #根下标 下移到原来的左子节点
- j=2*i+1#对应的 左子节点 下标
- else:
- break
- data[i]=tmp #最后空位,放入取出的值
- #堆排序 升序
- @cal_time
- def sift(data):
- n=len(data)
- for i in range(n//2-1,-1,-1): #最后的父节点, 步长, 最后
- sift_q(data,i,n-1)#进行调整
- for i in range(n-1,-1,-1):# i指向堆的最后下标
- data[0],data[i] =data[i],data[0]# 最大值 放到堆的最后下标,最后下标的值调整到最高位置
- sift_q(data,0,i-1)#调整出 除了最后下标 堆调整 排序完成
- #堆排序 降序
- @cal_time
- def sift_r(data):
- n=len(data)
- for i in range(n//2-1,-1,-1): #最后的父节点, 步长, 最前面
- sift_q(data,i,n-1)#进行调整
- list=[]
- for i in range(n-1,-1,-1):# i指向堆的最后下标
- list.append(data[0])#加入列表
- data[0]=data[i]#最后下标的值调整到最高位置
- sift_q(data,0,i-1)#调整出 除了最后下标 堆调整 排序完成i
- data[0:n]=list
- #归并排序
- #归并排序 合并
- def merge(list,low,mid,high):#列表,最左下标,中间下标,最右下标
- i=low #左边指向下标
- j=mid+1 #右边指向下标
- ltmp=[]#临时列表
- while i<=mid and j<=high:#两边都还有数时
- if list[i]<list[j]:
- ltmp.append(list[i])#添加到临时列表
- i+=1 #左边指向下标右移
- else:
- ltmp.append(list[j])#添加到临时列表
- j+=1#右边指向下标右移
- while i<=mid:#如果左边还有数时
- ltmp.append(list[i])
- i+=1
- while j<=high:#如果右边还有数时
- ltmp.append(list[j])
- j+=1
- list[low:high+1]=ltmp #写回原的列表
- #归并排序
- def mergesort_q(li,low,high):
- if low<high:
- mid=(low+high)//2 #取中间值
- mergesort_q(li,low,mid) #左边分解
- mergesort_q(li,mid+1,high) #右边分解
- merge(li,low,mid,high)#归并排序
- @cal_time
- def mergesort(data):
- return mergesort_q(data,0,len(data)-1)
#希尔排序
def _shell_sort(li): gap =len(li)//2 #分组的数 while gap>=1: for i in range(gap,len(li)): #分组对比 tmp=li[i]#取出要对比的数 j=i-gap #前一组的对比数 下标 while j>=0 and tmp< li[j]: #如果前一组有数, 并且大于后一组, li[j+gap]=li[j] #进行,前一组位置的值换到后一组 j-=gap #下标向左移一组 li[i-gap]=tmp # 对比的数,换到前一组 gap =gap//2 #分组减半 @cal_time def shell_sort(li): return _shell_sort(li)
#计数排序只能用于数字排序且是数字的一定范围内
def _count_sort(li,max_num): count=[0 for i in range(max_num+1)]#开一个列表 数字的范围内的 for num in li:#如果数字在数列中 count[num]+=1 #计数加1 i=0 for num ,m in enumerate(count):#下标与数值 for j in range(m): #输出到原来的列表中 li[i]=num # i+=1 #下标右移 @cal_time def count_sort(li): return _count_sort(li,len(li)-1)
#TOP排行
#TOP排行 def topk(li,k): ltmp=li[0:k+1]#取top数 多一位 insert_sort(ltmp)#插入排序 for i in range(k+1,len(li)):# 从取数的后一位开始 ltmp[k]=li[i] #列表最后 改为下一个数 tmp=ltmp[k] #临时值 j=k-1 #下标左移 while j>=0 and ltmp[j] >tmp:#判断 ltmp[j+1]=ltmp[j]# 数值 右移 j-=1 #左移一位下标 ltmp[j+1]=tmp #插入位置 return ltmp[0:k]# 返回所需的列表 #TOP排行 def topk_2(li,k): ltmp=li[0:k+1]#取top数 多一位 insert_sort(ltmp)#插入排序 for i in range(k+1,len(li)):# 从取数的后一位开始 ltmp[k]=li[i]#列表最后 改为下一个数 insert(ltmp,k) return ltmp[:-1]# 返回所需的列表
#堆top
#堆top def topn(li,n): heap=li[0:n]#取top数 for i in range(n//2-1,-1,-1):#建堆,小根堆 sift_q(heap,i,n-1)#调整 #进行遍历 for i in range(n,len(li)): if li[i] < heap[0]: #如果取来对比的数比根的小 heap[0] =li[i]#进行替换 sift_q(heap,0,n-1)#调整 for i in range(n-1,-1,-1): heap[0],heap[i] =heap[i],heap[0]# 最大值 放到堆的最后下标,最后下标的值调整到最高位置 sift_q(heap,0,i-1)#调整出 除了最后下标 堆调整 排序完成 return heap
data =list(range(100))#生成列表 random.shuffle(data)#打乱
python 第二百零八天 ----算法相关
个数 search not range clas war 中间 n-1 ice
原文:http://www.cnblogs.com/uge3/p/7928752.html
来源: http://www.bubuko.com/infodetail-2412450.html