概念
算法（Algorithm）：一个计算过程，解决问题的方法
时间复杂度与空间复杂度
时间复杂度
一个算法的优劣可以用时间复杂度与空间复杂度来衡量。
通常讨论算法的复杂度：1、问题规模相同 2、机器配置相同
常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。
如何判断一个算法的时间复杂度
- 循环减半的过程>>> O(logn)
- 几次循环就是N的几次方的复杂度
常用的时间复杂度（按效率排序）
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
空间复杂度
- 用来评估算法内存占用大小的一个式子
- 算法快总要付出点代价的，利用"空间"来换取"时间"
列表查找
指定从一个列表的所有元素中，查找指定的元素
1、顺序查找（利用Python内置函数index，in操作，for循环机制都可实现）
2、二分查找（注：前提列表是有序的）
二分查找又称为半查找， 由上图定义low（最小数索引）high（最大数索引）mid（折半数索引）
需求：按照上图找到数字3
- 既然是二分，每一次循环问题规模相应的要减半。mid=（low + high） // 2
- 如果val(查找数) < mid，即在这个列表二分的左边，high = mid - 1
- 如果val(查找数) > mid，即反之，low = mid + 1
def bin_search(data_list, val): low = 0 # 最小数下标 high = len(data_list) - 1 # 最大数下标 while low <= high: mid = (low + high) // 2 # 中间数下标 if data_list[mid] == val: # 如果中间数下标等于val, 返回 return mid elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标 high = mid - 1 else: # 如果val在中间数右边, 移动low下标 low = mid + 1 return # val不存在, 返回None ret = bin_search(list(range(1, 10)), 3) print(ret)
冒泡排序
冒泡：因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
利用相邻元素比较并进行位置的互换...
需求：一个打乱的列表，进行有效的排序
相邻两个值进行比较，将较大的值放在右侧，依次比较！（排序好的便不再比较）
def bubble_sort(li): for i in range(len(li) - 1): # 无需在意最后一个数 for j in range(len(li) - i - 1): # 循环的躺数, 每一趟可以排出一个最大数 if li[j] > li[j+1]: # 如果当前数大于后面的数, 即调换位置 li[j], li[j+1] = li[j+1], li[j] li = list(range(10)) random.shuffle(li) # 打乱列表 bubble_sort(li) print(li)
def bubble_sort(li): for i in range(len(li) - 1): # 无需在意最后一个数 go = False # 设定一个标识 for j in range(len(li) - i - 1): # 循环的躺数, 每一趟可以排出一个最大数 if li[j] > li[j+1]: # 如果当前数大于后面的数, 即调换位置, 否则可能是有序的 li[j], li[j+1] = li[j+1], li[j] go = True if not go: return li = list(range(1000)) random.shuffle(li) # 打乱列表 bubble_sort(li) print(li)
选择排序
选择：
- 选择第一个值的索引赋值给特殊变量，然后循环其他索引并进行值的比较，如果循环的值 < 特殊变量对应的值，那么将当前值的索引放入变量中，继续向后比较
- 选择第二个值的索引赋值给特殊变量，...
- ...
def select_sort(li): for i in range(len(li) - 1): index = i # 选择一个数 for j in range(i+1, len(li)): # 与i+1之后的每一个数比较 if li[j] < li[index]: # 如果之后的每一个数小于标识代表的最小数 index = j # 一直在选择最小数 li[i], li[index] = li[index], li[i] # 改变位置 li = list(range(10)) random.shuffle(li) select_sort(li) print(li)
插入排序
插入：
- 列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
- 每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空
import random def insert_sort(li): for i in range(1, len(li)): # 从下标1开始 tmp = li[i] # 拿出无序区第一个数 j = i - 1 # 有序区最大数的下标 while j >= 0 and tmp < li[j]: # 条件: 下标j要大于等于0 和 拿出的数小于有序区的最大数 li[j+1] = li[j] # 下标j对应的数要往后挪动一个位置 j = j - 1 # 有序区下一个元素继续比较 li[j+1] = tmp # tmp重新到自己该到的位置 li = list(range(100)) random.shuffle(li) insert_sort(li) print(li)
快速排序
import random def insert_sort(li): for i in range(1, len(li)): # 从下标1开始 tmp = li[i] # 拿出无序区第一个数 j = i - 1 # 有序区最大数的下标 while j >= 0 and tmp < li[j]: # 条件: 下标j要大于等于0 和 拿出的数小于有序区的最大数 li[j+1] = li[j] # 下标j对应的数要往后挪动一个位置 j = j - 1 # 留出一个位置给tmp li[j+1] = tmp # tmp重新到自己该到的位置 li = list(range(100)) random.shuffle(li) insert_sort(li) print(li
快速：
- 取一个元素P（第一个元素），使元素P归位
- 列表被P分成俩部分，左边都比P小，右边都比P大
- 递归完成排序
# 降序排列 def quick_sort(li, left, right): if left < right: mid = partition(li, left, right) quick_sort(li, mid + 1, right) quick_sort(li, left, mid - 1) def partition(li, left, right): tmp = li[left] # 取出最左边的数 while left < right: # 如果 left 与 right 值相等 表示tmp找到正确下标 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 or right] = tmp # tmp到达指定位置 return left or right # 返回tmp下标 data = list(range(10)) random.shuffle(data) quick_sort(data, 0, len(data)-1) print(data)
# 升序排列 def quick_sort(li, left, right): i = left j = right if i >= j: return li tmp = li[i] while i < j: while i < j and li[j] >= tmp: j -= 1 li[i] = li[j] while i < j and li[i] <= tmp: i += 1 li[j] = li[i] li[i] = tmp quick_sort(li, left, j-1) quick_sort(li, i+1, right) return li data = list(range(10)) random.shuffle(data) quick_sort(data, 0, len(data)-1) print(data)
堆排序
前传：树与二叉树简介
- 树是一种数据结构 比如：目录结构
- 树是一种可以递归定义的数据结构
- 树是由n个节点组成的集合：
如果n=0，那这是一棵空树；
如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。
二叉树：度不超过2的树（节点最多有两个叉）
- 满二叉树
- 完全二叉树
- （完全）二叉树可以用列表来存储，通过规律可以从父亲找到孩子或从孩子找到父亲
堆
- 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
- 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小
那么，堆有一定的规律，如果这个堆是这样的呢
堆排序过程：
- 建立堆
- 得到堆顶元素，为最大元素
- 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
- 堆顶元素为第二大元素
- 重复步骤3，直到堆变空
那么依托于这个过程，写一下代码
import random def sift(data, low, high): """ 建堆 :param data: :param low: :param high: :return: """ i = low # 堆的最高位置 j = 2 * i + 1 # 找左孩子 tmp = data[i] # 最高位置对应数值 while j <= high: # 孩子是否存在于树内, 一直往下找 if j+1 <= high and data[j] < data[j+1]: # 如果有右孩子并且右孩子比左孩子大 j = j+1 # j指向右孩子 if data[j] > tmp: # 如果孩子比父亲大 data[i] = data[j] # 孩子填充到父亲的空位 i = j # 孩子成为新父亲, 父亲成了孩子 j = 2 * i + 1 # 到下一层的新孩子 else: break data[i] = tmp # 最高领导放到父亲位置 def heap_sort(data): n = len(data) # 标识 data 的长度 # 建立好堆 for i in range(n//2-1, -1, -1): sift(data, i, n-1) # 出数 for i in range(n-1, -1, -1): # i指向堆的最后 data[0], data[i] = data[i], data[0] # 领导退休, 刁民上位 sift(data, 0, i-1) # 调整出新领导 data = list(range(100)) random.shuffle(data) heap_sort(data) print(data)
归并排序，希尔排序
更新中...