MergeSort(归并排序)算法Java实现详解编程语言
归并排序
归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序,也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
1.两路归并排序算法思路
①把 n 个记录看成 n 个长度为1的有序子表;
②进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表;
③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。
【例】 有一组关键字 {4,7,5,3,2,8,6,1},n=8, 将其按由小到大的顺序排序。 两路归并排序操作过程如图 9.12 所示,其中i 为子表长度。
2.算法实现
此算法的实现不像图示那样简单,现分三步来讨论。首先从宏观上分析,首先让子表表长 L=1 进行处理;不断地使 L=2*L ,进行子表处理,直到 L =n 为止,把这一过程写成一个主体框架函数 mergesort 。然后对于某确定的子表表长 L ,将 n 个记录分成若干组子表,两两归并,这里显然要循环若干次,把这一步写成一个函数 mergepass ,可由 mergesort 调用。最后再看每一组(一对)子表的归并,其原理是相同的,只是子表表长不同,换句话说,是子表的首记录号与尾记录号不同,把这个归并操作作为核心算法写成函数 merge ,由 mergepass 来调用。假设我们有一个没有排好序的序列,那么首先我们使用分割的办法将这个序列分割成一个一个已经排好序的子序列,然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程可以看下面的图例。
3.算法主要思想
template class T
void merge( T r[],T r2[],int s,int mid,int t)
//s为第一个子表首元素的下标,mid为第一个子表末元素的下标
//t为第二个子表末元素的下标
{ int i,j,k;
i=s;j=mid+1;k=s; //k是r2的初始指针
while((i =mid) (j =t))
{ k=k+1;
if(r[i].key =r[j].key){r2[k]=r[i];i++;}
else{r2[k]=r[j];j++;}
}
while(i =mid){k++;r2[k]=r[i];i++;}
while(j =t){k++;r2[k]=r[j];j++;}
} //merge
Java实现的二路归并排序的算法如下:
package algorithms; public class myMergeSort { static int number=0; public static void main(String[] args) { int[] a = {26, 5, 98, 108, 28, 99, 100, 56, 34, 1 }; printArray("排序前:",a); MergeSort(a); printArray("排序后:",a); private static void printArray(String pre,int[] a) { System.out.print(pre+"/n"); for(int i=0;i a.length;i++) System.out.print(a[i]+"/t"); System.out.println(); private static void MergeSort(int[] a) { // TODO Auto-generated method stub System.out.println("开始排序"); Sort(a, 0, a.length - 1); private static void Sort(int[] a, int left, int right) { if(left =right) return; int mid = (left + right) / 2; //二路归并排序里面有两个Sort,多路归并排序里面写多个Sort就可以了 Sort(a, left, mid); Sort(a, mid + 1, right); merge(a, left, mid, right);5.算法分析
(1)稳定性
归并排序是一种稳定的排序。
(2)存储结构要求
可用顺序存储结构。也易于在链表上实现。
(3)时间复杂度
对长度为n的文件,需进行趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
(4)空间复杂度
需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。
注意:
若用单链表做存储结构,很容易给出就地的归并排序。原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/16456.html
cgojava
相关文章
- 快速排序算法详细图解JAVA_实现快速排序
- java强制删文件夹_Java 删除文件夹 和 文件 集合
- java数组排序去重_JAVA数组去重排序
- java单例模式——详解JAVA单例模式及8种实现方式
- Java实现MD5算法
- 八大排序算法(java实现) 冒泡排序 快速排序 堆排序 归并排序 等[通俗易懂]
- java基本数据类型 think in java_Think in Java(一):Java基础[通俗易懂]
- java 阶乘算法_Java 实现阶乘算法
- java 随机数算法_Java随机数算法原理与实现方法实例详解
- java中sort排序_数据结构算法总结
- Java把string转json格式_java实体类转json字符串
- Java--十大排序算法
- java实现选择排序算法详解编程语言
- java实现排序算法:插入排序、选择排序、冒泡排序详解编程语言
- Java排序算法 – 基数排序详解编程语言
- java归并排序算法详解编程语言
- Java学习笔记之十一Java中常用的8大排序算法详解总结编程语言
- Java程序员必须掌握的8大排序算法详解编程语言
- 常见排序算法(java实现)详解编程语言
- 必须知道的八大种排序算法【java实现】(一) 冒泡排序、快速排序详解编程语言
- Linux 卸载Java:简单步骤完成(linux卸载java)
- Using Java to Work with MongoDB: A Guide for Developers(java操作mongodb)
- 让Java开发能力在Linux下得到更大发挥(java linux编程)
- Java搭配MySQL,实现创新跳跃的可能(java 与mysql)
- 本使用Oracle Java 进行升级新版本带来新体验(oracle java版)
- java枚举的使用示例
- JAVA算法起步之快速排序实例