c++ - 如何生成用于测试快速排序最佳案例的数组？

Question

我想测试 quickSort 的时间复杂度，但我不知道如何生成数组来测试最佳情况。我的 quickSort 版本将数组的最后一个元素作为枢轴。

标签： c++algorithmsortingtime-complexityquicksort

Answer 1

假设所有数组元素都不同，那么如果您总是选择最小或最大元素，那么显然会遇到最坏的情况。这将为您提供最差的递归深度和最大的比较次数。

但在最坏的情况下，您还需要进行多次交换。检查当最后一个元素最小或数组中最大元素时，您的快速排序实现移动了多少元素。决定什么是最坏的。然后排列数组中的数字，使每个子数组中的最后一个元素始终是最坏的情况。