2yexr

书上说到优化快速排序是修改“一次划分”算法，在指针high减1和low增1的同时进行冒泡操作，同时附设两个布尔型变量分别指示low和high在从两端向中间的移动过程中是否进行过交换记录的操作，若low从低端向中间的移动过程中没有进行交换记录的操作，则不再需要对低端子表进行排序，类似high指针也是如此。  
这样划分可以进一步改善快速排序的平均性能。  
对书上的说明不太明白  希望有人可以解释下  有算法或代码说明更好  谢谢  
 
---------------------------------------------------------------  
 

首先要了解快速排序的缺点，在无序数据中，快速排序有很好的效果。但在对于数据存在有序、反向有序及主次有序的形态时，快速排序都存在引起退化到二次行为的严重缺陷！  
 
由于这个缺点，你的这个改进算法是在排序的前期进行了数据有序与否的检查，尽量缩短数据交换的次数！而快速排序一种真正的改进算法是单个排序，算法思想如下：(以一把硬币为例)  
 
1、把硬币倒成一堆；  
2、检查硬币堆是否已经有序；如果无序，则：  
3、搅拌硬币并从硬币堆中抓取一些硬币。挑出这批硬币中的中值硬币；  
4、把面值更大的硬币放在右边的硬币堆；  
5、把面值更小的硬币放在左边的硬币堆；  
6、如果硬币对很小，使用折半插入算法，否则：  
7、对于每一堆硬币，返回步骤2，直到所有硬币全部排序完毕。由于把大面值硬币放在右边，而把小面值硬币放在左边，因而当每堆只有一枚硬币时，所有硬币完全有序。