CC基础知识复习53
目录
C/C++基础知识复习(53)
1. 插入排序 & 计数排序
插入排序：
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i-1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}- 时间复杂度 ：O(n²)
- 空间复杂度 ：O(1)
- 稳定性 ：稳定
计数排序：
void countingSort(int arr[], int n) {
int maxVal = *std::max_element(arr, arr+n);
std::vector<int> count(maxVal+1, 0);
for (int i = 0; i < n; i++) count[arr[i]]++;
int idx = 0;
for (int i = 0; i <= maxVal; i++) {
while (count[i]--) arr[idx++] = i;
}
}- 时间复杂度 ：O(n+k)
- 空间复杂度 ：O(k)
- 稳定性 ：稳定
2. 数据库的三范式
数据库的三范式是关系数据库设计的规范化原则，包括：
- 第一范式（1NF） ：每个字段都是原子的，不可再分。
- 第二范式（2NF） ：在1NF基础上，非主键字段完全依赖于主键。
- 第三范式（3NF） ：在2NF基础上，消除传递依赖。
通俗解释：
三范式就像整理房间的规则，确保数据存储的合理性和高效性。
第一范式（1NF） ：每个物品都放在固定的位置，不能乱放。
第二范式（2NF） ：每个物品都放在它专属的抽屉里。
第三范式（3NF） ：抽屉里不能放其他抽屉的钥匙。