谈到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相加，依次类推
算法往往是针对特定数据结构的
? | 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
| 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
|