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

java 算法之归并排序详解

一、思想

归并排序：将一个数组排序，可以先（递归地）将它分成两半部份分别排序，然后将结果归并起来；

二、概念

归并：将两个有序的数组归并成一个更大的有序数组；

三、特点

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

缺点：需要额外的空间和N成正比；

四、实现方法

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

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

五、代码

/** 
 * 归并排序 
 *  
 * @author pengcx 
 *  
 */  
public class Merge extends Sort {  
  /** 归并所需的辅助数组 */  
  private static Comparable[] aux;  
  
  public static void main(String[] args) {  
    String[] a = { "d", "a", "w", "b", "q" };  
    Merge.sort(a);  
    show(a);  
  }  
  
  public static void sort(Comparable[] a) {  
    aux = new Comparable[a.length];  
    sort(a, 0, a.length - 1);  
  }  
  
  /** 
  * 排序数组的a[lo]至a[hi]元素 
  *  
  * @param a 
  *      数组a 
  * @param lo 
  *      最小元素位置lo 
  * @param hi 
  *      最大元素位置hi 
  */  
  private static void sort(Comparable[] a, int lo, int hi) {  
    if (hi <= lo) {  
      return;  
    }  
  
    // 计算数组中间位置  
    int mid = 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 
  */  
  public static void merge(Comparable[] a, int lo, int mid, int hi) {  
    int i = lo, j = mid + 1;  
  
    for (int k = lo; k <= hi; k++) {  
      aux[k] = a[k];  
    }  
  
    for (int k = lo; k <= hi; k++) {  
      // 如果左边的元素用尽，取右边的元素  
      if (i > mid) {  
        a[k] = aux[j++];  
      }  
      // 如果右边的元素用尽，取左边的元素  
      else if (j > hi) {  
        a[k] = aux[i++];  
      }  
      // 如果右半边的当前元素小于左半边的当前元素，取右半边元素  
      else if (less(aux[j], aux[i])) {  
        a[k] = aux[j++];  
      }  
      // 如果右半边的当前元素大于等于左半边的当前元素，取左半边元素  
      else {  
        a[k] = aux[i++];  
      }  
    }  
  }  
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# java # 归并排序 # 归并排序详解 # 归并排序实例 # java二路归并排序示例分享 # java实现归并排序算法 # Java经典排序算法之归并排序详解 # Java 归并排序算法、堆排序算法实例详解 # java 中归并排序算法详解 # Java分治归并排序算法实例详解 # java 排序算法之归并排序 # Java算法之归并排序举例详解 # 递归 # 成正比 # 更大 # 所需 # 而不 # 希望能 # 将它 # 谢谢大家 # 所需要 # 先将 # 中移动 # 组中 # 长度为 # 后半部 # 前半 # strong # class # pengcx # author # brush

返回目录在线咨询

上一篇：无极做网站优化,无极优惠券怎么用？
下一篇：使用VPS建站时，如何优化网站的加载速度？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

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

您的项目需求