@許奕軒(https://discourse.xinyoudui.com/u/許奕軒)
@张彧
扯一下（bushi
步入damn题
课堂知识点
学习重点
一、时间复杂度在算法当中需要注意的事项
思考题
写下你的思考：
知识点：
1.时间复杂度
OJ后台编译器每秒大约执行10^7个基本运算，学会根据题目给定的n的范围来选择算法。
| 时间复杂度 | 建议不超过的n的范围 |
|---|---|
| O(logn) | long long内都行 |
| O(n) | 10^7 |
| O(nlogn) | 10^5 ~ 5*10^5 |
| O(n²) | 1000 ~ 5000 |
| O(n³) | 200 ~ 500 |
注： logn的计算方式：
logn 是以 2 为底的对数，表示将底数为 2 的指数幂变为 n 所需要的幂次，即 2^k=n，则 k=log_2n
此处表达的意思就是以2为底，n的对数，可简写为 logn。
以下是常见时间复杂度对比图：
2.插入排序与桶排序
插入排序
插入排序是一种简单直观的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。具体的排序过程如下：
-
从第一个元素开始，认为该元素已经被排序
-
取出下一个元素，在已经排序的元素序列中从后向前扫描
-
如果已排序的元素大于新元素，则将该元素移到下一位置
-
重复步骤3，直到已排序的元素小于或等于新元素
-
将新元素插入到该位置后
-
重复步骤2~5，直到排序完成
如图所示
插入排序实现核心代码如下：
/*插入排序*/
for(int i=2;i<=n;i++)
{
for(int j=i;j>=2;j--)
{
if(a[j]<a[j-1])
swap(a[j],a[j-1]);
else
break;
}
}
时间复杂度：
-
最好情况：O(n)（序列已经有序）
-
最坏情况：O(n^2)（序列是倒序排列的）
-
平均情况：O(n^2)
桶排序
桶排序（Bucket Sort）：
桶排序的思想是若待排序的值在一个明显有限的范围内（整型）时，可设计有限个有序桶，待排序的值装入对应的桶（当然一个桶内可以装入若干个值），桶号是待排序的值，顺序输出各桶的值，将得到有序的序列，具体的排序过程如下：
-
确定桶的数量和范围
-
将要排序的数据当作小旗分配到各个桶中
-
遍历所有的桶
-
如果桶中有小旗，则看桶中有几面小旗，有几面输出几次桶的下标
注意：桶排序也可以用于去重，在第四步中，我们只要判断桶中有小旗即输出桶的编号即可，不需要看里面具体有几面小旗。
桶排序实现过程图：
桶排序实现代码：
int n, a, b[11]={0}; //桶数组
for(int i=1; i<=n; i++){
cin>>a; //输入n个待排数据
b[a]++; //在对应编号的桶中插小旗
}
for(int i=1; i<=10; i++){ //遍历所有桶
while(b[i]>0){ //判断桶中是否有小旗
cout<<i<<" "; //输出桶的编号，即待排数据
b[i]--;
}
}
时间复杂度：
-
O(n+m)
题目环节
今天的题都挺简单的（雾
1. 插入排序（打印中间过程）
题目ID：6366必做题100分
最新提交：0 分
历史最高：0 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
插入排序基本思想是：每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
输入N个整数，将它们从小到大排序，输出插入排序的中间过程以及最后结果。
输入格式
第一行输入一个整数$NN$
第二行输入$NN$个整数$aiai$输出格式
输出$N−1N−1$行排序过程，每行$NN$个数。
样例
Input 1
5 5 4 3 2 1Output 1
4 5 3 2 1 3 4 5 2 1 2 3 4 5 1 1 2 3 4 5数据范围
1<=N<=1000,0<=ai<=1091<=N<=1000,0<=ai<=109
题解
在搞清楚这道题之前，我们先玩个扑克牌游戏
微软的纸牌大战相信大家都玩过，那如果我现在有这样的扑克牌
4行排序过程
5 4 3 2 1
你能用四行排序嘛？
这时候就要用到排序了
该题代码实现
#include<bits/stdc++.h>
using namespace std;
int a[1005];//变量a
int main()
{
int n , t;//变量n,t
int j;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
for(int i = 2; i <= n; i++)
{
t=a[i];
// 保存插入的数字
for(j = i-1; j >= 1 && a[j]>t ; j--)
{
a[j+1]=a[j];
}
a[j+1] = t;
for(int p = 1; p <= n; p++)
{
cout << a[p] << " ";
}
cout << endl;
}
return 0;
}
桶排序
\color{green}{巨难的一种排序，我不会时间复杂度awa}
\color{blue}{桶排序的名字也可以叫去重排序}
\color{blue}{题目建议：先做去重排序，简单~}
3. 去重排序
题目ID：9553必做题100分
最新提交：
Running
0 分
历史最高：
Running
0 分
时间限制: 4000ms
空间限制: 131072kB
题目描述
题目描述：
给定一个长度为n的正整数序列，请你去掉重复出现的数字，并以从小到大的顺序重新输出该序列。
输入格式：
第1行为一个整数n（不超过100000）。
接下来一行为n个不超过100000的正整数。
输出格式：
一行，无重复的序列。
样例输入 ：
4 1 4 4 3
样例输出 ：
1 3 4
约定：
1<=n<=100000
提示：
代码须上面在排序，下面在输出
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
int b;
cin >> b;
a[b]++;// 排序完毕
}
for(int i = 1; i <= 100000 ; i++)
{
if(a[i]!=0)
{
cout << i << " ";
}
}
return 0;
}
2. 桶排序
题目ID：8408必做题100分
最新提交：
Accepted
100 分
历史最高：
Accepted
100 分
时间限制: 4000ms
空间限制: 512000kB
题目描述
题目描述：
第一行输入一个正整数n。(n≤10000000)(n≤10000000)
接下来输入n个不比10000000大的正整数。
要求将他们从小到大依次输出。
样例输入：
样例输出：
damn码实现
1 1 2 4 5 6
#include <bits/stdc++.h>
using namespace std;
int a[10000005];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++)
{
int b;
cin >> b;
a[b]++; //排序
}
for(int i = 1; i <= 10000000; i++)
{
while(a[i]!=0)
{
cout << i << " ";
a[i]--;
}
}
return 0;
} ```
