告知快速排序的进度

Question

我目前正在对文件进行排序。目前，我使用heapsort来实现它，因为它很容易判断它的进度。我的意思是，有两个循环一个接一个，通过对两个循环中每一个循环的权重进行一些细微的调整，你就可以很好地估计当前的进度，并且显示一个进度条非常容易。

因为快速排序在大多数情况下比堆排序快，所以我想用它来代替，但我不确定如何判断它的进度。

Answer 1

有三个步骤：

• 将元素分成两个列表
• 排序左侧列表
• 排序右侧列表

您可以为每个步骤分配一部分在执行过程中必须填充的进度。假设总共有100%。假设两个列表的大小相同，步骤1获得20%，步骤2获得40%，步骤3也获得40%。这可以递归地继续。

问题是每一步的分数到底有多大。快速排序的平均时间复杂度为n*log(n)。假设对包含n元素的列表进行total = c*n*log(n)比较来排序。对大小为n*f (f < 1)的子列表进行排序需要进行以下数量的比较。

c*(n*f)*log(n*f) = 
c*(n*f)*(log(n)+log(f)) =
(c*n*log(n))*f + c*n*log(f)*f =
total*f + c*n*log(f)*f

因为f < 1，所以c*n*log(f)*f是负数。另一个子列表需要进行total*(1-f) + c*n*log(1-f)*(1-f)比较。因此，第一步需要进行以下数量的比较。

total - (total*f + c*n*log(f)*f) - (total*(1-f) + c*n*log(1-f)*(1-f)) =
total - total*f - total*(1-f) - (c*n*log(f)*f) - (c*n*log(1-f)*(1-f)) =
- (c*n*log(f)*f) - (c*n*log(1-f)*(1-f)) =
- c*n*(log(f)*f+log(1-f)*(1-f))

剩下的问题是：c的价值是什么？如果c是已知的，并且我没有犯错误，那么应该可以使用上面的公式计算这三个步骤的平均时间分数。