谈到Java中的十大排序算法,你或许并不陌生,像什么选择排序,冒泡排序,插入排序,但是后面的几个排序算法就不太清楚了,那么其余的排序算法还包括哪些,它们的时间复杂度,稳定性如何?大O分析法又是什么?这就是我们今天所要学习和讨论的内容!
1.1 数据结构和算法
算法,数据结构
O:时间复杂度
1.1.1 什么是数据结构
数据结构 (Data Structure)
存储数据的不同方式
| 2 | 4 | 7 | 1 | 6 | 5 | 3 |
数组:使用连续的小格(地址),每一个小格大小(存储单元大小)都相等,使用int类型的整数,一个整数紧挨着一个整数排列
| 2 | --> | 4 | --> | 7 | --> | 1 | --> | 6 | --> | 5 | --> | 3 |
链表:每个小格(地址)除了存储自己的数据之外,还存放着指向下小格(地址) 一个箭头 (指针)
1.1.2 什么是算法 (algorithm)?
同一问题的不同解决方法
例如计算 1 + 2 + 3 + … + 99 = ? ,可以有多种解法,直接从1到99相加,或者1和99相加,2和98相加,依次类推
算法往往是针对特定数据结构的
- 在链表中的元素7和1之间插入一个新元素0
| 0 |
| 2 | --> | 4 | --> | 7 | ----> | 1 | --> | 6 | --> | 5 | --> | 3 |
| 2 | --> | 4 | --> | 7 | | 0 | --> | 1 | --> | 6 | --> | 5 | --> | 3 |
| 2 | --> | 4 | --> | 7 | --> | 0 | --> | 1 | --> | 6 | --> | 5 | --> | 3 |
先让元素0指向元素1,然后再让元素7指向元素0
- 在数组中的元素7和1之间插入新元素0
| 2 | 4 | 7 | 1 | 6 | 5 | 3 |
| 2 | 4 | 7 | 0 | 1 | 6 | 5 | 3 |
创建一个新数组,将原数组复制一份到新数组中,在新数组的元素7和元素1之间插入新元素0
1.1.3 如何测算算法的优劣
时间测算
- 计算算法时间差
- 幅度不够循环来凑
空间测算
1.1.4 Big O标记法
1.什么是Big O?
Big O, 也叫大O标记法
2.什么是数据规模?
时间-问题 (数据)规模
- 不考虑必须要做的操作
循环、赋初值、程序初始化
- 不考虑常数项
2n–n
- 不考虑低次项
n^2 + n — n^2
3.简单案例说明
3-1 查鸡蛋问题
一小篮鸡蛋,原本有七八个鸡蛋,查鸡蛋数量需要1s;如果鸡蛋的数量增加到一百个,计算鸡蛋个数的时间也随之增长,变为1min (时间复杂度会随着数据规模扩大而相应变大);鸡蛋所占篮子的空间也随之增大,从一个小篮子变为一个大篮子 (空间复杂度也会岁数据规模扩大而随之变大)
3-2 访问数组和链表某个位置值
- 访问数组某个位置的值
假如想要去访问数组中某个下标的元素值,需要计算偏移量:这时需要计算时间复杂度,我们不考虑计算偏移量和数组初始化等必需要做的操作,只算随着规模扩大,时间发生了什么变化;如果随着数据规模扩大时间并没有发生任何变化,那么这个时候的时间复杂度我们称之为O(1) (O(1)表示一个常数,也就是随着数组的数据规模扩大,要查询某个下标值的时间都是固定的,没有任何变化)
-
访问链表某个位置的值
一般时间复杂度我们说的都是"最差"情况
假如要访问链表中的某个位置的元素值,查询第一个元素的时间复杂度是O(1),但如果要查询链表中的最后一个位置元素值,那么时间复杂度就变为了O(n),其实O(n) 也就是一个线性变化的射线 (也就是数学中的函数y=x在第一象限内的图像)
3-3 求数组平均数
如果要计算一个数组中所有元素的平均值,再不考虑计算偏移量和数组初始化等必要操作时,那么它的时间会随着数据规模的扩大而发生变化,因此时间复杂度为O(n)
总结:
- 使用Big O (大O标记法) 来表示时间复杂度
- 时间复杂度就是随着问题规模变化而变化的规律
- 用计算时间差的方式测算
- 数组和链表具体计算时时间复杂度会有所不同
1.2 排序问题
1.2.1 什么是排序问题?
将一串数字按照从大到小或者从小到大的顺序机型排序
1.2.2 常用的排序算法
1.常用排序算法列表
中文名称 | 英文名称 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|---|
选择排序 | Selection | n2 | n2 | n2 | 1 | In-place | 不稳定 |
冒泡排序 | Bubble | n2 | n2 | n | 1 | In-place | 稳定 |
插入排序 | Insertion | n2 | n2 | n | 1 | In-place | 稳定 |
堆排序 | heap | n log2 ^n | n log2 ^n | n log2 ^n | 1 | In-place | 不稳定 |
希尔排序 | Shell | n1.3 | n2 | n | 1 | In-place | 不稳定 |
归并排序 | Merge | n log2 n
|
n log2 n
|
n log2 n
|
n | Out-place | 稳定 |
快速排序 | Quick | n log2 n
|
n2 | n log2 n
|
nlog2 n
|
In-place | 不稳定 |
桶排序 | Bucket | n + k | n2 | n | n + k | Out-place | 稳定 |
计数排序 | Counting | n + k | n + k | n + k | n + k | Out-place | 稳定 |
基数排序 | Radix | n * k | n * k | n * k | n + k | Out-place | 稳定 |
注意:
- n是指数据规模,k是指桶的个数
- In-place表示线性时间比较类排序,即不占用额外内存;Out-place表示非线性时间比较类排序即占用额外内存
- 稳定是指,如果a原本在b的前面,并且a=b,排序之后a仍然在b的前面;不稳定是指,如果a原本在b的前面,并且a=b,排序之后a可能会出现在b的后面
- 共有10种排序,其中插入排序、堆排序、归并排序和快速排序重点记忆
- 最坏时间复杂度和最好时间复杂度不需要记忆
2. 排序算法巧记法
《忆排序 面试我最强》
选泡插,快归堆 希 桶计 基,
N方 N老 N一三,
对N加K N乘K,
不稳稳稳 不稳稳,
不稳 不稳 稳稳 稳!
好了,今天的初识十大排序算法到这里就结束了,欢迎大家学习和讨论!
参考视频链接:https://www.bilibili.com/video/BV14i4y1T7Af