归并排序
归并排序,指的是将两个已经排序的序列合并成一个序列的操作。
归并操作的过程如下:
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
/** * 归并排序 * * @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)
稳定性:稳定
扩展:
在java中,当执行一次泛型排序时,进行一次元比较可能是昂贵的,但是移动元素则是省时间的。归并排序使用所有的流行的排序算法中最少的比较次数,因此是使用java的通用排序算中的上好的选择。
相关推荐
使用Java实现简单的归并排序算法,给大家提供一个参考。
Java实现归并排序.rar
在Java实现中,归并排序通过递归调用mergeSortHelper方法将数组划分为更小的子数组,并在最后使用merge方法将有序子数组合并成一个完整的数组。归并排序虽然需要额外的空间来存储临时数组,但其稳定的性能和可并行化...
mergeSort 方法实现了归并排序算法。它使用递归的方式将数组不断划分为更小的子数组,直到每个子数组只有一个元素,然后再依次将这些子数组进行合并,从而实现排序。 merge 方法用于合并两个有序子数组。它借助两个...
实现归并排序的一个类
该资源提供了一份全面的指南,介绍了如何在Java中实现归并排序。文档中涵盖了归并排序的基本概念,包括如何对数组进行排序以及如何在Java中实现归并排序。此外,文档还包括一个逐步指南,介绍如何在Java中实现归并...
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
给初学者学习算法用,用java实现的排序算法,包括二路归并和插入排序。
利用分治法思想实现归并排序,Java语言描述。
一年前做的排序动画,归并排序动画一直未完成,今天完成了,与大家共享
java快速排序 归并排序 冒泡排序 选择排序
java归并外排序
用ArrayList实现的排序算法,希望对有需要的同学有帮助,如有错误请指出。JDK版本为1.7
外排序--基于败者树的多路归并排序算法的java实现
用java语言实现冒泡排序、插入排序、堆排序、快速排序、归并排序、希尔排序、桶排序,并且对各种排序算法进行性能的比较。
归并排序,消除递归归并排序,快排,Java实现
一个Java小程序,利用递归思想实现的归并排序算法。其中有两个类,排序数据是写死在main方法中的。