Javajava算法
快速排序算法详解
快速排序是一种分治排序算法，通过选取基准值将数组划分为小于和大于基准的两部分，再递归排序子数组。文章介绍了递归实现思路及 Hoare 法、挖坑法、前后指针法等三种分区实现方式。分析了最坏情况下的时间复杂度 O(n^2) 与平均情况 O(nlogn)，以及空间复杂度。同时探讨了通过三数取中优化基准选择、在小区间使用插入排序防止栈溢出的优化策略。
快速排序是一种分治排序算法，通过选取基准值将数组划分为小于和大于基准的两部分，再递归排序子数组。文章介绍了递归实现思路及 Hoare 法、挖坑法、前后指针法等三种分区实现方式。分析了最坏情况下的时间复杂度 O(n^2) 与平均情况 O(nlogn)，以及空间复杂度。同时探讨了通过三数取中优化基准选择、在小区间使用插入排序防止栈溢出的优化策略。
左断开结果与右断开结果加上突兀根如何实现上一层的结果：
左断开有序+右断开有序加突兀根实现它比左部分都大、它比右部分都小就可以实现上一层的有序
书写时是突兀根先实现再递归实现左右断开结果：
书写时反着来先实现突兀根一个节点左边都比都比它小、右边都比它大，再用递归实现它断开的左右有序结果
突兀根从底层向上的回搭搭建二叉树：
当突兀根来到倒数第二层，当共有两个元素下突兀根去作为在上层的会去操作实现上层与下两层结果的表示连接时，左边、右边都是有序的结果，要实现它这层的有序结果要突兀根去操作实现为它的值比左边的都大、比右边的都小，操作具体实现为与 1 节点的值进行交换完成突兀根的实现操作，实现了突兀根所在的上层结果与下层左右两断开结果的连接表示，说明突兀根的实现操作在底层确实是能完成基础排序的
用二叉树递归实现排序实质上还是确定元素大小排在的数组位置递归完一个个来排的：
它排的位置左边都比它小、右边都比它大，它排的位置就是它在数组中排的大小位置，同时也确定着其它元素的相对大小排位位置，所以最后一层元素不去找基准排位置也是相对已确定下来的不用去排，所以 if(start == end)return 的
待排序元素 将其所在的待排序区域 调整划分成 以它为基准值 左边都比它小、右边都比它大的 两部分，并将它基准值 放入两部分的中间 就完成了此元素的排序
要去排的元素基准值 在待排序区域里面 任意取好后，在待排序区域左右两端 往内相遇铺路，右端往内铺 遇小不符 等停，左端往内铺 遇大换过去 交换，直至路头遇相等，此时路头位置 即基准元素 大小排在的位置，最后将基准元素交换过去 就完成了此元素的排序
private static int partition(int[] array, int left, int right) {
int i = left;
int j = right;
int pivot = array[left];
while (i < j) {
while (i < j && array[j] >= pivot) {
j--;
}
while (i < j && array[i] <= pivot) {
i++;
}
swap(array, i, j);
}
swap(array, i, left);
return i;
}
遇到与基准值相等大小的元素时 直接作为可行的 路过掉的，因为与基准值相等大小的元素 到最后排序在 此作为基准元素左右两边 都是可以的，所以此时排放在基准的左右两路 最后成两部分 都是可以的
基准为路的相遇点，要设置在属于左路的 因为最后基准交换 放到相遇点，基准值放到相遇点进去排序，相遇点的值 会交换放到第一个位置 即基准值的左边 需要是左路的部分，所以每轮的铺路都是 先进行右路的铺完到左边停 再进行左路的铺
要去排的元素基准值 在待排序区域内任意取好 并挖成坑，从左右端先左或右都行 往同向内 互相埋坑时 又挖坑地 推坑，推坑时始终是 一端路停在坑位 等着另一端路 往内铺路 挖到坑填上，所以左右路两端相遇时 一定遇在坑位，此位置就是 基准元素大小排序的位置 排好
private static int partition(int[] array, int left, int right) {
int i = left;
int j = right;
int pivot = array[left];
while (i < j) {
while (i < j && array[j] >= pivot) {
j--;
}
array[i] = array[j];
while (i < j && array[i] <= pivot) {
i++;
}
array[j] = array[i];
}
array[i] = pivot;
return i;
}
要去排序的基准元素 在待排序区间 任意选好后，定义 prev 与 cur 两前后指针，在排序区间的一端开始 同向往另一端 通过前后交换 动态维护 prev 及之前的区间为小路、cur 及到 prev 之前的区间为大路，这样当 cur 遍历完排序区间时，数组就被分好了 小路与大路两部分，再将基准元素交换放到 prev 指针位置处，一个基准元素 就在待排序区间排好了
private static int partition(int[] array, int left, int right) {
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array, cur, prev);
}
cur++;
}
swap(array, prev, left);
return prev;
}
基准排序的特点
递归的调用语句 算的是 调用里面执行的内容 (调用本身不算)，每次调用里面的 常量次数执行语句不算 (因为乘常量 常量可忽略的)，只算里面的 找调基准排的 非常量级的时间复杂度，算时间复杂度时就 一层层地算 每层里面所有递归调用的 时间和：
当元素完全顺序或完全逆序 排时，其呈现的二叉树结构为单分支的二叉树：
每一层都是 n 次遍历 只能排好 1 个元素，对应共有 n 层
最开始第一层时间是 n-1，再下层一个元素已经排好了 时间是 n-2，到最后一层时 最后一个元素被间接排好 递归调用函数里面是直接 return 的，所以一共有 n 层，n-1 层要去算时间，从上往下 每层的时间从n-1 减到 1 的等差数列和，最后大 O 算成的时间复杂度为O(n^2)，实际上的时间会比 n^2 少
当数组呈完全二叉树排列时：
每一层都是 n 次遍历 对应排好 2 的 n 层次方个 元素，对应共有 log(n) 层
因为每一层往下 已排好的元素越来越多，每一层中 所有基准区间总的去排的次数 会越来越少，到最后一层里 会有许多通过间接排就排好的元素 不需要去排的，但大 O 算时的最后结果是 偏大地算为 每层所有找基准排的时间为固定的 n，然后树的高度为 log(n)，时间复杂度为O(n*log(n))，实际上的时间会比它少很多（根节点高度视为 0 的）
因为递归调用的栈空间是动态复用的，所以空间复杂度为递归树的最大高度下算每层开辟的空间，因为这里每层递归函数里面开辟的空间是常量级的，所以大 O 算排序递归的空间复杂度就为递归调用栈的深度即二叉树的高度：
二叉树每层分支得越多装得越满：
在每个待排序区间虽然是可以任意取元素作基准，但我们尽量取大小排在中间的元素使生成的树分支更多树更矮时间复杂度与空间复杂度都更低，我们采用三数取中法，即得到待排序区间后，在区间的首中尾的三个数比较下拿更小值更有可能得使得取的基准值大小更偏中一点
当二叉树经上层已排好序节点能确定往下再分更多的更小的待排序区间去排序时，在二叉树下几层会分出很多的待排序子区间去排序，除了最底层的不需要去排序，其它在上层的每个区间的一次排序函数里都会执行到再调用下层的两个递归，在此时由于待排序子区间被分的特别多，会连续调用特别多的函数，一时间开辟特别多的函数栈帧，很有可能会造成栈溢出
因此在最后几层的许多待排序子区间去排序时，我们可以直接在倒数的上几层中就开始截断，不再往下通过分更多的子区间去基准排序了，直接在这一层将待排序区域用插入排序直接排好，因为经过上层的有很多元素已经排好了位置，剩下的待排序元素也是间接地比较有序的，用插入排序也可以高效地完成，就不用去开辟下层大量聚集的函数栈帧避免了栈溢出，降低了开辟空间的成本
但是由于快速排序原本最后一层的元素通过上层元素的排好序全部可以间接地不用去排直接排好的，改成了插入排序后时间复杂度可能会比原来的纯快速排序更高了
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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