python 第二百零八天 ----算法相关

2018-06-17 23:41:14来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

查找方法   :    顺序查找法     二分查找法

 1 import time,random
 2 
 3 #时间计算
 4 def cal_time(func):
 5     def wrapper(*args,**kwargs):
 6         time1=time.time()
 7         n=func(*args,**kwargs)
 8         time2=time.time()
 9         print(func.__name__,'times:',time2-time1)
10         return n
11     return wrapper
12 
13 #顺序查找法
14 @cal_time
15 def linear_search(data_set,val):
16     for i in range(range(data_set)):
17         if data_set[i]==val:
18             return i
19     return
20 
21 
22 #二分查找法
23 @cal_time
24 def bin_search(data_set,val,*args,**kwargs):#二分查找
25     low=0   #最小下标
26     high=len(data_set)-1    #最大下标
27     while low <= high:  #当最小下标小于或等于最大下标时 进行调用
28         mid =(low+high)//2  # 二分计算
29         if data_set[mid]==val:  #如果中间值等于要查找的值,
30             return mid  #返回中间下标
31         elif data_set[mid]>val: #如果大于中间值
32             high=mid-1  #最大下标移到中间值之前一个位置
33         else:
34             low=mid+1   #最小下标移到中间值之后一个位置
35     return
36 
37 #@cal_time
38 def bin_search_dic(data_set,val):#二分查找 字典
39     low=0   #最小下标
40     high=len(data_set)-1    #最大下标
41     while low <= high:  #当最小下标小于或等于最大下标时 进行调用
42         mid =(low+high)//2  # 二分计算
43         if data_set[mid]['id']==val:  #如果中间值等于要查找的值,
44             return mid  #返回中间下标
45         elif data_set[mid]['id']>val: #如果大于中间值
46             high=mid-1  #最大下标移到中间值之前一个位置
47         else:
48             low=mid+1   #最小下标移到中间值之后一个位置
49     return
50 
51 
52 @cal_time
53 def bin_search_dic_two(data_set,val):
54     return bin_search(data_set,val)
55 #字典生成
56 @cal_time
57 def random_list(n):
58     result=[]#空列表
59     ids=list(range(1001,1001+n))#id的列表
60     a1=['Y','L','D','I','P']
61     a2=['t','s','','','e','o']
62     a3=['s','n','x','r']
63     for i in range(n):
64         temp={}
65         id=ids[i] #id有序
66         age = random.randint(18,60)#随机生成 18到60之间
67         name=random.choice(a1)+random.choice(a2)+random.choice(a3)
68         temp={'id':id,'age':age,'name':name}
69         result.append(temp)
70     return result
71 
72 
73 data=list(range(10000000))
74 bin_search(data,500)
75 name_list=random_list(9)
76 #print(name_list)
77 dics=bin_search_dic(name_list,1004)
78 #print(name_list[dics])
View Code

 

排序的多种算法:   

#冒泡排序

 1 @cal_time
 2 def bubble_sort(list):
 3     for i in range(len(list)-1): #下标
 4         for j in range(len(list)-i -1):#排序后,下一趟的下标
 5             if list[j]>list[j+1]: #大于 升序
 6                 list[j],list[j+1]=list[j+1],list[j]  #进行交换
 7 
 8 @cal_time
 9 def bubble_sort_p(list):#冒泡排序 优化
10     for i in range(len(list)-1): #下标
11         tag=False  #交换标志
12         for j in range(len(list)-i -1):
13             if list[j]>list[j+1]: #大于 升序
14                 list[j],list[j+1]=list[j+1],list[j]  #进行交换
15                 tag=True
16         if not tag:#如果没有产生交换
17             break #直接退出

 

#选择排序

 1 def select_sort(li):#选择排序
 2     for i in range(len(li)-1):#n-1趟
 3         tag=False  #交换标志
 4         min_loc=i #默认第一个为最小值的下标
 5         for j in range(i+1,len(li)):
 6             if li[j]< li[min_loc]:#如果当前下标值小于第一个下标,
 7                 min_loc=j  #最小值的下标位置进行更新下标
 8                 tag=True
 9         if not tag:#如果没有产生交换
10             break #直接退出
11         else:
12             li[i],li[min_loc]=li[min_loc],li[i] #进行对换

 

#插入排序

 1 def insert(li,i):
 2     tmp=li[i]#取出当前值
 3     j=i-1 #对比的值的下标 向左对比
 4     while j>=0 and li[j]> tmp:#对比的下标不为负 ,对比的值大于取出的值,
 5         li[j+1]=li[j] #进行对换
 6         j=j-1 #下标左移
 7     li[j+1]=tmp #对比值比较小的右边 放入取出的值
 8 
 9 #插入排序
10 @cal_time
11 def insert_sort(li):
12     for i in range(1,len(li)):# 当前下标
13         insert(li,i)#单次排序

 

#快排
 1 #递归 归位
 2 def partition(data,left,right):
 3     tmp =data[left]# 从左边取数
 4     while left <right: #左右下标不相碰
 5         while left <right and data[right]>= tmp: #右边的值 大于取出的值时
 6             right-=1 #右边下标左移一位
 7         data[left]=data[right]#找到右边小于取出值 ,移到左边空位
 8         while left < right and data[left] <=tmp:#左边的值 小于取出的值时
 9             left +=1 #左边右移一位
10         data[right]=data[left]#找到左边大于取出值 ,移到右边空位
11     data[left]=tmp #当左右下标相遇 取出值 放入空位
12     return  left #返回左下标
13 
14 #快排
15 def quick_sort(data,left,right):
16     if left <right:
17         mid =partition(data,left,right)#进行递归调整
18         quick_sort(data,left,mid-1)
19         quick_sort(data,mid+1,right)
堆排
 1 #堆排 将堆调整
 2 def sift_q(data,low,high):
 3     i= low #根  下标
 4     j=2*i+1  #对应的 左子节点 下标
 5     tmp =data[i] #取根下标值
 6     while j<=high: #如果左节点下标小于等于最大下标
 7         if  j <high and data[j]<data[j+1]: #如果左下标小在最大下标,并且,左了节点的数值小于 右子节点的数值
 8             j+=1 #下标右移一位
 9         if tmp < data[j]:#如果根节点的值小于,左子节点
10             data[i]=data[j] # 左子节点值,移到根节点
11             i=j #根下标 下移到原来的左子节点
12             j=2*i+1#对应的 左子节点 下标
13         else:
14             break
15     data[i]=tmp  #最后空位,放入取出的值
16 
17 #堆排序 升序
18 @cal_time
19 def sift(data):
20     n=len(data)
21     for i in range(n//2-1,-1,-1): #最后的父节点, 步长, 最后
22         sift_q(data,i,n-1)#进行调整
23     for i in range(n-1,-1,-1):# i指向堆的最后下标
24         data[0],data[i] =data[i],data[0]# 最大值 放到堆的最后下标,最后下标的值调整到最高位置
25         sift_q(data,0,i-1)#调整出 除了最后下标 堆调整    排序完成
26 
27 #堆排序 降序
28 @cal_time
29 def sift_r(data):
30     n=len(data)
31     for i in range(n//2-1,-1,-1): #最后的父节点, 步长, 最前面
32         sift_q(data,i,n-1)#进行调整
33     list=[]
34     for i in range(n-1,-1,-1):# i指向堆的最后下标
35         list.append(data[0])#加入列表
36         data[0]=data[i]#最后下标的值调整到最高位置
37         sift_q(data,0,i-1)#调整出 除了最后下标 堆调整    排序完成i
38     data[0:n]=list
#归并排序

 1 #归并排序  合并
 2 def merge(list,low,mid,high):#列表,最左下标,中间下标,最右下标
 3     i=low #左边指向下标
 4     j=mid+1 #右边指向下标
 5     ltmp=[]#临时列表
 6     while i<=mid and j<=high:#两边都还有数时
 7         if list[i]<list[j]:
 8             ltmp.append(list[i])#添加到临时列表
 9             i+=1 #左边指向下标右移
10         else:
11             ltmp.append(list[j])#添加到临时列表
12             j+=1#右边指向下标右移
13     while i<=mid:#如果左边还有数时
14         ltmp.append(list[i])
15         i+=1
16     while j<=high:#如果右边还有数时
17         ltmp.append(list[j])
18         j+=1
19     list[low:high+1]=ltmp  #写回原的列表
20 
21 #归并排序
22 def mergesort_q(li,low,high):
23     if low<high:
24         mid=(low+high)//2 #取中间值
25         mergesort_q(li,low,mid) #左边分解
26         mergesort_q(li,mid+1,high) #右边分解
27         merge(li,low,mid,high)#归并排序
28 
29 @cal_time
30 def mergesort(data):
31     return mergesort_q(data,0,len(data)-1)
#希尔排序
 1 def _shell_sort(li):
 2     gap =len(li)//2 #分组的数
 3     while gap>=1:
 4         for i in range(gap,len(li)): #分组对比
 5             tmp=li[i]#取出要对比的数
 6             j=i-gap #前一组的对比数 下标
 7             while j>=0 and tmp< li[j]: #如果前一组有数, 并且大于后一组,
 8                 li[j+gap]=li[j] #进行,前一组位置的值换到后一组
 9                 j-=gap #下标向左移一组
10             li[i-gap]=tmp # 对比的数,换到前一组
11         gap =gap//2 #分组减半
12 
13 @cal_time
14 def shell_sort(li):
15     return _shell_sort(li)
#计数排序   只能用于数字排序 且是数字的一定范围内
 1 def _count_sort(li,max_num):
 2     count=[0 for i in range(max_num+1)]#开一个列表  数字的范围内的
 3     for num in li:#如果数字在数列中
 4         count[num]+=1  #计数加1
 5     i=0
 6     for num ,m in enumerate(count):#下标与数值
 7         for j in range(m): #输出到原来的列表中
 8             li[i]=num  #
 9             i+=1 #下标右移
10 
11 @cal_time
12 def count_sort(li):
13     return _count_sort(li,len(li)-1)
#TOP排行
 1 #TOP排行
 2 def topk(li,k):
 3     ltmp=li[0:k+1]#取top数 多一位
 4     insert_sort(ltmp)#插入排序
 5     for i in range(k+1,len(li)):# 从取数的后一位开始
 6         ltmp[k]=li[i] #列表最后 改为下一个数
 7         tmp=ltmp[k] #临时值
 8         j=k-1 #下标左移
 9         while j>=0 and ltmp[j] >tmp:#判断
10             ltmp[j+1]=ltmp[j]# 数值 右移
11             j-=1 #左移一位下标
12         ltmp[j+1]=tmp #插入位置
13     return ltmp[0:k]# 返回所需的列表
14 #TOP排行
15 def topk_2(li,k):
16     ltmp=li[0:k+1]#取top数 多一位
17     insert_sort(ltmp)#插入排序
18     for i in range(k+1,len(li)):# 从取数的后一位开始
19         ltmp[k]=li[i]#列表最后 改为下一个数
20         insert(ltmp,k)
21     return ltmp[:-1]# 返回所需的列表
#堆top
 1 #堆top
 2 def topn(li,n):
 3     heap=li[0:n]#取top数
 4     for i in range(n//2-1,-1,-1):#建堆,小根堆
 5         sift_q(heap,i,n-1)#调整
 6     #进行遍历
 7     for i in range(n,len(li)):
 8         if li[i] < heap[0]: #如果取来对比的数比根的小
 9             heap[0] =li[i]#进行替换
10             sift_q(heap,0,n-1)#调整
11     for i in range(n-1,-1,-1):
12         heap[0],heap[i] =heap[i],heap[0]# 最大值 放到堆的最后下标,最后下标的值调整到最高位置
13         sift_q(heap,0,i-1)#调整出 除了最后下标 堆调整    排序完成
14     return heap
1 data =list(range(100))#生成列表
2 random.shuffle(data)#打乱

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:python SyntaxError: EOL while scanning string literal

下一篇:Centos 7 安装python3.5与2.7并存