java - 关于取模运算符的使用

Question

这是快速排序算法的一部分代码，但我真的不知道为什么它使用 rand() %n 请帮助我谢谢

Swap(V,0,rand() %n)  // move pivot elem to V[0]

Answer 1

它用于随机化快速排序以实现平均 nlgn 时间复杂度。

引用自维基百科:

What makes random pivots a good choice?

Suppose we sort the list and then divide it into four parts. The two parts in the middle will contain the best pivots; each of them is larger than at least 25% of the elements and smaller than at least 25% of the elements. If we could consistently choose an element from these two middle parts, we would only have to split the list at most 2log2n times before reaching lists of size 1, yielding an algorithm.