Java算法基础学习之初识排序算法

谈到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

上一篇:2021-01-16


下一篇:喜欢的抖音视频只能收藏,不能保存?一篇文章教会你使用Python下载抖音无水印视频