插入排序
#include <iostream>
#include <vector>
// 插入排序函数
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i]; // 当前要插入的元素
int j = i - 1; // 从已排序序列的最后一个元素开始比较
// 将大于 key 的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入 key 到正确的位置
}
}
int main() {
std::vector<int> arr = {5, 4, 3, 2, 1};
std::cout << "Original array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
insertionSort(arr);
std::cout << "Sorted array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
时间复杂度:最好on,最差on方
空间复杂度:o1
稳定性:稳定
是否能对代码进行提升:可以使用二分查找优化寻找位置环节
计数排序
#include <iostream>
#include <vector>
#include <algorithm>
// 计数排序函数
void countingSort(std::vector<int>& arr) {
if (arr.empty()) return;
int maxVal = *std::max_element(arr.begin(), arr.end());
int minVal = *std::min_element(arr.begin(), arr.end());
int range = maxVal - minVal + 1;
std::vector<int> count(range, 0);
std::vector<int> output(arr.size());
// 统计每个元素出现的次数
for (int num : arr) {
count[num - minVal]++;
}
// 计算累计频率
for (int i = 1; i < range; ++i) {
count[i] += count[i - 1];
}
// 构建输出数组
for (int i = arr.size() - 1; i >= 0; --i) {
output[count[arr[i] - minVal] - 1] = arr[i];
count[arr[i] - minVal]--;
}
// 将排序好的元素复制回原数组
for (int i = 0; i < arr.size(); ++i) {
arr[i] = output[i];
}
}
int main() {
std::vector<int> arr = {5, 4, 3, 2, 1};
std::cout << "Original array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
countingSort(arr);
std::cout << "Sorted array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
时间复杂度:最好on+k,最差on+k
空间复杂度:on+k
稳定性:稳定
是否能对代码进行提升:可以考虑使用 std::unordered_map 来存储元素及其出现的次数,当元素范围很大但元素个数较少时,可减少空间开销。
数据库的三范式是什么?
数据库的三范式(3NF)是数据库设计中用于规范关系型数据库表结构的一系列规则,旨在减少数据冗余,提高数据完整性和一致性。
一、第一范式(1NF)
定义:
- 要求数据库表的每一列都是不可再分的原子数据项,即表中的每个属性都不能再拆分成多个子属性。
示例:
- 不满足 1NF 的表:
| 学生信息 |
| 张三,20 岁,男 | - 满足 1NF 的表:
| 姓名 | 年龄 | 性别 |
| 张三 | 20 | 男 |
二、第二范式(2NF)
定义:
- 在满足第一范式的基础上,非主属性完全依赖于主键。这意味着如果表有复合主键,其他属性必须完全依赖于整个主键,而不是主键的一部分。
示例:
- 不满足 2NF 的表(假设主键是
(学生ID, 课程ID)
):
| 学生 ID | 课程 ID | 学生姓名 | 课程名称 | 成绩 |
| 001 | 001 | 张三 | 数学 | 85 |
| 001 | 002 | 张三 | 语文 | 90 | - 这里
学生姓名
只依赖于学生ID
,而不依赖于(学生ID, 课程ID)
,存在部分依赖。 - 满足 2NF 的表可以拆分成:
- 学生表(
学生ID
为主键):
| 学生 ID | 学生姓名 |
| 001 | 张三 | - 成绩表(
(学生ID, 课程ID)
为主键):
| 学生 ID | 课程 ID | 课程名称 | 成绩 |
| 001 | 001 | 数学 | 85 |
| 001 | 002 | 语文 | 90 |
三、第三范式(3NF)
定义:
- 在满足第二范式的基础上,任何非主属性不传递依赖于主键。即非主属性之间不能存在依赖关系,它们只能直接依赖于主键。
示例:
- 不满足 3NF 的表(假设主键是
学生ID
):
| 学生 ID | 学生姓名 | 系名 | 系主任 |
| 001 | 张三 | 计算机系 | 李四 | - 这里
系主任
依赖于系名
,而系名
依赖于学生ID
,存在传递依赖。 - 满足 3NF 的表可以拆分成:
- 学生表(
学生ID
为主键):
| 学生 ID | 学生姓名 | 系名 |
| 001 | 张三 | 计算机系 | - 系表(
系名
为主键):
| 系名 | 系主任 |
| 计算机系 | 李四 |
使用三范式的优点:
- 减少数据冗余:避免了重复存储数据,节省了存储空间。
- 提高数据完整性:降低了数据更新、插入和删除时出现不一致的风险。
- 方便维护:使数据库结构更清晰,易于理解和维护。
使用三范式的局限性:
- 有时为了提高性能,可能需要反规范化(denormalization)。例如在数据仓库中,经常会为了查询性能而牺牲一些范式规则,通过冗余数据来减少多表连接的操作,提高查询效率。
总之,三范式是数据库设计的重要指导原则,但在实际应用中,需要根据具体的业务需求和性能要求灵活调整,以达到性能和数据一致性之间的平衡。