在这个公式中，继续这个问题，我认为如果我们假设n等于3，那么我们有一个类似A={4,5,7}的数组
根据这个公式，我们从n=3得到8，这意味着对于长度为3的数组，这是8的平均值，这太奇怪了！
- 在quickSort中到底发生了什么来获得平均比较8形式的数组这么短！而且发生了很多比较，那太糟糕了！是真的吗
我认为如果我们将数组与4步进行比较，会比使用quickSort快得多！
所以你的问题似乎是关于公式
E[X]=E[sum(i，1，n-1，sum(j，i+1，n，pi，j(]
在这张图片中，你上传了另一个问题。
这里E[X]表示期望值。简单地说：如果你多次进行实验(对随机数组排序(，X的平均值就会得到。
pi，j是在算法运行期间将项目i和项目j相互比较的机会。对于一个好的算法，碰巧项目i与项目k进行比较，项目k与项目j进行比较，这通常使得没有必要真正比较项目i和项目j。因此，算法越好，这种概率pi，j越低。
在最坏的情况下，例如，当n仅为3时，可以使pi，j=1。如果你计算公式，你会得到n=3，E[X]=3，因为(i，j(只有三个组合：(1,2(，(1,3(和(2,3(。这意味着对于n＝3，总是要进行3次比较。这对所有好的算法都是平等的，因为你不能利用item_i<项目_k<项目_j。
对于较大的n，有很多机会利用不需要显式测试所有item_i与所有item_j的优势。例如，可汗学院的文章中提供了详细的分析。