插入排序 计数排序 数据库的三范式
1) 插入排序
思想:
1、将数组分为有序表和无序表,每次从无序表中取出一个元素,插入到有序表的适当位置,刚开始有序表中只有一个数,无序表中有 n-1 个数。
2、每遍历一次,有序表中元素增加一个,无序表中元素个数减少一个,重复 n-1 次,完成排序。
代码:
#include<iostream>
#include<memory>
#include<vector>
using namespace std;
void insert_sort(vector<int>&vec) {
for(int i = 1; i < vec.size(); i++) {//插入多少个元素
int j = i - 1;//代表的是有序部分的最后一个元素
int index = vec[i];//代表的是要插入的元素
for( ; j >= 0; j--){//寻找插入位置
if(vec[j] > index) vec[j+1] = vec[j];
//给要插入的元素腾出来一个位置
else break;
}
vec[j+1] = index;
}
}
int main(){
vector<int> vec = { 4,3,1,2,7,6,4 };
insert_sort(vec);
for(auto it : vec) cout<<it<<" ";
return 0;
}
平均时间复杂度:O(n^2)
最好时间复杂度(有序情况):O(n)
比较 n-1 趟,每一趟比较一次,不移动元素,故最好时间复杂度为 O(n)
最坏时间复杂度(逆序情况):O(n^2)
第一次排序时有序表 1 个元素,无序表 n-1 个元素,比较 1 次,移动 1 次
第二次排序时有序表 2 个元素,无序表 n-2 个元素,比较 2 次,移动 2 次
...
第 n-1 次排序时有序表 n-1 个元素,无序表 1 个元素,比较 n-1 次,移动 n-1 次
故插入排序时间复杂度为 O((1+2+3...+n-1)*2) = O(n*(n-1)) = O(n^2)
空间复杂度:O(1)
在原数组上操作,即使用了常数级空间 O(1)
稳定性
稳定
2)计数排序
思想:
原理:将数值作为桶号,遍历整个数组,将相应的桶进行计数
1、遍历原数组,找到最大值 max,然后申请 max+1 个空间(桶),初始化为0(下标为0~mas),
即 vector<int>bucket(max+1,0)
2、再次遍历原数组,找到每个数值对应的桶号,并对桶计数++,即 bucket[ vec[i] ]++
3、遍历桶数组,看对应的桶内计数为几就取出几下下标值(桶号),放到原数组中。
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e4;
int num[N];
//计数排序
void Bucket_Sort(int n) {
//找到最大值
int max = num[0];
for(int i = 0; i < n; i++) max = max < num[i] ? num[i] : max;
//创建桶
int* bucket = new int[max+1]{0};
//将元素放入桶中
for(int i = 0; i < n; i++) bucket[num[i]]++;//计数
//将元素取出还原
int j = 0;
for(int i = 0; i <= max; i++){
while(bucket[j] > 0){
num[j++] = i;
bucket[i]--;
}
}
}
int main(){
int n;
cin>>n;
for(int i = 0; i < n; i++) {
cin>>num[i];
}
Bucket_Sort(n);
for(int i = 0; i < n; i++) {
cout<<num[i]<<" ";
}
}
平均时间复杂度:O(n)
遍历数组找最大值 max 时间复杂度为 O(n)
遍历数组把对应的数放入对应的桶时间复杂度也为 O(n)
遍历桶,从桶中把数取出来放入原数组,假设有 m 个空桶,则时间复杂度为 O(n+m)
总上所述时间复杂度为 O(3n+m) = O(n)
空间复杂度:O(n)
创建了辅助数组(桶),即 max+1 个桶(不管创建了多少桶,只要创建了辅助数组,空间复杂度就是 O(n)
稳定性
稳定
3) 数据库的三范式是什么?
1、第一范式:强调的是列的原子性,即数据库表的每一列都是不可分割的原子数据项;
2、第二范式:要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性;
3、第三范式:任何非主属性不依赖于其它非主属性