java 归并排序的实例详解_网络技术_宿州市腾雀网络科技有限公司

java 归并排序的实例详解

发布时间 - 2026-01-11 02:19:58 点击率：次

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算法知识本站还有很多，大家可以搜索，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# java # 归并排序 # 归并排序详解 # 排序 # Java 十大排序算法之归并排序刨析 # 图解Java排序算法之归并排序 # java 排序算法之归并排序 # JAVA十大排序算法之归并排序详解 # Java分治归并排序算法实例详解 # java 中归并排序算法详解 # Java 详细讲解分治算法如何实现归并排序 # 递归 # 则是 # 希望能 # 下一 # 使其 # 分别为 # 谢谢大家 # 指的是 # 还有很多 # 最好用 # 次元 # 最初 # ts # param # SuppressWarnings # unchecked # lt # extends # static # Comparable

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：centos spool最佳实践与建议

下一篇：中国免费建站网：永久免费自助建站与中文网站生成系统

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：centos spool最佳实践与建议

下一篇：中国免费建站网：永久免费自助建站与中文网站生成系统