插入排序与计数排序；数据库的三范式
1. 插入排序与计数排序
插入排序
- 代码（以升序排序为例，采用C语言风格）:
void insertionSort(int arr[], int n) { | |
int i, key, j; | |
for (i = 1; i < n; i++) { | |
key = arr[i]; | |
j = i - 1; | |
while (j >= 0 && arr[j] > key) { | |
arr[j + 1] = arr[j]; | |
j = j - 1; | |
} | |
arr[j + 1] = key; | |
} | |
} |
-
时间复杂度：
- 最好情况：O(n)（当输入数组已经有序时）。
- 最坏情况：O(n^2)（当输入数组是逆序时）。
- 平均情况：O(n^2)。
-
空间复杂度：O(1)（只需要常量级别的额外空间）。
-
稳定性：稳定（当遇到相等元素时，不会改变它们的相对位置）。
-
代码提升：
- 对于小规模数据集或几乎有序的数组，插入排序表现良好。
- 可以通过二分查找法优化查找插入位置的过程，但这种优化在大多数情况下并不显著，因为插入排序的主要开销在于元素的移动。
计数排序
- 代码（以升序排序为例，采用C语言风格，并假设待排序元素为0到k之间的整数）：
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
void countingSort(int arr[], int n, int k) { | |
int count[k + 1]; | |
int output[n]; | |
memset(count, 0, sizeof(count)); | |
for (int i = 0; i < n; i++) { | |
count[arr[i]]++; | |
} | |
for (int i = 1; i <= k; i++) { | |
count[i] += count[i - 1]; | |
} | |
for (int i = n - 1; i >= 0; i--) { | |
output[count[arr[i]] - 1] = arr[i]; | |
count[arr[i]]--; | |
} | |
memcpy(arr, output, sizeof(output)); | |
} |
-
时间复杂度：O(n + k)，其中n是数组的长度，k是待排序元素的最大值。
-
空间复杂度：O(n + k)（需要额外的数组来存储计数和输出）。
-
稳定性：稳定（当遇到相等元素时，它们会按照在输入数组中的相对顺序出现在输出数组中）。
-
代码提升：
- 计数排序对于小范围的整数排序非常高效。
- 如果k的值很大，可以考虑使用其他算法，如基数排序或桶排序，这些算法可以处理更广泛的元素范围。
- 在实际应用中，可以通过优化内存分配和减少不必要的数组复制来进一步提高性能。
2. 数据库的三范式
数据库的三范式是数据库设计中的一种规范标准，旨在减少数据冗余并建立结构合理的数据库。以下是三范式的具体定义：
- 第一范式（1NF）：确保每个表中的每个字段都是原子的，即每个字段的值都不能再被分解为更小的数据单元。这可以避免数据冗余和数据更新异常的问题。
- 第二范式（2NF）：在满足第一范式的基础上，要求每个非主键字段都完全依赖于主键，而不是依赖于主键的一部分或其他非主键字段。这可以进一步减少数据冗余和更新异常的问题。
- 第三范式（3NF）：在满足第二范式的基础上，要求每个非主键字段都只依赖于主键，而不依赖于其他非主键字段。这可以确保数据表中的每个字段都有其独立的意义，并且进一步减少数据冗余。
遵循三范式有助于保持数据的一致性、完整性和查询效率。然而，在实际应用中，有时为了优化查询性能或满足特定业务需求，可能会适当地违反范式规则，引入一些冗余数据或关联表。这需要在设计时综合考虑系统需求、性能要求、数据复杂性和系统扩展性等因素，并权衡范式的优劣。