详解java 归并排序的实例

作者:kgmucom   在线用户:14
风之恋奇迹私服技术网是一家提供最新互联网编程技术网站

今天爱站技术频道小编为大家带来详解java 归并排序的实例,其实我们初学者要多多接触不同类型的程序知识,才能进行不断的进步,下面就跟随爱站技术频道小编的步伐来学习吧!

详解java 归并排序的实例

归并排序

       归并排序,指的是将两个已经排序的序列合并成一个序列的操作。 

归并操作的过程如下:

代码 

/** 
 * 归并排序 
 * 
 * @param ts 
 */ 
@SuppressWarnings("unchecked") 
public static <T extends Comparable<? super T>> void mergeSort(T[] ts) { 
 
  // 辅助空间 
  T[] tempArray = (T[]) new Comparable[ts.length]; 
 
  mergeSort(ts, tempArray, 0, ts.length - 1); 
} 
 
/** 
 * 递归 
 */ 
private static <T extends Comparable<? super T>> void mergeSort(T[] ts, T[] tempArray, int left, int right) { 
 
  if (left < right) { 
 
    int center = (left + right) / 2; 
 
    mergeSort(ts, tempArray, left, center); 
 
    mergeSort(ts, tempArray, center + 1, right); 
 
    // 左右合并 
    merge(ts, tempArray, left, center + 1, right); 
 
  } 
 
} 
 
/** 
 * 合并 
 */ 
private static <T extends Comparable<? super T>> void merge(T[] ts, T[] tempArray, int leftPos, int rightPos, int rightEnd) { 
  int leftEnd = rightPos - 1; 
  int temPos = leftPos; 
  int numElements = rightEnd - leftPos + 1; 
 
  while (leftPos <= leftEnd && rightPos <= rightEnd) 
    //比较放到辅助空间 
    if (ts[leftPos].compareTo(ts[rightPos]) <= 0) 
      tempArray[temPos++] = ts[leftPos++]; 
    else 
      tempArray[temPos++] = ts[rightPos++]; 
 
  while (leftPos <= leftEnd) 
    tempArray[temPos++] = ts[leftPos++]; 
 
  while (rightPos <= rightEnd) 
    tempArray[temPos++] = ts[rightPos++]; 
 
  //考回原数组,此处最好用System.arraycopy优化 
  for (int i = 0; i < numElements; i++, rightEnd--) 
    ts[rightEnd] = tempArray[rightEnd]; 
} 
 

 复杂度:O(n log n)

       比较操作的次数介于(n log n)/2和n log n - n + 1。 赋值操作的次数是(2nlogn)。

       归并算法的空间复杂度为:Θ(n) 

 稳定性:稳定 

以上就是详解java 归并排序的实例介绍,本站有很多关于java方面的知识,您可以搜索查阅,希望对您有所帮助,同时也感谢大家对爱站技术频道的支持。

提供最全面的奇迹sf开服版本和最新的奇迹私服开服技术信息,奇迹私服文库让每一位奇迹私服玩家找到自己需要的版本技术文章

上一篇:Spring Boot发送邮件详解

下一篇:java制作简单验证码功能

请发表您的评论