排序
直接调用sort函数，注意key的选择
如果想要对两个或者多个层面进行排序，比如说一个二维数组[[1,2],[3,4]]，可以把key设成tuple形式，比如说key=lambda x:(x[0],x[1])，默认升序排列，如果想要降序，可以直接在前面添个负号，或者把reverse设为True
如果考场上不允许用这个方法，建议用选择排序或者计数排序。
选择排序：
- 需要自己定义compare函数，对于常见的比大小排序，实际上这个compare函数就是lambda x,y:return x<y,如果x<y,函数返回True，就说明找到了最小值，那么就需要与未排好序的第一个元素进行交换。
- 常见模板：
Python
for i in range(n):
best_idx = i # 当前位置应该放的记录索引
for j in range(i + 1, n):
if compare(records[j], records[best_idx]):
best_idx = j
# 交换到正确位置
<div markdown="1" style="margin-top: -30px; font-size: 0.75em; opacity: 0.7;">
:material-circle-edit-outline: 约 224 个字 :fontawesome-solid-code: 43 行代码 :material-clock-time-two-outline: 预计阅读时间 2 分钟
</div>
records[i], records[best_idx] = records[best_idx], records[i]x
计数排序：
需要先找到数组中的最大元素，然后构建一个计数数组，长度为maxVal+1
Python
def relative_sort_array(arr1, arr2):
# 1. 找到 arr1 中的最大值以确定计数数组的大小
# 如果题目没有给出范围，也可以用哈希表（dict）
upper = max(arr1)
# 2. 统计 arr1 中每个元素的出现次数
frequency = [0] * (upper + 1)
for x in arr1:
frequency[x] += 1
res = []
# 3. 首先处理 arr2 中的元素
for x in arr2:
while frequency[x] > 0:
res.append(x)
frequency[x] -= 1
# 4. 处理未在 arr2 中出现过的元素
# 计数数组的下标本身就是升序的，直接遍历即可
for x in range(upper + 1):
while frequency[x] > 0:
res.append(x)
frequency[x] -= 1
return res
# 测试示例 1
arr1_1 = [2,3,1,3,2,4,6,7,9,2,19]
arr2_1 = [2,1,4,3,9,6]
print(f"示例 1 输出: {relative_sort_array(arr1_1, arr2_1)}")
# 测试示例 2
arr1_2 = [28,6,22,8,44,17]
arr2_2 = [22,28,8,6]
print(f"示例 2 输出: {relative_sort_array(arr1_2, arr2_2)}")