双路快排的问题
来源：3-5 三路快排partition思路的应用 Sort Color
讲武德的年轻人
2022-07-20
bobo老师，借这个地方请教您在“算法与数据结构”体系课中的双路快排的问题。在partition函数中，您实现的版本中，在while循环的前后都需要用swap函数来调整pivot元素的位置。我修改了一下partition函数，不需要进行这样的调整，相应的while循环也进行了修改，即当左指针i > 右指针j的时候，才退出循环 (您的版本中是i >= j退出)。这样，partition函数需要返回了一个int[]型数组，记录j和i的位置，在quickSort中，只需要对[l, j]和[i, r]分别进行快排就行了。我用了测试用例认为应该是对的？想请教您这算不算是一种常数级别的优化呢？当然，我觉得书写方法还是看个人习惯，本质并无优劣。
public class Solution {
public void sortIntegers2(int[] a) {
Random rnd = new Random();
quickSort(a, 0, a.length - 1, rnd);
}
private void quickSort(int[] a, int l, int r, Random rnd) {
if (l >= r)
return;
int[] p = partition(a, l, r, rnd);
quickSort(a, l, p[0], rnd);
quickSort(a, p[1], r, rnd);
}
private int[] partition(int[] a, int l, int r, Random rnd) {
int p = rnd.nextInt(r - l + 1) + l;
int pivot = a[p];
int i = l;
int j = r;
while (true) {
while (i <= j && a[i] < pivot)
i++;
while (i <= j && a[j] > pivot)
j--;
if (i > j)
break;
swap(a, i, j);
i++;
j--;
}
return new int[]{j, i};
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}1回答
-
逻辑是正确的。
我的测试结果，你的这版代码是比课程代码慢的，测试结果如下：（其中 QuickSort2Ways2 是你的这版代码）
我认为核心原因是：partition 中使用了 new。new 是很慢的一个操作。因为 Java 原生不支持返回多个函数值，对于不支持某类操作的语言，“绕弯子”达成这个目的肯定会牺牲性能。
我个人不是很推崇在某个语言中“绕弯子”以达到某个并不支持的语言特性；而更推崇“绕弯子”以不使用这个语言特性（毕竟它不支持）。这就是为什么，对于课程中的三路排序，我选择了不单独写 partition 函数，而将 partition 的过程和 sort 融合起来。因为对于三路快排，单独写 partition，就牵扯到了要返回两个函数值的问题。
但这个原则只是我个人的一个原则，也并无好坏。在很多时候，这个性能的影响也并不大。（比如你的这版代码，对 100 万级别的数据，差距在 ms 级别，完全在承受范围里。）所以根据自己的喜好来就好。
赞一下换一个方式去实现，相信你完全理解了这个算法的原理：）
==========
补充两点：
1）
这个问题在 C++ 或者 Python 中都不存在。Python 原生支持返回多个函数值；C++ 中可以使用传入引用的方式解决。注意：C++ 中的引用和 Java 中说的引用不是一个概念。说白了，是因为 C++ 支持对地址的操作，可以直接给出一个地址，去读写这个地址中的内容。所以我怀疑用 C++ 实现你这个思路，性能差距不大，但是懒得实验了。
我个人其实不喜欢纠结太过细碎的常数级“优化”：），因为其实对于现代编译器而言，很多这种“非常细碎的”常数级的优化，编译器就给做了，在上层代码上做这种工作，通常收益很低。
（但要注意，我强调的是“非常细碎的”常数级优化。但有的常数级优化不是如此。还是要具体问题具体分析。另外，在特定场合下，这类优化是有意义的，比如偏底层，或者低延迟高并发的场景。但是如果对性能这么敏感，或许本身不应该选择使用 Java 语言。我知道有人专门针对 C/C++ 语言研究这类优化，有个挺知名的 tech blogger，一时想不起来，在这方面做了很多工作。但很少听说 Java 工程师专门研究这种语言层面的细碎优化。）
2）
因为你特意强调了你的版本的代码是 i > j 退出，我的代码是 i >= j 退出，所以我怀疑你认为 i > j 是优于 i >= j 的。但实际上不是如此。虽然我们说 i >= j 是 i > j 或者 i == j，好像多了一个判断，但是在计算机底层，>= 是一个指令，用汇编表示就是 JGE，而 > 就是 JG。更往底层看，从数字逻辑的角度，JGE 就是一个电路。（JG 也是一个电路）
也就是逻辑上，i >= j 和 i > j || i == j 是一样的，但是性能上，这二者完全不同。前者的性能是优于后者的。而 i >= j 和 i > j 的性能是相同的。这一点看汇编码很容易看出来。（对于 Java 来说，看字节码。）
（但是！这里还是要有但是：对于现代编译器，是能直接把 i > j || i == j 优化成 i >= j 的。我用 C++ 实验了一下，是如此。）
继续加油！：）
012022-07-20
相似问题