快速排序中常见中轴选择方法及实现代码(三)
初始数据： 2 2 2 2 2 2 2 2 2
分割后： 2 2 2 2 2 2 2 2 2
i→ ←j
第一次交换后： 2 2 2 2 2 2 2 2 2
i=1 j=6
第二次交换后： 2 2 2 2 2 2 2 2 2
i=2 j=5
第三次交换后： 2 2 2 2 2 2 2 2 2
3= i j=4
第四前交换后： 2 2 2 2 2 2 2 2 2
（与a[right-1]交换） 3= j i=4
虽然停止扫描并交换两个数据看起来并没有什么意义，因为所有的数据都是相等的，但是它却可以把数组平均地分为两个子数组。使快排达到最理想的情况，也就是说，我们是用交换来换来了效率，真是不可思议。
同时，在上面的分析中，我们是忽略了下标越界的检查的，从上面的分析中，我们可以看到，如果继续扫描（第1种情况），则需要在两个方向上做检查（这里所讲的所有算法都需要），它与我们之前所说的算法都非常的不一致。更加让人无法容忍的是，它会使快排变成最坏的情况。
在第2种情况中，虽然要交换元素，但是，却使快排以最理想的情况运行，并使算法与之前描述的完全一致。
总之，当遇到与中轴相等的元素时，应停止扫描。所以在我们的所有代码中，while循环中的条件都没有“=”。
极端的情况并不极端
上面的例子中，举出了一个非常极端的例子来说明遇到与中轴相等的元素时的处理方法。其实在现实中，这种情况并不极端。
试想要排序的数据有10,000个，其中有2,000个元素相等，并随机分布在数组中，也就是说平均在一个有10个元素的数组中有2个元素相等，这是非常普遍的情况。然而随着快排的进行，这2,000个相等的数，最终会被交换到一个连续的空间中，并出现了前面我们所说的极端情况。它就会成为我们算法的一个瓶颈。