计数排序

一、算法描述

1.1 核心思想

• 计数排序是桶大小为 1 的桶排序的一种特殊情况
• 由于桶大小为 1，所以桶内都是相同的值
• 桶内都是相同的值，无需桶内排序，只需要记录数据频率
• 最后排序时，按照数据频率将数据填充回原数组

1.2 细节解释

归并排序

一、算法描述

1.1 核心思想

• 二分，将数据二等均分，然后分别排序，再合并2个排好序的数据
• 递归，一直二等均分数据，直到无法分割后，才开始递归合并返回
• 整个二分和合并的过程类似于一棵二叉树，从下往上合并数据，先对子树排序，再合并成根节点

1.2 细节解释

冒泡和插入对比

一、比较次数

冒泡排序比较：

插入排序

一、算法描述

1.1 核心思想

• 数据分为已排序区间和未排序区间
• 插入都是从未排序区间取出元素，插入到已排序区间合适的位置中
• 插入已排序区间时，同时要保证已排序区间的有序性

1.2 细节解释

选择排序

一、算法描述

1.1 核心思想

• 数据分为已排序区间和未排序区间
• 从未排序区间中找到最小/最大的元素，放到到已排序区间的尾部
• 执行 n 轮后，所有未排序元素都会迁移到已排序区间中

1.2 细节解释

冒泡排序

一、算法描述

1.1 核心思想

• 每次操作只会影响相邻的 2 个元素
• 每轮冒泡至少让 1 个元素移动到它正确的位置（1 轮是指从头到尾操作一遍元素）
• 最多经过 n 轮冒泡后，所有元素都会被移到正确的位置

1.2 细节解释

快速排序

一、算法描述

1.1 核心思想

• 二分，选取一个分区值，将数据分割成 2 部分：小于和大于
• 递归，对小于大于两部分再排序，不断选点分割数据，直到无法分割为止
• 整个二分过程类似于一棵二叉树，从上往下排序，先确定根节点位置，再处理子树排序

1.2 细节解释

Happen-Before原则的借助

Happen-Before 原则可以保证变量的可见性，因此可以通过 “借助” 的方式，来间接地实现对无锁保护变量的安全性保护。

“借助” 技术，一般将程序次序规则和其他某个规则（比如监视器锁规则或者 volatile 变量规则）结合起来实现的。

这种 “借助” 技术，对于代码语句的顺序非常敏感，因此很容易出错，属于一种高级技术。

Java内存模型

一、什么是内存模型？

缓存一致性问题：

• 在多处理器系统中，每个处理器都有自己的高速缓存，而它们又共享同一主内存（Main Memory）
• 当多处理器对同一块主内存区域进行操作时，可能会导致各自的缓存数据不一致，这就是缓存一致性问题

并发问题来源

一、缓存带来的可见性问题

• 计算机中可以保存数据的地方有几个：寄存器、缓存、主内存
• 原始数据都保存在主存上，最初的读取和最终的写入，都是在主存上操作
• CPU 与主存之间存在缓存，每个 CPU 都有自己独立的的缓存
• 操作数据时，首先要将原始数据从主存中读取到 CPU 的缓存中，然后再对缓存的数据进行操作
• 单 CPU 下，一个线程对缓存的修改，对于另一个线程来说是可见的，因为只有一个缓存
• 多 CPU 下，线程可能运行在不同 CPU 上，操作的是各自不同的缓存，相互之间是不可见的