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. ​数据库的三范式

数据库的三范式是关系数据库设计的规范化原则，包括：

1. ​第一范式（1NF）​：每个字段都是原子的，不可再分。
2. ​第二范式（2NF）​：在1NF基础上，非主键字段完全依赖于主键。
3. ​第三范式（3NF）​：在2NF基础上，消除传递依赖。

通俗解释：

三范式就像整理房间的规则，确保数据存储的合理性和高效性。

​第一范式（1NF）​：每个物品都放在固定的位置，不能乱放。

第二范式（2NF）​：每个物品都放在它专属的抽屉里。

第三范式（3NF）​：抽屉里不能放其他抽屉的钥匙。