java 往word写入内容:9.9.3 快速排序优化（2）

来源：百度文库 编辑：中财网 时间：2024/04/29 19:29:29

9.9.3 快速排序优化（2）

3．优化小数组时的排序方案

对于一个数学科学家、博士生导师，他可以攻克世界性的难题，可以培养最优秀的数学博士，但让他去教小学生“1+1=2”的算术课程，那还真未必会比常年在小学里耕耘的数学老师教得好。换句话说，大材小用有时会变得反而不好用。刚才我谈到了对于非常大的数组的解决办法。那么相反的情况，如果数组非常小，其实快速排序反而不如直接插入排序来得更好（直接插入是简单排序中性能最好的）。其原因在于快速排序用到了递归操作，在大量数据排序时，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了一个大炮打蚊子的大问题。因此我们需要改进一下QSort函数。

  1. #define MAX_LENGTH_INSERT_SORT 7 /* 数组长度阀值 */  
  2. /* 对顺序表L中的子序列L.r[low..high]作快速排序 */  
  3. void QSort（SqList &L,int low,int high）  
  4. {  
  5. int pivot;  
  6. if（（high-low）>MAX_LENGTH_INSERT_SORT）  
  7. {/*当high-low大于常数时用快速排序*/  
  8. pivot=Partition（L,low,high）; /* 将L.r[low..high]一分为二，*/  
  9. /* 并算出枢轴值pivot */  
  10. QSort（L,low,pivot-1）; /* 对低子表递归排序 */  
  11. QSort（L,pivot+1,high）; /* 对高子表递归排序 */  
  12. }  
  13. else /* 当high-low小于等于常数时用直接插入排序 */  
  14. InsertSort（L）;  
  15. }

我们增加了一个判断，当high‐low不大于某个常数时（有资料认为7比较合适，也有认为50更合理，实际应用可适当调整），就用直接插入排序，这样就能保证最大化地利用两种排序的优势来完成排序工作。

4．优化递归操作

大家知道，递归对性能是有一定影响的，QSort函数在其尾部有两次递归操作。如果待排序的序列划分极端不平衡，递归深度将趋近于n，而不是平衡时的log2n，这就不仅仅是速度快慢的问题了。栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此如果能减少递归，将会大大提高性能。

于是我们对QSort实施尾递归优化。来看代码。

  1. /* 对顺序表L中的子序列L.r[low..high]作快速排序 */  
  2. void QSort1（SqList *L,int low,int high）  
  3. {  
  4. int pivot;  
  5. if（（high-low）>MAX_LENGTH_INSERT_SORT）  
  6. {  
  7. while（low{  
  8. pivot=Partition1（L,low,high）; /*L.r[low..high]一分为二,*/  
  9. /*算出枢轴值pivot */  
  10. QSort1（L,low,pivot-1）; /* 对低子表递归排序 */  
  11. low=pivot+1; /* 尾递归 */  
  12. }  
  13. }  
  14. else  
  15. InsertSort（L）;  
  16. }

当我们将if改成while后（见加粗代码部分），因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1赋值给low，再循环后，来一次Partition（L,low,high），其效果等同于“QSort（L,pivot+1,high）;”。结果相同，但因采用迭代而不是递归的方法可以缩减堆度而高体能栈深，从提高了整体性能。

在现实的应用中，比如C++、java、PHP、C#、VB、JavaScript等都有对快速排序算法的实现10，实现方式上略有不同，但基本上都是在我们讲解的快速排序法基础上的精神体现。

我们现在学过的排序算法，有按照实现方法分类命名的，如简单选择排序、直接插入排序、归并排序，有按照其排序的方式类比现实世界命名的，比如冒泡排序、堆排序，还有用人名命名的，比如希尔排序。但是刚才我们讲的排序，却用“快速”来命名，这也就意味着只要再有人找到更好的排序法，此“快速”就会名不符实，不过，至少今天，TonyHoare发明的快速排序法经过多次的优化后，在整体性能上，依然是排序算法王者，我们应该要好好研究并掌握它。11

注：10有兴趣可以想办法到网上下载阅读它们的源代码。

快速排序vc 求助C的快速排序！ 求助C的快速排序 快速启动栏无法排序 快速排序的循环算法 怎样用快速法进行排序？ 请用快速排序法对一个整型数组进行排序（数组元素为1到10） 快速排序法与希尔排序法的具体步骤 帮忙做一道题：关于冒泡排序与快速排序。 假如给你一个随机的数组,该怎么快速排序？（c语言） 一个多线程快速排序的程序调试 “快速启动”中图标排序问题 求快速排序法的C++代码 快速排序的定义怎样的？ 关于快速排序法的一个问题。 排序。随机生成若干个数据，程序将数据排序后输出，分别使用快速排序，希尔排序，冒泡排序算法进行排序。 二级C公共基础题中的插入排序,选择排序,快速排序,归并排序各有什么特点，具体是怎么回事？ java中用快速排序（排序算法应该是正确的），不报错，但执行起来不行。在elipse中执行的。 java中用快速排序（排序算法应该是正确的），不报错，但执行起来不行。在elipse中执行的。 谁会对C++中的排序算法,比如冒泡排序,插入排序,选择排序,快速排序等的MPI并行实现代码? 用快速分类算法给出数据（49，38，65，97，76，13，27，49）的第一趟排序过程 3忍强弱排序 排序（大到小） 排序。。。。。。。。