java 归并排序的实例详解

java 归并排序的实例详解

归并排序

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

归并操作的过程如下：

•  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
•  设定两个指针，最初位置分别为两个已经排序序列的起始位置
•  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
•  重复步骤3直到某一指针到达序列尾
•  将另一序列剩下的所有元素直接复制到合并序列尾
  

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的通用排序算中的上好的选择。

以上使用java 使用归并排序的简单实例，有关java算法知识本站还有很多，大家可以搜索，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！