时间复杂度与空间复杂度
常用O(1)或O(n)表示，其中1表示一个单位(最简单的单位，可以是多个或1个，但在时间上总体是较低且连续的)，时间通常指的是程序运行时间，空间则是指程序在运行时所占用的内存空间。各个阶段的复杂度可用下面的顺序比较:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) ...
注意：
1. O(n2) 表示 O(n的平方)
2. O(logn) 表示时间(或空间)单位相对于n的对数，即：假设时间(或空间)的k次方为n，logn 表示实际复杂度为k
注意递归必定具有空间复杂度，因为系统需要开辟空间来记录每次函数递归前的状态，以便结果返回时调用。
递归与汉洛塔
递归有两个特点:
- 调用自身
- 有明确的终止条件
汉罗塔问题则是一个很好的递归例子，通过Python实现如下:
def hanoi(n, a, b, c):
"""
将 n 个盘子从柱子 a 经过 柱子 b 移动到柱子 c
步骤如下：
首先需要将 n-1 个盘子经过柱子 c 移动到柱子 b
此时柱子 a 只剩一个盘子(最底部的大盘子)，柱子 c 为空
然后将柱子 a 的盘子 移动到柱子 c
此时柱子 a 为空
最后将 n-1 个盘子经过柱子 a 移动到柱子 c
此时所有盘子都在柱子 c上
n 为要移动的 n 个盘子
a 柱子 a
b 柱子 b
c 柱子 c
注意三个参数的顺序
"""
if n > 0:
hanoi(n-1, a, c, b)
print(f'Moving {a} to {c}')
hanoi(n-1, b, a, c)
查找
查找一般来说是在某个对象(列表、集合等)中找到指定的元素所在位置。
顺序查找
顺序查找的时间复杂度为O(n)，实现如下:
def linear_search(li, val):
"""
遍历并比较，找到合适的值的索引并返回
"""
for index, value in li:
if value == val:
return index
else:
return None
二分查找
二分查找的时间复杂度为O(logn)，但前提是只能对经过排序后的列表产生作用，如果拿到的是未经排序的列表，那么对列表进行排序的时间复杂度为O(n)。假定拿到的是已经排好序的列表，那么二分法实现如下:
def binary_search(li, val):
"""
每次取中间值，找到待索引区域
直到找到指定的值或没有中间值为止
"""
left = 0
right = len(li) - 1
while right >= left:
mid = (left + right) // 2
value = li[mid]
if value == val:
return mid
elif value > val:
right = mid - 1
else:
left = mid + 1
else:
return None
排序
冒泡排序
遍历列表的每一个值，如果当前值大于当前值的后面一个值，则交换两个值的位置，使较大的值处于后面。重复遍历直到排好序为止。
算法实现:
def bubble_sort(li):
"""冒泡排序
遍历 len(li)-1 趟 (从0开始)
"""
cycles = len(li) - 1
for i in range(cycles):
is_exchanged = False
for j in range(cycles - 1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
if not is_exchanged:
is_exchanged = True
if not is_exchanged:
break
选择排序
遍历列表，找到最小的值，将它放到一个新的位置。如此反复直到剩下的所有值都转移到新位置为止。算法实现:
def select_sort(li):
"""选择排序
遍历 len(li) - 1 趟 (从0开始)"""
li_length = len(li)
for i in range(li_length-1):
# 找到并记录最小元素所在位置
min_loc = i
for j in range(i+1, li_length):
if li[j] < li[min_loc]:
min_loc = j
if min_loc != i:
li[min_loc], li[i] = li[i], li[min_loc]
插入排序
插入排序类似于摸牌，每当摸到一张新牌时，就和手里面的牌依次进行比较，如果小于被比较的牌，则将被比较的牌往后移一位，直到大于被比较的牌或前面没有牌可以比较时(即摸到的牌为当前手里牌最小的牌)，将摸到的牌插入到当前位置的后一位。算法实现：
def insert_sort(li):
"""插入排序
类似于打牌，从列表中依次取一张牌
用获取的牌与手中的牌依次对比
如果获取的牌比对比的牌小，则将它插入到对比的牌的前面
"""
for i in range(1, len(li)):
# 假定第一张牌为手中的牌
# i 表示获取的牌的下标
tmp = li[i]
# j 表示手里牌的下标
j = i - 1
while j >= 0 and li[j] > tmp:
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
快速排序
从列表中随机选一个数，并将它重新放到列表中，使得它左边的数都比它小，它右边的数都比它大。根据它的位置将列表分为两部分，再依次对这两部分执行同样的操作，最后递归直到所有数都按顺序排好为止。
快速排序的复杂度是O(nlogn)，而上面三种(冒泡、选择、插入)的复杂度为O(n^2)，因此快速排序实现较快。但仍有极低概率出现最坏的情况，使得快速排序的复杂度为O(n^2)。算法实现:
"""
Quick sort
"""
import random
def quick_sort(li, left, right):
"""快速排序算法"""
if left < right:
mid = partition(li, left, right)
quick_sort(li, left, mid-1)
quick_sort(li, right, mid+1)
def partition(li, left, right):
"""从给定列表的指定范围随机抽取一个数 x
找到 x 在列表中的相应位置 pos
使得列表中所有 pos 左边的数都比 x 小
所有 pos 右边的数都比 x 大
将 x 放到列表中 pos 所在的位置
并返回 pos
"""
pos = random.randint(left, right)
tmp = li[pos]
while left < right:
# 由于取出了tmp
# 可以视作tmp所在列表中的位置为一个空位
# 先从空位的左边部分从左往右开始寻找
# 如果出现某个数大于tmp
# 那么交换两个数的位置
while left < pos and li[left] <= tmp:
left += 1
li[pos] = li[left]
pos = left
# 同理从右往左找
while pos < right and li[right] >= tmp:
right -= 1
li[pos] = li[right]
pos = right
# 最后将 tmp 放到 pos 所在位置
# 使得: pos 左边的数都比 tmp 小，
# pos 右边的数都比 tmp 大
li[pos] = tmp
return pos
if __name__ == '__main__':
li = list(range(10000, 0, -1))
# random.shuffle(li)
print(li)
quick_sort(li, 0, len(li)-1)
print(li)
堆排序
前言 - 树与堆
- 树
- 定义
树是一种数据结构，从一个点出发，分散为多个点，
每一个分散的点又可以分散为多个点，照此依次递归直到不再有分散的点为止。
- 节点
其最顶部的节点被称为树的根节点，最底部的节点被称为叶子节点(即不再有延申)。
树的每个度关联着父节点和子节点，子节点是从父节点延申出来的。
- 度
每次分散的维度(次数)又被称为度，树的度则是取树中最大的度。
- 二叉树
- 定义
二叉树是树中的一种特殊结构，表示树的每个节点的子节点不超过两个。
- 满二叉树
二叉树的每一个节点都有两个子节点(叶子节点除外，因为它没有子节点)。
- 完全二叉树
从树的顶部往下，有不间断的子节点，直到叶子节点。
叶子节点右边可以不完整，但从左往最右的部分不能出现断裂。
- 完全二叉树与列表
将完全二叉树的每个节点，从顶至下，且从左至右依次取出，依次放入一个列表中，如：
9
/ \
8 7
/ \ / \
6 5 4 3
/ \
2 1
转化为列表：
[9, 8, 7, 6, 5, 4, 3, 2, 1]
下标： 0, 1, 2, 3, 4, 5, 6, 7, 8
那么此时，给定任意节点在列表中的位置 i ，
可以根据固定的公式找到其父节点和左右子节点所在位置：
左边子节点 l:
l = 2i + 1
右边子节点 r:
r = 2i + 2
父节点 f：
f = i - 1 // 2
- 堆
- 定义
堆是一种特殊的完全二叉树结构，它分为：
a. 大根堆
任一节点比其子节点大
b. 小根堆
任一节点比其子节点小
注意：当根节点的左右子树都是堆，但其自身不是堆时，可以通过一次向下调整使其变为堆，比如:
0
/ \
8 7
/ \ / \
6 5 4 3
/ \
2 1
||
\/
8
/ \
6 7
/ \ / \
2 5 4 3
/ \
0 1
过程描述：
0首先和8比较，因为小于8所以和8交换位置，
依次继续和其子节点进行比较，如果小于其子节点则交换位置，
直到不再小于其子节点或没有子节点为止。
- 构造堆
对任一完全二叉树，都可以通过下面的方法将其转化为堆：
假定有完全二叉树如下：
0
/ \
4 6
/ \ / \
9 1 7 2
/ \
3 5
现将二叉树拆分为一个个小的子二叉树，
比如最下面的 5,3,9 为一个子二叉树，依次是:
4
6 9 1 ...
7 2 3 5
接下来对每一个子二叉树进行一次向下调整，使其变为一个堆。
比如最后的子二叉树调整为(因为符合堆的特征所以没有调整):
9 9
/ \ => / \
3 5 3 5
2,7,6调整为：
6 7
/ \ => / \
7 2 6 2
5,3,1,9,4 调整为：
4 9
/ \ => / \
9 1 5 1
/ \ / \
3 5 3 4
最后，这个完全二叉树就会变成一个堆：
9
/ \
5 7
/ \ / \
4 1 6 2
/ \
3 0
实际上就是对每一个子二叉树进行向下调整，
每当最下面的子二叉树稻城堆条件时，将其整合到上面一层，
然后再对整合后的二叉树进行向下调整，如此往复
堆排序
堆排序本质上就是把列表当作一个完全二叉树，然后从二叉树的最后一个叶子节点所在的最下子二叉树开始，一步步的构造一个堆(大根堆或小根堆)，构造完堆后，即可根据堆的特性一次次的弹出一个数并保存到列表的最后，同时缩小堆的规模(去掉最后一个数，这个数是已经排好序的)，如此往复直到堆被缩小到0为止，此时的列表就变为了一个有序列表了。
堆排序的时间复杂度为O(nlogn)。
代码实现：
- 向下调整的代码实现:
def sift(li, low, high):
"""
对堆进行向下调整
使得在指定范围内的二叉树变为堆结构
:param li: 列表
:param low: 二叉树顶点位置 即根节点位置
:param high 指定范围内的二叉树的最后一个元素所在位置
"""
# i 指向堆顶点
# left 指向 i 的左孩子
# tmp 用于保存顶部变量
i = low
left = i * 2 + 1
tmp = li[i]
while left <= high:
# 从左右节点中找出最大的元素
# 赋值给larger
larger = left
right = left + 1
if right <= high and li[right] > li[left]:
larger = right
# 将左右孩子中最大的元素与顶点进行比较
if li[larger] > tmp:
# 如果大于顶点则将顶点置为最大的孩子元素
# 同时重新对 顶点和顶点的左孩子进行赋值
# 即向下看一层
li[i] = li[larger]
i = larger
left = i * 2 + 1
else:
# 如果不大于则表示本次向下调整完成
# 结束循环
break
# 最后将缓存的顶点元素放到 i 指向的位置
# 此时 i 如果未调整则是顶点元素
# 如果经过调整则是左右孩子中的任一个孩子所在位置
li[i] = tmp
- 堆排序实现：
def heap_sort(li):
length = len(li)
# 构造堆
# 从下往上 找到每一个子完全二叉树的顶点
# 顶点位置是相邻的
# 进行向下调整
left = length - 1
top = (left - 1) // 2
for i in range(top, -1, -1):
sift(li, i, left)
# 从后往前遍历堆的每一个元素
# 取出堆的根节点(即列表的最大值)
# 与堆的最后一个叶子元素进行交换
# 并将堆的范围缩减一个元素(即排除最后一个叶子元素，也是列表的最大值)
# 对堆进行一次向下调整
# 重复上面的步骤，即可完成堆排序
for i in range(left, -1, -1):
li[0], li[i] = li[i], li[0]
sift(li, 0, i-1)
堆排序与topk
topk问题是指从一个列表中找到排名前k的值，有如下几种思路用来解决该问题：
- 排序后切片 时间复杂度为 O(nlogn)
- 冒泡/选择/插入排序(只需要排k次) 时间复杂度为 O(kn)
- 堆排序思路 时间复杂度为 O(klogn)
上面三种思路中，堆排序思路是时间复杂度是最低的。使用堆排序解决topk问题的大致思路如下:
1. 取列表的前k个值构造一个小根堆，假定堆顶就是目前第k大的数
2. 在列表中从k往后依次取出一个值与小根堆的根节点值进行比较，
如果小于该节点值则忽略该元素，
否则将堆顶更换为该元素，并重新进行一次向下调整
3. 遍历完成后，前k个值则为反序的列表中最大的k个元素
实现代码如下:
def sift(li, low, high):
"""
对堆进行向下调整
使得在指定范围内的二叉树变为堆结构
:param li: 列表
:param low: 二叉树顶点位置 即根节点位置
:param high 指定范围内的二叉树的最后一个元素所在位置
注意与上面的sift函数比较，上面sift中的 > 符号在此处全部变为了 <
这表示构造出来的堆是一个小根堆
"""
i = low
left = i * 2 + 1
tmp = li[i]
while left <= high:
larger = left
right = left + 1
if right <= high and li[right] < li[left]:
larger = right
if li[larger] < tmp:
li[i] = li[larger]
i = larger
left = i * 2 + 1
else:
break
li[i] = tmp
def topk(li, k):
"""
找出 li 中最大的 k 个数
但是不改变 li 的结构
返回一个长度为 k 的有序列表
"""
# 对 li 的前 k 个元素构造堆
heap = li[0:k]
left = k - 1
top = (left - 1) // 2
for i in range(top, -1, -1):
sift(heap, i, left)
# 遍历 li 中 k 后面的值并与堆顶进行比较
end = len(li) - 1
for i in range(k, end):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap, 0, left)
# 对构造的堆进行排序
for i in range(left, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
sift(heap, 0, i-1)
# 返回包含前 k 个元素的列表
return heap
归并排序
- 归并的含义：
对两个有序的列表进行一定操作，归并为一个有序的列表。
具体操作如下：
假定有如下两个有序列表，分别为 li1, li2：
1， 5， 8， 3， 6， 9
此时开辟一个新的临时列表 tmp
分别依次从 li1, li2 中的第一个元素开始，
假定分别为 x, y，且 x 大于 y
比较两个元素的大小，将较小的元素(y)放到临时列表中，
留下较大的元素(x)与 li2 的下一个元素进行比较
重复上面的步骤，最后即可得到一个新的有序列表
- 归并排序：
归并排序是将列表分解为两个部分
在将分解后的两个部分各分解为两个部分
以此重复，
直到最后分解后的两个部分为两个有序的列表时
也就是两个列表各自包含的元素为0个或一个时
对两个列表进行归并即可
简单来说，归并排序与堆排序有些类似，
二者都是知晓某个原理(堆/归并)，
再构造条件运用该原理从而实现排序
- 代码实现：
def merge(li, low, mid, high):
"""归并
对指定范围内的列表元素进行归并操作
并用归并后的结果覆盖该列表相应范围内的元素
"""
# 创建一个临时列表
# 将原列表指定范围内的数据切分为两部分
# 并用变量 j 指向第二部分的初始位置
# 用变量 i 指向第一部分的初始位置
tmp = []
i = low
j = mid + 1
# 取出两部分的第一个元素进行比较
# 将较小的元素放到临时列表中
# 再往后查找新的元素进行比较
# 直到有一个部分的元素已全部取出为止
while i <= mid and j <= high:
if li[i] < li[j]:
tmp.append(li[i])
i += 1
else:
tmp.append(li[j])
j += 1
# 分别检查两个部分
# 如果还有剩余的元素
# 则依次添加到临时列表中
while i <= mid:
tmp.append(li[i])
i += 1
while j <= high:
tmp.append(li[j])
j += 1
# 将临时列表的数据写入到原列表对应的位置
# 注意覆盖范围需要包含 high
# 所以使用 high+1
li[low:high+1] = tmp
def merge_sort(li, low=0, high=None):
"""归并排序
不断将列表分为两个部分
直到两个部分都为有序时(包含元素为1个或0个时)
进行归并
"""
# 第一次递归前
if high is None:
high = len(li) - 1
# 至少有两个元素 递归
if low < high:
mid = (low + high) // 2
merge_sort(li, low, mid)
merge_sort(li, mid + 1, high)
merge(li, low, mid, high)
- 归并排序的时间复杂度与空间复杂度
因为涉及到创建新的列表以及递归
所以归并排序也存在空间复杂度，
它的空间复杂度为 O(n)
时间复杂度为 O(nlogn)
几种排序对比
注：
1. 快排涉及递归，所以存在空间复杂度；
2. 稳定性是指再存在两个相同元素的情况下，两个相同元素的相对位置是否变动，
如果相对位置发生了改变，则不稳定，反之即稳定。
一般来说，对列表进行挨次调整的算法(如冒泡排序、归并排序等)是稳定的，
而跳着调整的算法(如插入排序、快速排序)则不稳定。
希尔排序
- 希尔排序是在插入排序的基础上做的改良。大体思路如下：
假定列表长度为 n
以某个数 d 为基点，这个数需大于 0 小于 n， 假定为 n // 2
从列表的起始位置开始，以 d 为间隔，每隔 d 个单位从列表中去一个值
直到列表末尾
把取出的值视作一个列表，对这个列表进行插入排序
重复上面的步骤直到列表中的值取完为止
此时将 d 设为 d // 2
继续重复上面的步骤
直到 d 变为 1 时，进行最后一次插入排序
结束后排序完成
- 代码实现：
def insert_sort_gap(li, gap):
"""
有间隔的插入排序
"""
for i in range(gap, len(li)):
tmp = li[i]
j = i - gap
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
def shell_sort(li):
"""
希尔排序
"""
d = len(li) // 2
while d >= 1:
insert_sort_gap(li, d)
d //= 2
- 复杂度
希尔排序的时间复杂度介于 O(n) 到 O(n^2) 之间
这取决于 d 的取值(不同的取值方法会导致不同的时间复杂度)
目前取值方法中最快的时间复杂度为:
O(nlog2n) 即O(n*logn*logn)
具体可参见维基百科
计数排序
- 概念
假定已知一个未知长度的列表中的元素全都介于 0-100 之间
这个列表为 li
创建一个新的元素全部为 0 且长度为 100 的列表 tmp
遍历 li 中的每一个元素
用 tmp 统计该元素的出现次数
清空 li
将 tmp 中存储的元素及出现次数依次写入到 li 中
排序完成
- 代码实现
def count_sort(li, max_count):
"""计数排序
:param li: 需要排序的列表
:param max_count: 列表元素的最大值
该列表中的所有值介于 0 到 max_count 之间
"""
# 创建临时列表用于计数
tmp = [0 for _ in range(max_count+1)]
for i in li:
tmp[i] += 1
# 将统计好的结果重新写入到 li 中
li.clear()
for index, val in enumerate(tmp):
for i in range(val):
li.append(index)
- 复杂度
由于计数排序需要创建新的列表，所以存在空间复杂度，最大为 O(n)
其时间复杂度为 O(n)
桶排序
- 概念
桶排序基于计数排序
假定有一个列表 li
li 列表中的数最大值为10000
分 10 个列表(即桶)
分别对应： 0-9999 10000-19999 20000-29999 ... 的数值范围
遍历 li
按 0-9999 10000-19999 20000-29999 ... 的范围区分每个数
并将数放入相应的桶中
放入时可做相应的排序，保持桶内的数有序
完成后将所有的桶重新组成一个列表
此时排序完成
- 代码实现
def bucket_sort(li, n=100, max_num=10000):
"""桶排序
:param n: 分为多少个桶
:param max_num: 列表中的最大值
"""
# 创建桶
buckets = [[] for _ in range(n)]
for var in li:
# 找到元素属于哪个桶
# 注意当 var == max_num 时
# var // (max_num // n) == 10
# 所以需要考虑到这种情况
# 因此使用 min
i = min(var // (max_num // n), n-1)
# 将元素放入相应的桶中
buckets[i].append(var)
# 保持桶内有序(插入排序)
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break
li.clear()
for bucket in buckets:
li.extend(bucket)
- 复杂度
桶排序的时间复杂度为 O(n+k) ~ O(n2k)
空间复杂度为 O(nk)
桶排序的表现取决于数据的分布，也就是需要对数据排序时采取不同的分桶策略
基数排序
- 概念
基数排序类似于桶排序，但分桶策略有所不同
首先找到列表中的最大数
并算出这个数的位数 k (比如: 1000 -> 3, 99999 -> 5)
首先遍历列表，对列表中所有值按个位数排序(分别放入 0-9 10个桶中)
再次遍历列表，... 按十位数进行排序
...
遍历 k 次
最后列表即为有序
- 代码实现
def radix_sort(li):
"""基数排序"""
# 找到列表中最大的值的位数并遍历
k = 0
max_num = max(li)
while 10 ** k <= max_num:
# 创建桶
buckets = [[] for _ in range(10)]
# 遍历列表
for val in li:
# 找到当前 k 对应的位数的值 并放入对应的桶中
# 89 & k=0 -> 9
# 89 & k=5 -> 0
digit = (val // 10 ** k) % 10
buckets[digit].append(val)
# 重置列表
li.clear()
for bucket in buckets:
li.extend(bucket)
k += 1