擅长:python、mysql、java
<p>我找到了一个更容易实现的方法。(正如Jon Bentley在他的《编程珍珠》(Programming pearls)一书中提到的,Lumoto的方法很简单)。在</p>
<p>其思想是在扫描过程中保持不变,即在任何时候小于轴的元素被放在最左边的部分,而等于轴的元素放在该部分的旁边,大于轴的元素放在最右边。剩下的部分是那些元素还没有被检查过。在</p>
<p>这些部分由i,k,j所限定。当我们检查一个元素时,如果它等于轴,我们就前进到下一个元素,如果它小于轴,我们可以将它与“相等”部分上的第一个元素交换,这样就可以恢复不变量。否则,我们需要在更大的区域前继续与最后一个交换。在</p>
<pre><code>/*
* Another 3-way partition ternery quick sort based on N. Lomuto's method.
* Invariant: ... less ... | ... equal ... | ... ? ... | greater |
* i k j
*/
void qsort3(Key* xs, int l, int u) {
int i, j, k; Key pivot;
if (l < u - 1) {
i = l; j = u; pivot = xs[l];
for (k = l + 1; k < j; ++k) {
while (pivot < xs[k]) { j; swap(xs[j], xs[k]); }
if (xs[k] < pivot) { swap(xs[i], xs[k]); ++i; }
}
qsort3(xs, l, i);
qsort3(xs, j, u);
}
}
</code></pre>
<p>我用100000个元素对标准库中的qsortapi测试了这个程序。在</p>