1) 选择排序
思想：
1、遍历数组，选择找到最大值，记录最大值下标 maxindex，然后将最大值与最后一个值交换，
即 swap(vec[maxindex] , vec[n-1]);
2、在剩下的待排序数组中，重新找到最大值，重复第一步，swap(vec[maxindex] , vec[n-2]);
循环操作，直至数组排序完成。
#include<iostream>
using namespace std;
const int N = 1e4;
int num[N],n;
void Select_sort(){
for(int i = 1; i < n; i++){//外层for控制找最大值的次数
int index = 0;
for(int j = 1; j <= n-i; j++){//找待排序元素中的最大值
if(num[index] < num[j])
index = j;
}
swap(num[index],num[n-i]);//交换
}
}
int main(){
cin>>n;
for(int i = 0; i < n; i++){
cin>>num[i];
}
Select_sort();
for(int i = 0; i < n; i++)
cout<<num[i]<<" ";
return 0;
}
平均时间复杂度：O(n^2)
第一次排序时是 n 个元素，比较 n-1 次
第二次排序时是 n-1 个元素，比较 n-2 次
第 n-1 次排序时是 2 个元素，比较 1 次
第 n 次排序时是 1 个元素，比较 0 次
元素交换次数为 k ( k < n-1 次）
时间复杂度 = 比较次数 + 交换次数
故选择排序时间复杂度为 O( 1+2+3+...+n-1+k) = O(n*(n-1)/2+k) = O(n^2)
空间复杂度：O(1)
在原数组上操作，即使用了常数级空间O(1)
稳定性：
不稳定
实例：3 2 3 1 从小到大排序（选择最小的放前面）排序之后红色 3 在黑色 3 前面，所以不稳定。
2)冒泡排序
思想：
1、从左到右，相邻两数两两比较，若下标小的数大于下标大的数则交换，将最大的数放在数组的最后一位（即下标 n-1 的位置）
2、采用相同的方法，再次遍历数组，将第二大的数，放在数组倒数第二的位置（即 n-2 的位置），以此类推，直到数组有序。
3、优化：当数组在整个遍历过程中没有发生交换，说明待排序数组已经有序，此时可以直接结束排序过程（用 bool 类型变量做标记）。
#include<iostream>
using namespace std;
const int N = 1e4;
int num[N],n;
void Bubble_sort(){
for(int i = 1; i < n; i++){
bool flag = false;
for(int j = 0; j < n-i; j++){
if(num[j] > num[j+1]) {
swap(num[j],num[j+1]);
flag = true;
}
}
if(!flag) return;
}
}
int main(){
cin>>n;
for(int i = 0; i < n; i++){
cin>>num[i];
}
Bubble_sort();
for(int i = 0; i < n; i++)
cout<<num[i]<<" ";
return 0;
}
平均时间复杂度：O(n^2)
最好时间复杂度（有序情况）：O(n)
比较 n-1 次，交换 0 次，故最好时间复杂度为 O(n)
最坏时间复杂度（逆序情况）：O(n^2)
第一次排序时是 n 个元素，比较 n-1 次，交换 n-1 次
第二次排序时是 n-1 个元素，比较 n-2 次，交换 n-2 次
第 n-1 次排序时是 2个元素，比较 1 次，交换 1 次
第 n 次排序时是 1 个元素，比较 0 次，交换 0 次
故冒泡排序时间复杂度为 O((1+2+3...+n-1)*2) = O(n*(n-1)) = O(n^2)
空间复杂度：O(1)
在原数组上操作，即使用了常数级空间 O(1)
稳定性
稳定
3) 请说下你对 MySQL 架构的了解？
先看下 MySQL 的基本架构图：
大体来说，MySQL可以分为Server层和存储引擎两部分。
连接器：负责和客户端建立连接，获取权限，管理连接
查询缓存：在一个查询语句中，会先到缓存中查看之前是否查询过这条语句（如果开启了查询缓存功能）：若存在则直接返回缓存的结果，优点是命中缓存时效率很高，缺点是缓存失效非常频繁，只要有对一个表的更新，该表所有的查询缓存都会被清空，MySQL8.0 版本已删除了查询缓存功能
分析器：对SQL语句进行词法分析和语法分析，判断语法是否合法
优化器：对SQL语句进行优化，选择索引
执行器：调用存储引擎接口，返回结果
存储引擎层负责：数据的存储和提取，其架构是插件式的，支持 InnoDB MyISAM 等多个存储引擎。从 MySQL 5.5.5 版本开始默认的是 InnoDB，但是在建表时可以通过 engine = MyISAM 来指定存储引擎。不同存储引擎数据的存取方式不同，支持的功能也不同。