基本算法之排序和排列
排序
下面是一些基础排序算法和其复杂度的表格：
| 排序算法 | 平均时间复杂度 | 基本原理 |
|---|---|---|
| 冒泡排序 | O(n^2) | 重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来 |
| 选择排序 | O(n^2) | 从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始（或末尾）位置，直到全部待排序的数据元素排完 |
| 插入排序 | O(n^2) | 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入 |
| 希尔排序 | O(n \log n) - O(n^2) | 通过定义间隔序列来表示在排序过程中进行比较的元素，依次缩小间隔进行排序 |
| 归并排序 | O(n \log n) | 利用分治策略，将原问题分解为若干个规模小而相互独立，与原问题形式相同的子问题，递归解决这些子问题，然后合并其结果，就得到原问题的解 |
| 快速排序 | O(n \log n) | 通过分治策略，选择一个基准元素，将比它小的元素移动到它的左边，比它大的元素移动至右边，对左右两边的序列重复进行这种分治排序 |
| 堆排序 | O(n \log n) | 利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点 |
| 计数排序 | O(n + k) | 将输入的数据值转化为键存储在额外开辟的数组空间中，然后依次把计数大于1的填充回原数组 |
| 桶排序 | O(n + k) | 将数组分到有限数量的桶里，每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序） |
| 基数排序 | O(nk) | 通过从低位开始，将所有待比较数值统一为同样的数位长度，数位较短的数前面补零，然后从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成以后, 数列就变成了一个有序序列 |
在Python中，对一个 list进行排序，常用它的子函数 sort()进行排序，如果是对更加复杂的数据结构进行排序，则需要使用 sorted()函数进行排序。
l = [3, 4, 2, 3, 1, 2, 3]
l.sort()
print(l)
最后的运行结果为：
[1, 2, 2, 3, 3, 3, 4]
sorted()的用法如下：
sorted(iterable, cmp=None, key=None, reverse=False)
iterable是一个可以迭代的对象，cmp为一个比较的函数，这个函数具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。key是用来比较的参数，一般是可迭代对象的数据成员。reverse表示是否递减。下面是一个使用范例：
d = {
'cxk': 2.5,
'wyb': 1.0,
'wyt': 5.0,
'hb': 10.0
}
nd = sorted(d.items(), key=lambda x: x[1])
print(nd)
sorted()返回的是一个列表，对字典使用 sorted函数，先得用 items方法转换为有序数对的列表，然后对其数对的索引1进行排序。最终输出的结果为：
[('wyb', 1.0), ('cxk', 2.5), ('wyt', 5.0), ('hb', 10.0)]
例题
答案：
import os
import sys
n,q = map(int, input().split(" "))
books = []
people = []
for i in range(n):
books.append(int(input()))
for q in range(q):
people.append(tuple(map(str, input().split(" "))))
books.sort()
# print(books)
# print(people)
def func1(book, target):
n = len(str(target))
if (book-target)%(10**n) == 0:
return True
return False
for i in people:
flag = 0
for j in books:
if int(j) - int(i[1]) < 0:
continue
else:
if func1(int(j), int(i[1])):
print(j)
flag = 1
break
if flag == 1:
flag = 0
else:
print(-1)
排列
利用 itertools 库中的 permutations
permutations的用法如下：
def permutations(iterable: Iterable[_T], r: Optional[int]=...) -> Iterator[Tuple[_T, ...]]
其中：
Iterable是一个可以迭代的对象，就是我们要进行全排列的数字；r是全排列的中元素的个数，例如在3个数据中找出r个数据的全排列。
下面是一个例子：
from itertools import permutations
print(list(permutations([1, 2, 3, 4])))
得到的结果为：
[(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]
自写全排列
递归
递归写全排列的方法如下：
def permute(nums, r):
def backtrack(first=0):
# 如果选择的元素数量符合要求，添加到输出列表中
if len(temp) == r:
output.append(temp[:])
return
for i in range(first, n):
# 动态维护数组
nums[first], nums[i] = nums[i], nums[first]
# 添加元素到当前排列
temp.append(nums[first])
# 继续递归填下一个数
backtrack(first + 1)
# 撤销操作
temp.pop()
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
output = []
temp = []
backtrack()
return output
例题
题解：
from itertools import permutations
nums = {1,2,3,4,5,6,7,8,9,10,11,12,13}
cnt = 0
for i in permutations(nums, 3):
if i[0] * i[1] == i[2]:
for j in permutations(nums - set(i), 3):
if j[0] / j[1] == j[2]:
for k in permutations(nums - set(i) - set(j) , 3):
if k[0] - k[1] == k[2]:
for l in permutations(nums - set(i) - set(j) - set(k) , 3):
if l[0] + l[1] == l[2]:
cnt += 1
print(cnt)
这个代码用到了如下几个性质：
- set类型能够进行加减运算，相当于数学中集合的加减运算；
- 乘除最难匹配，先匹配乘除，再匹配加减。
- 用到了剪枝的思想，这个思想会在后面具体讲解。
评论区