什么是算法？
算法：一个计算过程，解决问题的方法
一个大牛曾说过：程序=数据结构+算法
递归的两个特点：
调用自身
结束条件
下面两个的不同：
# def func3(x): # if x>0: # print(x) # func3(x-1) # func3(5)这个打印的结果是54321 def func4(x): if x > 0: func4(x - 1) print(x) func4(5)#这个打印的结果是12345
我们来看代码运行的时间复杂度和空间复杂度：
时间复杂度：
print('Hello World!')#这个时间的复杂度是o(1)
for i in range(n):
print('Hello World') #z这个时间的复杂度是o(n)
for i in range(n):
for j in range(n):
print('Hello World!')#这个时间的复杂度是o(n2)
while n>1:
print(n)
n=n//2 #这个时间的复杂度是O(logn)
时间复杂度小结：
时间复杂度是用来估计算法运行时间的一个式子(单位)。
一般来说，时间复杂度高的算法比复杂度低的算法慢。
常见的时间复杂度(按效率排序)：
如何一眼判断时间复杂度？
循环减半的过程就是O(logn)
几次循环就是n的几次方复杂度。
空间复杂度：
它是用来评估算法内存占用大小的一个式子
递归查找的二分法：
def linear_search(data_set,value):#时间复杂度是O(n) for i in range(range(data_set)): if data_set[i]==value: return i return def bin_search(data_set,value):#时间复杂度是O(logn) low=0 high=len(data_set)-1 while low<=high: mid=(low+high)//2 if data_set[mid]==value: return mid elif data_set[mid]>value: high=mid-1 else: low=mid+1
递归版的二分查找：
def bin_search_rec(data_set,value,low,high): if low <= high: mid=(low+high)//2 if data_set[mid]==value: return mid elif data_set[mid]>value: return bin_search_rec(data_set,value,low,mid-1) else: return bin_search_rec(data_set,value,mid+1,high) else: return li=[55,66,77,88,99,100,200,600,500] s=bin_search_rec(li,100,0,len(li)-1) print(s)
排序模块：
排序届lowB三人组：
冒泡排序
import random def bubble_sort_2(li):#时间复杂度是O(n*2) for i in range(len(li) - 1): # i 表示趟数 # 第 i 趟时： 无序区：(0，len(li) - i) change = False for j in range(0, len(li) - i - 1): if li[j] > li[j+1]: li[j], li[j+1] = li[j+1], li[j] change = True if not change: return li = list(range(10000))#生成一个列表 random.shuffle(li)#打乱列表 print(li) bubble_sort_2(li)#冒泡排序 print(li)
选择排序
import random def select_sort(li): for i in range(len(li) - 1): # i 表示趟数，也表示无序区开始的位置 min_loc = i # 最小数的位置 for j in range(i + 1, len(li)): if li[j] < li[min_loc]: min_loc = j li[i], li[min_loc] = li[min_loc], li[i] li = list(range(10)) random.shuffle(li) print(li) select_sort(li) print(li)
插入排序
import random def insert_sort(li): for i in range(1, len(li)): # i 表示无序区第一个数 tmp = li[i] # 摸到的牌 j = i - 1 # j 指向有序区最后位置 while li[j] > tmp and j >= 0: #循环终止条件： 1. li[j] <= tmp; 2. j == -1 li[j+1] = li[j] j -= 1 li[j+1] = tmp li = list(range(10)) random.shuffle(li) print(li) insert_sort(li) print(li)
NB排序方法：
import time def cal_time(func): def wrapper(*args, **kwargs): t1 = time.time() result = func(*args, **kwargs) t2 = time.time() print("%s running time: %s secs." % (func.__name__, t2-t1)) return result return wrapper
快排
# def partition(li, left, right): # temp = li[left] # while left < right: # while left < right and li[right] >= temp: # right -= 1 # li[left] = li[right] # while left < right and li[left] <= temp: # left += 1 # li[right] = li[left] # # li[left] = temp # return left # def partition(li, left, right): # # ri = random.randint(left, right) # # li[left], li[ri] = li[ri], li[left] # tmp = li[left] # while left < right: # while left < right and li[right] >= tmp: # right -= 1 # li[left] = li[right] # while left < right and li[left] <= tmp: # left += 1 # li[right] = li[left] # li[left] = tmp # return left # def quick_sort(li, left, right): # if left < right: # mid = partition(li, left, right) # # quick_sort(li, left, mid - 1) # # quick_sort(li, mid + 1, right) # # # li = list(range(100)) # li.reverse() # print(li) # quick_sort(li, 0, len(li) - 1) # print(li) import random from timewrap import * import copy import sys sys.setrecursionlimit(100000) # 设置最大递归深度 def partition(li, left, right): ri = random.randint(left, right) # 加上这个是为了防止最坏的情况出现 li[left], li[ri] = li[ri], li[left] tmp = li[left] while left < right: while left < right and li[right] >= tmp: right -= 1 li[left] = li[right] while left < right and li[left] <= tmp: left += 1 li[right] = li[left] li[left] = tmp return left # 返回归并的的索引 def _quick_sort(li, left, right): if left < right: # 至少有两个元素 mid = partition(li, left, right) _quick_sort(li, left, mid - 1) _quick_sort(li, mid + 1, right) @cal_time def quick_sort(li): return _quick_sort(li, 0, len(li) - 1) @cal_time def sys_sort(li): li.sort() li = list(range(100000)) random.shuffle(li)#这是打乱列表的顺序 li.reverse() li1 = copy.deepcopy(li) li2 = copy.deepcopy(li) sys_sort(li1) # 0.17502140998840332 secs.系统使用C写的比较快 quick_sort(li2) # quick_sort running time: 0.0004992485046386719 secs. # print(li)
堆排序：
from timewrap import * import random def _sift(li, low, high): """ :param li: :param low: 堆根节点的位置 :param high: 堆最后一个节点的位置 :return: """ i = low # 父亲的位置 j = 2 * i + 1 # 孩子的位置 tmp = li[low] # 原省长 while j <= high: if j + 1 <= high and li[j + 1] > li[j]: # 如果右孩子存在并且右孩子更大 j += 1 if tmp < li[j]: # 如果原省长比孩子小 li[i] = li[j] # 把孩子向上移动一层 i = j j = 2 * i + 1 else: li[i] = tmp # 省长放到对应的位置上(干部) break else: li[i] = tmp # 省长放到对应的位置上(村民/叶子节点) def sift(li, low, high): """ :param li: :param low: 堆根节点的位置 :param high: 堆最有一个节点的位置 :return: """ i = low # 父亲的位置 j = 2 * i + 1 # 孩子的位置 tmp = li[low] # 原省长 while j <= high: if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在并且右孩子更大 j += 1 if tmp < li[j]: # 如果原省长比孩子小 li[i] = li[j] # 把孩子向上移动一层 i = j j = 2 * i + 1 else: break li[i] = tmp @cal_time def heap_sort(li): n = len(li) # 1. 建堆 for i in range(n//2-1, -1, -1): sift(li, i, n-1) # 2. 挨个出数 for j in range(n-1, -1, -1): # j表示堆最后一个元素的位置 li[0], li[j] = li[j], li[0] # 堆的大小少了一个元素 （j-1） sift(li, 0, j-1) li = list(range(10000)) random.shuffle(li) heap_sort(li) print(li) # li=[2,9,7,8,5,0,1,6,4,3] # sift(li, 0, len(li)-1) # print(li)
归并排序
import random from timewrap import * import copy import sys def merge(li, low, mid, high): i = low j = mid + 1 ltmp = [] while i <= mid and j <= high: if li[i] < li[j]: ltmp.append(li[i]) i += 1 else: ltmp.append(li[j]) j += 1 while i <= mid: ltmp.append(li[i]) i += 1 while j <= high: ltmp.append(li[j]) j += 1 li[low:high+1] = ltmp def _merge_sort(li, low, high): if low < high: # 至少两个元素 mid = (low + high) // 2 _merge_sort(li, low, mid) _merge_sort(li, mid+1, high) merge(li, low, mid, high) # print(li[low:high+1]) def merge_sort(li): return _merge_sort(li, 0, len(li)-1) li = list(range(16)) random.shuffle(li) print(li) # li=[10,8,11,7] # merge_sort(li) # # print(li)
NB算法的时间复杂度都是O(nlongn):
一般情况下：就运行时间而言：
快速排序<归并排序<堆排序
三种排序算法的缺点：
快速排序：极端情况下排序效率低
归并排序：需要额外的内存开销
堆排序：在快的排序算法中相对较慢