Javajava算法
快速排序与归并排序的非递归实现
本文介绍了快速排序和归并排序的非递归实现原理及代码。快速排序通过栈模拟递归过程，利用分区函数 partition 确定基准元素位置；归并排序通过迭代方式合并有序子数组，使用 gap 控制合并长度。此外还总结了 Java 中 List 接口 sort 方法和 Collections 工具类 sort 的使用场景及 Comparator 接口的应用。
本文介绍了快速排序和归并排序的非递归实现原理及代码。快速排序通过栈模拟递归过程，利用分区函数 partition 确定基准元素位置；归并排序通过迭代方式合并有序子数组，使用 gap 控制合并长度。此外还总结了 Java 中 List 接口 sort 方法和 Collections 工具类 sort 的使用场景及 Comparator 接口的应用。
（在区间内进行基准排序时，默认以区间第一个元素为待排序元素）
用基准排序把每一个元素在对应已知的待排序范围排好，因为每排好一个元素，此元素排序位置确定且其排出的左小右大性质能缩小剩余的元素的待排序范围区域，所以每当一个元素排好后，其余元素对应的已知待排序范围就会发生变化，所以元素所在的待排序区域是经过动态变化来的。
public static void quickSortNonR(int[] array) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = array.length - 1;
int pivot = partition(array, left, right);
if (pivot - 1 > left) {
stack.push(left);
stack.push(pivot - 1);
}
if (pivot + 1 < right) {
stack.push(pivot + 1);
stack.push(right);
}
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
pivot = partition(array, left, right);
if (pivot - 1 > left) {
stack.push(left);
stack.push(pivot - 1);
}
if (pivot + 1 < right) {
stack.push(pivot + 1);
stack.push(right);
}
}
}
// 基准排序挖坑法实现
private static int partition(int[] array, int left, int right) {
int key = array[left];
while (left < right) {
while (left < right && array[right] >= key) {
right--;
}
// right 下标元素一定比 key 小
array[left] = array[right];
while (left < right && array[left] <= key) {
left++;
}
// left 下标元素一定比 key 大
array[right] = array[left];
}
array[left] = key;
return left;
}
利用栈的动态进出存储删取管理这些动态区间。
partition 方法是默认拿待排序区间的第一个元素为基准完成该元素在待排序区间内排好的。
说明剩下的左边的待排序区域至少有两个元素，还是需要去进行基准排序的。
一轮轮去有序数组 gap 的两两合并，去合并的有序数组单位会越来越大，直到最后一次两两合并后成的是整体数组的一个有序数组，数组就整体排好序了。
public static void mergeSortNor(int[] array) {
int gap = 1;
while (gap < array.length) {
for (int i = 0; i < array.length; i += 2 * gap) {
int left = i;
int mid = left + gap - 1;
int right = mid + gap;
if (mid >= array.length) {
mid = array.length - 1;
}
if (right >= array.length) {
right = array.length - 1;
}
merge(array, left, right, mid);
}
gap *= 2;
}
}
private static void merge(int[] array, int left, int right, int mid) {
int s1 = left;
int s2 = mid + 1;
int[] tmpArr = new int[right - left + 1];
int k = 0;
// 证明两个区间都同时有数据的
while (s1 <= mid && s2 <= right) {
if (array[s2] <= array[s1]) {
tmpArr[k++] = array[s2++];
} else {
tmpArr[k++] = array[s1++];
}
}
while (s1 <= mid) {
tmpArr[k++] = array[s1++];
}
while (s2 <= right) {
tmpArr[k++] = array[s2++];
}
// tmpArr 里面一定是这个区间内有序的数据了
for (int i = 0; i < tmpArr.length; i++) {
array[i + left] = tmpArr[i];
}
}
每轮去两两合并的单有序数组的元素个数，最开始的单位有序数组长度是 1。
一轮中往后继续去合并下一对的两 gap 有序数组。
一轮全部两两合并完后 gap 单位有序数组长度已翻倍。
gap >= array.length 时，继续去有序数组合并也都只有一个靠前的左数组 (整体数组)，去合并也是没有变化了，且其实在 gap >= array.length 之前一定有最后一次的两两合并成整体有序数组的了。
i < array.length，再进来的 left 是一定是 left < array.length 的。
实现了 List 接口的 ArrayList、LinkedList、Stack 都可调用 List 接口继承下来的 sort 方法直接进行排序：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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