一聚教程网:一个值得你收藏的教程网站

热门教程

java 算法之归并排序详解及实现代码

时间:2022-06-29 01:35:02 编辑:袖梨 来源:一聚教程网

java 算法之归并排序详解

一、思想

归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来;  

二、概念

归并:将两个有序的数组归并成一个更大的有序数组;  

三、特点

优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比;

缺点:需要额外的空间和N成正比; 

 四、实现方法

将两个不同的有序数组归并到第三个数组中;

先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间; 

五、代码

 

 代码如下复制代码

/**

 * 归并排序

 * 

 * @author pengcx

 * 

 */ 

publicclassMergeextendsSort { 

  /** 归并所需的辅助数组 */ 

  privatestaticComparable[] aux; 

   

  publicstaticvoidmain(String[] args) { 

    String[] a = {"d","a","w","b","q"}; 

    Merge.sort(a); 

    show(a); 

  } 

   

  publicstaticvoidsort(Comparable[] a) { 

    aux =newComparable[a.length]; 

    sort(a,0, a.length -1); 

  } 

   

  /**

  * 排序数组的a[lo]至a[hi]元素

  * 

  * @param a

  *      数组a

  * @param lo

  *      最小元素位置lo

  * @param hi

  *      最大元素位置hi

  */ 

  privatestaticvoidsort(Comparable[] a,intlo,inthi) { 

    if(hi <= lo) { 

      return; 

    } 

   

    // 计算数组中间位置 

    intmid = lo + (hi - lo) /2; 

    // 排序数组a左边的元素 

    sort(a, lo, mid); 

    // 排序数组a右边的元素 

    sort(a, mid +1, hi); 

    // 合并数组a左边和右边的元素 

    merge(a, lo, mid, hi); 

  } 

   

  /**

  * 将数组a的a[lo]至a[mid]的元素与a[mid]至a[hi]的元素合并

  * 

  * @param a

  *      合并的数组a

  * @param lo

  *      最小数组元素lo

  * @param mid

  *      中间元素位置mid

  * @param hi

  *      最大元素位置hi

  */ 

  publicstaticvoidmerge(Comparable[] a,intlo,intmid,inthi) { 

    inti = lo, j = mid +1; 

   

    for(intk = lo; k <= hi; k++) { 

      aux[k] = a[k]; 

    } 

   

    for(intk = lo; k <= hi; k++) { 

      // 如果左边的元素用尽,取右边的元素 

      if(i > mid) { 

        a[k] = aux[j++]; 

      } 

      // 如果右边的元素用尽,取左边的元素 

      elseif(j > hi) { 

        a[k] = aux[i++]; 

      } 

      // 如果右半边的当前元素小于左半边的当前元素,取右半边元素 

      elseif(less(aux[j], aux[i])) { 

        a[k] = aux[j++]; 

      } 

      // 如果右半边的当前元素大于等于左半边的当前元素,取左半边元素 

      else{ 

        a[k] = aux[i++]; 

      } 

    } 

  } 

}

 

热门栏目