C++快速排序中Lambda随机选基准导致性能骤降问题排查

哇，这性能落差也太夸张了——从0.012秒跳到15秒，绝对不是Lambda本身的锅，大概率是你用Lambda实现基准选择时踩了某个关键的坑。我来帮你捋捋最可能的原因：

1. 随机数生成器被重复初始化（最可能的元凶） #

如果你的Lambda表达式里每次都新建一个Random实例来生成基准索引，那麻烦就大了。举个例子，你可能写了类似这样的代码：

quickSort(strList, (arr) -> new Random().nextInt(arr.length));

Java里的Random默认用系统当前时间作为种子，短时间内连续创建多个Random实例的话，它们的种子会高度重复，导致生成的随机数几乎完全一样。这就意味着你的快排每次都选同一个位置的元素当基准——比如每次都选第一个元素。

这种情况下，快排会直接退化成**O(n²)**的时间复杂度。25000个元素的话，O(n²)就是6亿多次操作，和原来的O(n log n)（大概25000*15≈37万次操作）比，性能差几百倍都很正常，15秒完全说得通。

怎么修复？ #

把Random实例提前创建好，让Lambda捕获这个已有的实例，而不是每次都新建：

Random rand = new Random();
quickSort(strList, (arr) -> rand.nextInt(arr.length));

这样每次调用Lambda都会复用同一个随机数生成器，生成的索引是真正随机的，快排就能回到正常的O(n log n)性能。

2. 其他可能的小概率原因 #

• Lambda的捕获逻辑有额外开销？：别担心，Lambda的调用开销极小，完全不可能导致这么大的性能差距，这个可以直接排除。
• 基准索引计算错误？：比如Lambda返回的索引超出数组范围，但这种情况会直接抛出ArrayIndexOutOfBoundsException，而不是变慢，所以也不符合你的情况。

验证方法 #

你可以先手动打印几次Lambda返回的基准索引，如果发现大部分甚至全部都是同一个值，那就能实锤是随机数生成器重复初始化的问题了。

内容的提问来源于stack exchange，提问作者Jakemathbad