当前位置:   article > 正文

Java练习:分治法之合并排序(merge Sort)_java java 分治法 不同文件 合并排序

java java 分治法 不同文件 合并排序

返回 Java编程练习目录


分而治之(divide-and-conquer)是一种古老但实用的策略、普适性的问题求解策略。本质上,分而治之策略是将整体分解成部分的思想。

按照系统科学的观点,该策略仅适用于线性系统——整体正好对于部分之和

(两路)合并排序遵循分治法的三个步骤,其操作如下:

(1) 分解:将数组大致分成两半。例如将9个元素的数组划分成5+4两半。

(2) 排序:一般需要对子序列递归地再进行划分。极端地,子序列仅仅剩下一个数据,则子序列不需要排序。以突出前后两个步骤。实际程序,划分是有度的。

(3) 合并:将两个已排序的数据序列合并。

1.合并

[5.1.2 针对LinearList]的例程5-3归并(merging)算法,解决的问题:已知la和lb的元素非降序排列(前面的元素小于等于后面的元素),将la和lb合并为lc,且lc中的元素非降序排列。

  1. public static void merge(LinearList la, LinearList lb,LinearList lc){
  2. if(la==null || lb==null|| lc==null){
  3. throw new java.lang.NullPointerException();
  4. }
  5. lc.clear();
  6. int i=0; int j=0;
  7. while( (i<=la.length())&&(j<=lb.length()) ){
  8. int ai=la.getAt(i);
  9. int bj=lb.getAt(j);
  10. if(ai<=bj){
  11. lc.add(ai);
  12. i++;
  13. }else{
  14. lc.add(bj);
  15. j++;
  16. }
  17. }
  18. while( i<=la.length() ){
  19. int ai=la.getAt(i++);
  20. lc.add(ai);
  21. }
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/716313
推荐阅读
相关标签
  

闽ICP备14008679号