1.排序
- 冒泡
- 选择
- 插入
- 二分插入
- 希尔
- 堆排序
- 快速排序
- 归并
- 桶排序
- 计数排序
- 基数排序
from tools import timer,num_timer,Time
def bubblesort(a):
n=len(a)
for i in range(n):
for j in range(i+1,n):
if a[j]>a[i]:
a[i],a[j]=a[j],a[i]
return a
def selectionsort(a):
n=len(a)
for i in range(n):
small=i
for j in range(i+1,n):
if a[small]>a[j]:
small=j
if i!=small:
a[i],a[small]=a[small],a[i]
return a
def insertsort(a):
n=len(a)
for i in range(n):
k=i
v=a[i]
while k>0 and a[k-1]>v:
a[k]=a[k-1]
k-=1
a[k]=v
return a
def quicksort(a):
def _quicksort(a):
if len(a)<=1:
return a
n=a.pop()
less=[]
more=[]
for i in range(len(a)):
if a[i]<=n:
less.append(a[i])
else:more.append(a[i])
return _quicksort(less)+[n]+_quicksort(more)
return _quicksort(a)
def mergesort(a):
def merge(la,lb):
if len(la)>len(lb):
la,lb=lb,la
n=len(la)
m=len(lb)
res=[]
i=j=0
while i<n and j<m:
if la[i]<lb[j]:
res.append(la[i])
i+=1
else:
res.append(lb[j])
j+=1
if i==n:
res.extend(lb[j:])
else:
res.extend(la[i:])
return res
def _mergesort(a):
hi=len(a)
if hi<=1:
return a
lo=0
mid=(hi+lo)//2
fl=_mergesort(a[:mid])
el=_mergesort(a[mid:])
return merge(fl,el)
return _mergesort(a)
def insertSort(nums):
'''
每步将一个待排序的记录，
按其关键码值的大小插入前面已经排序的数组中适当位置上，
直到全部插入完为止。
:param nums:
:return: nums
'''
for i in range(len(nums)):
for j in range(0,i):
if nums[i]<nums[j]:
nums[i],nums[j] = nums[j],nums[i]
return nums
def bubbleSort(nums):
'''
:param nums:
:return:
'''
for i in range(len(nums)):
for j in range(i,len(nums)):
if nums[i]>nums[j]:
nums[i],nums[j] = nums[j],nums[i]
return nums
def binarySearch(nums,item):
'''
:param nums:
:param item:
:return:
'''
low = 0
high = len(nums) - 1
while low <= high:
mid = (low+high)//2
if nums[mid]==item:
return True
elif nums[mid]<item:
low = mid + 1
else:
high = mid - 1
return False
def mergeSort(nums):
def _merge(nums1,nums2):
'''
:param nums1:
:param nums2:
:return:
'''
res = []
len1 = len(nums1)
len2 = len(nums2)
i = j = 0
while i<len1 and j<len2:
if nums1[i]<=nums2[j]:
res.append(nums1[i])
i += 1
else:
res.append(nums2[j])
j += 1
if len(nums1)==i:
res.extend(nums2[j:])
else:
res.extend(nums1[i:])
return res
if len(nums)<=1:
return nums
mid = len(nums)//2
low = mergeSort(nums[:mid])
high = mergeSort(nums[mid:])
return _merge(low,high)
def selectSort(nums):
'''
它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，
存放在序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，
然后放到已排序序列的末尾。
以此类推，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
:param nums:
:return:
'''
for i in range(len(nums)):
min = i
for j in range(i+1,len(nums)):
if nums[min]>nums[j]:
min = j
if min!=i:
nums[min],nums[i] = nums[i],nums[min]
return nums
def quickSort(nums,left,right):
'''
:param nums: 数组
:param left: 下标
:param right: 上标
:return: none
'''
if left>right:return
i,j = left,right
tmp = nums[left]
while i!=j:
while nums[j]>=tmp and i<j:
j-=1
while nums[i]<=tmp and i<j:
i+=1
if i<j:
nums[i],nums[j] = nums[j],nums[i]
nums[left],nums[i] = nums[i],tmp
quickSort(nums,left,i-1)
quickSort(nums,i+1,right)
def shellSort(arr):
'''
是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），
是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
:param arr:
:return:
'''
n = len(arr)
h = 1
while h<n/3:
h = 3*h + 1
while h >= 1:
for i in range(h,n):
j = i
while j >= h and arr[j] < arr[j-h]:
arr[j],arr[j-h] = arr[j-h],arr[j]
j -= h
h = h//3
def binaryInsertSort(arr):
'''
折半插入排序又称二分法插入排序，是插入排序的一种，其基本思想是：设在数据表中有一个元素序列V[0]，V[1]，…，V[n-1]。
其中V[0]，V[1]，…，V[i-1]是已经排好序的元素。在插入V[i]时，利用折半搜索方法寻找V[i]的位置。
:param arr:
:return:
'''
for i in range(1, len(arr)):
tmp = arr[i]
low, high = 0, i - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] >= tmp:
high = mid - 1
else:
low = mid + 1
j = i - 1
while j >= low - 1:
arr[j + 1] = arr[j]
j -= 1
arr[low] = tmp
return arr
def heapSort(arr):
'''
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆是一个近似完全二叉树的结构，并同时满足堆积的性质：
即子结点的键值或索引总是小于（或者大于）它的父节点。
:param arr:
:return:
'''
def bigEndian(arr,start,end):
root = start
while True:
child = root*2+1
if child>end:
break
if child+1 <= end and arr[child]<arr[child+1]:
child+=1
if arr[root]<arr[child]:
arr[root],arr[child] = arr[child],arr[root]
root=child
else:
break
first = len(arr)//2 - 1
for i in range(first,-1,-1):
bigEndian(arr,i,len(arr)-1)
for j in range(len(arr)-1,0,-1):
arr[0],arr[j] = arr[j],arr[0]
bigEndian(arr,0,j-1)
a=[1,2,4,1,1,2,34,56,7,1]
bubbleSort(a)
print(a)
2.查找
- 二分查找
def binary_search(s,a):
low = 0
high = len(s) - 1
while low<=high :
mid = (low + high) // 2
print('low:{} high:{} mid:{},s:{}'.format(low,high,mid,s[mid]))
if s[mid] == a:
return True
if s[mid] < a:
low = mid + 1
else:
high = mid - 1
return False
3.数据结构
- 优先级队列
- 链表
- 队列
- 堆栈
- map
class priorityQueue:
'''
[(1,A),(2,D)]
'''
def __init__(self):
self.data = []
def add(self,item):
if len(self.data)==0:
self.data.append(item)
return
for k,v in enumerate(self.data):
if v[0]>=item[0]:
break
else:
k += 1
self.data.insert(k,item)