归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))的额外空间,时间复杂度为O(nlog(n)),算法不是自适应的,不需要对数据的随机读取。
工作原理:
1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2、设定两个指针,最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
代码实现:
- public<wbr></wbr>void<wbr>mergeSort(){<wbr><wbr><wbr></wbr></wbr></wbr></wbr>
-
long[]<wbr>workSpace<wbr>=<wbr></wbr></wbr></wbr>new<wbr></wbr>long[nElems];<wbr><wbr><wbr></wbr></wbr></wbr>
-
recMergeSort(workSpace,0,nElems-1);<wbr><wbr><wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
-
private<wbr></wbr>void<wbr>recMergeSort(</wbr>long[]<wbr>workSpace,<wbr></wbr></wbr>int<wbr>lowerBound,<wbr></wbr></wbr>int<wbr>upperBound){<wbr><wbr><wbr></wbr></wbr></wbr></wbr>
-
if(lowerBound<wbr>==<wbr>upperBound){<wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>
-
return;<wbr><wbr><wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
-
else{<wbr><wbr><wbr></wbr></wbr></wbr>
-
int<wbr>mid=(lowerBound+upperBound)/</wbr>2;<wbr><wbr><wbr></wbr></wbr></wbr>
-
recMergeSort(workSpace,<wbr>lowerBound,<wbr>mid);<wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>
-
recMergeSort(workSpace,<wbr>mid+</wbr>1,<wbr>upperBound);<wbr><wbr><wbr></wbr></wbr></wbr></wbr>
-
merge(workSpace,<wbr>lowerBound,<wbr>mid+</wbr></wbr>1,<wbr>upperBound);<wbr><wbr><wbr></wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
-
private<wbr></wbr>void<wbr>merge(</wbr>long[]<wbr>workSpace,<wbr></wbr></wbr>int<wbr>lowPtr,<wbr></wbr></wbr>int<wbr>highPtr,<wbr></wbr></wbr>int<wbr>upperBound){<wbr><wbr><wbr></wbr></wbr></wbr></wbr>
-
int<wbr>j<wbr>=<wbr></wbr></wbr></wbr>0;<wbr><wbr><wbr></wbr></wbr></wbr>
-
int<wbr>lowerBound<wbr>=<wbr>lowPtr;<wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>
-
int<wbr>mid<wbr>=<wbr>highPtr<wbr>-<wbr></wbr></wbr></wbr></wbr></wbr>1;<wbr><wbr><wbr></wbr></wbr></wbr>
-
int<wbr>n<wbr>=<wbr>upperBound-lowerBound+</wbr></wbr></wbr>1;<wbr><wbr><wbr></wbr></wbr></wbr>
-
while(lowPtr<=mid&&highPtr<=upperBound){<wbr><wbr><wbr></wbr></wbr></wbr>
-
if(theArray[lowPtr]<theArray[highPtr]){<wbr><wbr><wbr></wbr></wbr></wbr>
-
workSpace[j++]=theArray[lowPtr++];<wbr><wbr><wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
-
else{<wbr><wbr><wbr></wbr></wbr></wbr>
-
workSpace[j++]=theArray[highPtr++];<wbr><wbr><wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
-
while(lowPtr<=mid){<wbr><wbr><wbr></wbr></wbr></wbr>
-
workSpace[j++]<wbr>=<wbr>theArray[lowPtr++];<wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
-
while(highPtr<=upperBound){<wbr><wbr><wbr></wbr></wbr></wbr>
-
workSpace[j++]<wbr>=<wbr>theArray[highPtr++];<wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
-
for(j=0;j<n;j++){<wbr><wbr><wbr></wbr></wbr></wbr>
-
theArray[lowerBound+j]=workSpace[j];<wbr><wbr><wbr></wbr></wbr></wbr>
- }<wbr><wbr><wbr></wbr></wbr></wbr>
- }<wbr><wbr></wbr></wbr>
归并排序是比较稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5)
(括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2
是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.
分享到:
相关推荐
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
java排序算法使用及场景说明 文档后面有一些别人的链接,多在google上搜索Java排序算法,及维基百科上面也有很全的算法介绍。
分治算法实验(用分治法实现归并排序算法).doc
详解Java常用排序算法-归并排序
java实现的常用的几种基本排序算法,插入、交换、选择、归并
自己编写的基于java的快速排序和归并算法
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
Java排序算法实现 Java排序算法实现 Java排序算法实现
Java排序算法代码.
主要介绍了Java排序算法总结之归并排序,较为详细的分析了归并排序的原理与java实现技巧,需要的朋友可以参考下
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
Java排序算法 Java排序算法.rar
ZB第二十八讲(插入排序和交换排序算法).ppt.ppt
该资源提供了一份全面的指南,介绍了如何在Java中实现归并排序。文档中涵盖了归并排序的基本概念,包括如何对数组进行排序以及如何在Java中实现归并排序。此外,文档还包括一个逐步指南,介绍如何在Java中实现归并...
尚硅谷Java排序算法PPT
根据算法导论实现的归并排序算法