java 归并排序的实例详解

时间:2021-05-19

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

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章