给定输入数组 60,80,15,95,7,12,35,90,55 ，条件为选择第一个元素作为基准，现在给定输入有多少种排列方式，使得输出为快速排序的第一遍给出了相同的结果？
我尝试了一些排列，对于每个排列，我在第一遍中得到了相同的输出，但我无法理解这背后的逻辑，所以我更改了输入数组，然后尝试，我发现它给出了不同的结果，所以这种影响取决于输入数组对给定输入数组的某些特定排列给出相同结果的因素是什么，请概括这个术语。
最佳答案
如果我们想在第一次通过后保持相同的输出，我们必须不做的是改变将出现在枢轴同一侧的任何元素的顺序——也就是说，任意一对同时为 <= 60 的元素, 或两者 > 60 .这样做会改变它们在最终输出中出现的顺序。如果一个元素是 <= 60，则可以更改一对元素的顺序另一个是> 60 .
因此对于每个类别(<= 60 和> 60)，我们需要事先为其元素选择正确的顺序，并且不要违反此顺序。这意味着我们实际上正在做的是合并两个列表——一个包含所有项目 <= 60按照我们希望它们出现的顺序，另一个包含所有项目 > 60按照我们希望它们出现的顺序。也就是说，如果我们按顺序从一个列表中取出一些元素，然后按顺序从另一个列表中取出一些元素，并重复此操作直到两个输入列表都为空，那么取出的元素序列将在 1 次快速排序通过后生成所需的最终顺序。
那么，有多少种方法可以做到这一点？有 5 个号码 <= 60 :15、7、12、35、55 和 3 个数字 > 60 : 80, 95, 90。我们可以将生成合并序列所涉及的选择序列描述为 0 和 1 的序列，0 表示“从 <= 60 列表中取下一个元素”，1 表示“取下一个元素” > 60 列表中的元素”。那么我们想知道的是恰好包含 5 个 0 和 3 个 1 的 0 和 1 的不同序列的数量——或者等价地，从 0 序列的 5+3=8 个位置中选择 3 个的方法的数量变成1s。即8 choose 3 , 或 8!/3!5! = 56 .这对每个可能的有效合并只计算一次，因此有 56 种方式对 60、80、15、95、7、12、35、90、55 的最后 8 个元素进行排序，以在 1 次快速排序后生成特定的输出序列。
关于algorithm - 对于给定的输入数组，有多少种排列方式是可能的，以便所有排列方式在快速排序的第一遍中都能给出相同的输出？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34591025/