谈到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.常用排序算法列表

注意：

• 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