Javajava算法
分治算法详解：快速排序、归并排序与快速选择
介绍分治算法的核心思想，涵盖快速排序及其优化（三指针法处理重复元素）、荷兰国旗问题、快速选择算法求第 K 大元素及最小 K 个数。同时讲解归并排序在逆序对计数及翻转对问题中的应用，对比暴力枚举与分治策略的时间复杂度差异，提供基于 Java 的代码实现细节与边界条件处理。
介绍分治算法的核心思想，涵盖快速排序及其优化（三指针法处理重复元素）、荷兰国旗问题、快速选择算法求第 K 大元素及最小 K 个数。同时讲解归并排序在逆序对计数及翻转对问题中的应用，对比暴力枚举与分治策略的时间复杂度差异，提供基于 Java 的代码实现细节与边界条件处理。
参考 LeetCode 题目 颜色分类
算法原理和移动零非常相似。
简述移动零的算法原理：
cur 在从前往后扫描的过程中，如果扫描的数符合 f 性质，就把这个数放到 dest 之前的区域；符合 g 性质则不管，直到 cur 遍历到最后，dest 指针就可以把数组划分成两个部分。
当 i 遍历结束数组后，整个数组就被排好序了，并且数组以 left，right 两个指针为分界线分成三个部分。
在遍历的过程中，整个数组会被划分成四个部分：
[0, left]：存储 0(left, i)：存储 1[i, right-1]：待扫描区域[right, n-1]：存储 2对遍历到的 nums[i] 的不同元素的分类处理：
nums[i] = 0
对于这种情况，只需要 swap(nums[left + 1], nums[i])，然后 left++, i++ 即可。要注意 nums[left+1]=1。
但是有一种极端情况，就是如果 i = left + 1，并且也符合 nums[i] = 0 的情况，我们依旧要执行 swap(nums[left + 1], nums[i])。虽然这种极端情况是变成自己和自己交换，但是处理方法不变：交换完成后，left++, i++。
nums[i] = 1
此时我们令 i++ 即可。
nums[i] = 2
对于这种情况，我们可以 swap(nums[i], nums[right - 1])，然后 right--。
此时需要特别注意，swap(nums[i], nums[right - 1]) 后，i 是不可以 ++ 的，因为 [i, right-1] 是待扫描区域，交换后，nums[i] 依旧是待扫描元素，所以如果是和 right - 1 交换的情况，i 是一定不可以 ++ 的。
循环终止条件
当待扫描区域已经没有元素，说明此时数组所有元素已经全部被扫描并且分好类了，结束循环即可，所以循环终止条件是 i != right。
指针初始化
根据算法原理，为了保证 left 指向 0 区域的最右边，right 区域指向 2 区域的最左边，我们交换元素是不会让 nums[left]，nums[right] 亲自和 nums[i] 进行交换的。所以我们的指针初始化的值如下：
left = -1right = n
这样的操作是为了避免漏掉对 nums[0]，nums[n - 1] 的扫描。编写代码
public void sortColors(int[] nums) {
int left = -1;
int right = nums.length;
int i = 0;
while (i < right) {
if (nums[i] == 0) {
swap(nums, ++left, i++);
} else if (nums[i] == 1) {
i++;
} else {
swap(nums, i, --right);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
报错原因：交换元素的方法不对；并且初始化 left，和 right 的操作没有处理好，会漏掉对 nums[0]，nums[n - 1] 的扫描。
参考 LeetCode 题目 使用快速排序来排序数组
解法：原始快速排序 原始快速排序的方法最核心的步骤，就在于根据基准元素进行数据划分的过程，这个步骤的名字是 partition。 但是，如果使用快速排序的数组有重复元素，那么快排的时间复杂度就会退化。
解法：用'数组分三块'的思想实现快速排序 这是基于原始快速排序的优化策略，用于应对快速排序的数组有大量重复元素的情况，从对数组分成两块划分为分成三块。 在数组出现大量重复元素时，通过把数组分成三段，可以把时间复杂度从 O(N^2) 降到 O(N)。
分类讨论 我们通过递归不断对划分的小区域排序，最终得到排好序的数组。
优化：用随机的方式选择基准元素 如果要想让快排的时间复杂度趋于 O(N*logN)，就需要随机地选择基准元素。随机选择基准元素，就是给我们一个数组，我们要等概率地返回区间上的任意一个数。
编写代码
准备工作 传入要排序的左区间和右区间： 如果 L >= R，则说明排序的区间要么只有一个，要么这个区间没有元素，说明整个数组已经排序完毕。
随机生成基准元素 & 初始化下标
要记一下如何生成随机数下标，以及要特别注意这里的初始化 left != -1，right != nums.length。
把数组分三块
[left + 1, right - 1] 这块区域用于存与生成的随机基准元素值相同的元素，并且以这块区域为基准，把其他数组元素分到这三块区域对应的区域。
可以记一下这个 partition 的过程，这是快排的核心逻辑。
[L, left] & [right, R] 进行排序
根据 nums[i] 与 key 的大小关系，把所有元素放到 [left + 1, right - 1] 的两边（两边还是乱序的），再对两边区域进行递归排序即可。
参考 LeetCode 题目 数组中的第 K 个最大元素
解法：基于快排实现快速选择算法
快速排序 Partition 本题是要找出数组中第 K 大的元素 kthLargest，那么我们可以根据基准元素，来判断 kthLargest 是落在上面三个区域的哪一个区域，然后对这个区域进行继续进行 Partition，继续找 kthLargest。
根据 K 的值分情况讨论，确定 kthLargest 的区间位置 我们先分别设三个区间的元素个数。
处理细节问题 解释特殊情况下的边界处理。
编写代码
先根据快排 partition 原理，把数组分三块
根据 k 的值来决定递归三块中的哪一块区域
参考 LeetCode 题目 最小的 k 个数
解法一：直接排序 时间复杂度 O(N * logN)
解法二：使用大根堆 (求最小的前 K 个数) 时间复杂度 O(N * logK)
解法三：快速选择算法 时间复杂度趋于 O(N)，因为是随机选择基准元素。
对 K 的值分类讨论
(1) a > k
(2) b >= k
这种情况我们直接返回前面两个区域的前 k 个小的元素即可，不用关心 [L, right] 区间的顺序。
(3) k > b+c
通过这三种情况，我们就能明显的感受到快速选择排序是最优的解法。比如第三种情况，此时 [L, right] 区间是没有排序的，但是我们依旧已经找到了最小的 k 个元素的一部分；而其他两种情况都是要对数组的每一个元素进行排序。
编写代码 我们是对 nums 的前 k 个元素进行排序，然后把 nums 的前 k 个元素赋值给 ret，然后返回。 报错原因：粗心导致 left & right 指针的初始值写错了。
参考 LeetCode 题目 归并排序
当数组块被分成每一块都只有一个元素，分块结束；用双指针合并两个有序数组；归并排序的决策树非常像二叉树的后续遍历 (左右根)，而快排则类似前序遍历 (先对数组整体粗糙分一遍，再去两边区域细分)。
参考 LeetCode 题目 使用归并排序来排序数组
int[] nums, tmp;
public int[] sortArray(int[] _nums) {
nums = _nums;
tmp = new int[nums.length];
mergeSort(0, nums.length - 1);
return nums;
}
public void mergeSort(int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(left, mid);
mergeSort(mid + 1, right);
int cur1 = left;
int cur2 = mid + 1;
int i = 0;
while (cur1 <= mid && cur2 <= right) {
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
for (int j = left; j <= right; j++) nums[j] = tmp[j - left];
}
把 tmp 设置为全局，就不用在每次递归时，创建一个新的 tmp，减少时间开销。
参考 LeetCode 题目 数组中的逆序对
解法一：暴力枚举 固定其中一个数，在这个数后面区间找比这个数小的数，来构成一个逆序对；使用两层 for 循环即可，但是会超时。
解法二：归并排序
算法原理 本质还是暴力枚举，逆序对个数 = a + b + c。
(1) 左半部分 + 右半部分 + 一左一右
(2) 左半部分 + 左排序 + 右半部分 + 右排序 + 一左一右 + 排序 对左右两边排好序，再一左一右挑数组成逆序对，并不影响结果。
本题为什么可以利用归并排序解决问题？ 我们在找出左右两边的逆序对个数时，先对两边排序再一左一右，会非常快。
一左一右查找逆序对策略优化 我们在之前找左右两边区域的所有逆序对时，就刻意地对左右两边进行排序，找完左右两边的逆序对时，nums 的两边区域的顺序已经被排序成升序，此时我们需要一左一右寻找逆序对。
策略一：判断 nums[cur1]>nums[cur2] + 升序 统计一左一右逆序对的固定策略：固定 cur2，只要 cur1 一移动到 nums[cur1]>nums[cur2] 位置，就统计符合要求的区间的元素个数，cur2++。 假设我们固定 cur2，要在左边找有多少个比 nums[cur2] 大的元素。 令 cur1 在左边区域中从左到右扫描，找出第一个 nums[cur1] > nums[cur2] 的 cur1。
(1) nums[cur1] <= nums[cur2] 我们直接让 cur1++，并且为了让数组有序，我们要把 nums[cur1] 放入辅助数组中，方便后续排序，继续往后找即可。
(2) nums[cur1] > nums[cur2] 出现这种情况，对于两边升序区域，当 nums[cur1] > nums[cur2]，说明此时 cur1 指向的元素，是左边区域第一个比 nums[cur2] 大的元素；cur1 后面所有元素都比 nums[cur2] 大。也因为是升序排序，在 cur1 一走到第一个合法位置时，ret += mid - cur1 + 1 即可。本轮 cur2 的所有能拿到的逆序对就已经统计好了，此时 cur2++ 即可。
如果策略一使用降序排列会出现的问题 对于降序排序，我们依旧是需要固定 cur2。我们依旧需要采取【只要 cur1 一移动到 nums[cur1]>nums[cur2] 的位置，就统计符合这个要求的区间的元素个数】的策略。如下图的情况：因为是降序排序的，所以 cur2 不能因为 nums[cur1]>nums[cur2] 就马上++，还必须看下一个 cur1 能否满足 nums[cur1]>nums[cur2]。因为采取了【只要 cur1 一移动到 nums[cur1]>nums[cur2] 的位置，就统计符合这个要求的区间的元素个数】的策略，因此就会造成大量的重复计算。cur1 一移动，判断是否大于 cur2，如果判断成立，马上就让 ret += cur1 - left + 1，所以会出现多次重复计算。所以使用策略一，在排序数组时不能用降序，避免大量重复计数，所以只能用升序。
策略二：nums[cur1]<nums[cur2] + 降序 统计一左一右逆序对的固定策略：固定 cur2，只要 cur1 一移动到 nums[cur1]<nums[cur2] 位置，就统计符合要求的区间的元素个数，cur2++。
编写代码
策略一 + 升序 准备工作及主逻辑。
策略二 + 降序
参考 LeetCode 题目 计算右侧小于当前元素的个数
这道题的本质，还是类似于求逆序对的个数。
解法：归并排序（左半部分 + 左排序 + 右半部分 + 右排序 + 一左一右 + 排序）
一左一右策略：nums[cur1] < nums[cur2] + 降序（上一题策略二）
nums[cur1] <= nums[cur2]，cur2++；修改对应的辅助数组；nums[cur1] > nums[cur2]，把 nums[cur1] 对应 ret[] 下标的元素加上 right - cur2 + 1；修改对应的辅助数组。
处理细节问题 我们要找到 nums[cur1] 对应 ret[] 的对应下标，因为我们排序的时候，下标已经乱了。 如果我们使用哈希表来设置 <nums 元素 , ret 下标> 的映射，如果 nums 有重复元素，哈希表无法存储重复元素，就无法解决下标混乱的问题。 所以我们设置与 nums 同等规模的数组 index[]，表示 nums 未排序时元素的原始下标。 不管 nums[] 因为排序，里面的元素怎么移动，index 对应的元素绑定移动。 那如何让 nums[] 和 index[] 绑定移动呢？我们需要创建两个辅助数组 tmp，来让它们同步移动。 最后，让 ret[index[i]] += right - cur2 + 1 即可。
编写代码 准备工作及核心逻辑。 报错原因：对于降序排序的一左一右操作不熟练，判断条件写错了。
参考 LeetCode 题目 翻转对
直接插入排序
选择排序
**冒泡排序
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online