课堂知识点 学习重点
- 时间复杂度在算法当中需要注意的事项
- 插入排序算法介绍，插入排序的过程，插入排序的原理
- 桶排序算法介绍，桶排序的过程，桶排序原理
思考题
- 上节课的两个排序算法时间复杂度应该怎么计算? 写下你的思考:
- 上节课的选择排序和冒泡排序过程是怎么样的?写下你的思考:
知识点：
- 时间复杂度
OJ 后台编译器每秒大约执行 10^7 个基本运算，学会根据题目给定的 n 的范围来选择算法。
| 时间复杂度 | 建议不超过的 n 的范围 |
|---|---|
| O(logn) | long long 内都行 |
| O(n) | 10^7 |
| O(nlogn) | 10^5~5*10^5 |
| O(n2) | 1000~5000 |
| O(n3) | 200~500 |
| 2.插入排序与桶排序 |
插入排序
插入排序是一种简单直观的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。具体的排序过程如
- 从第一个元素开始，认为该元素已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果已排序的元素大于新元素，则将该元素移到下一位置
- 重复步骤 3，直到已排序的元素小于或等于新元素
- 将新元素插入到该位置后
- 重复步骤 2~5，直到排序完成
如图所示
2 10 12 5 6 原始数据
2 10 12 5 6 第一趟排序(
2 10 12 5 6 第二趟排序(
4 10 12 1 5 6 第三趟排序(
4 10 12 5 6 第四趟排序(
4 10 12 5 6 第五趟排序(
3 4 10 12 5 6 第六趟排序
- 确定桶的数量和范围
- 将要排序的数据当作小旗分配到各个桶中
- 遍历所有的桶
- 如果桶中有小旗，则看桶中有几面小旗，有几面输出几次桶的下标
注意：桶排序也可以用于去重，在第四步中，我们只要判断桶中有小旗即输出桶的编号即可，不需要看里面具体有几面小旗。
桶排序实现过程图:
注：logn 的计算方式：
logn 是以 2 为底的对数，表示将底数为 2 的指数幂变为 n 所需要的幂次，即 2^k=n，则 k=log_2n 此处表达的意思就是以 2 为底，n 的对数，可简写为 logn。
核心代码：
/插入排序/
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;
} }