《归并排序算法的原理及JAVA实现.docx》由会员分享，可在线阅读，更多相关《归并排序算法的原理及JAVA实现.docx（4页珍藏版）》请在三一办公上搜索。
1、归并排序算法的原理及JAVA实现归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为： 1）划分子表 2）合并半子表 首先我们来讨论归并算法，归并算法将一系列数据放到一个向量中，索引范围为first,last,这个序列由两个排好序的子表构成，以索引终点为分界线，以下面一个序列为例 7，10，19，25，12，17，21，30，48 这样的一个序列中，分为两个子序列 7,10,19,25 和 12,17,21,30,48，如下图所示： 再使用归并算法的时候的步骤如下： 第一步
2、：比较vindexA=7和vindexB=12,将较小的vindexA取出来放到临时向量tempArray中，然后indexA加1 第二步：比较vindexA=10和vindexB=12,将较小的10放到临时变量tempArray中，然后indexA+; 第三步：比较vindexA=19与vindexB=12，将较小的12存放到临时变量tempArray中，然后indexB+; 第四步到第七步：按照以上规则，进行比对和存储，得到如下结果： 最后一步：将子表b中剩余项添加到临时向量tempArray中 然后将临时变量中的值按照索引位置，拷贝回向量v中，就完成了对向量v的归并排序 Java实现代码
3、： package com.sort.merge; public class Merge /* * 分治法,自顶向下，递归分割数组，最终归并 */ public static void merge(int arr,int start,int end) if(startend) int mid = (start+end)/2; merge(arr,start,mid);/递归地对arrstart.mid排序 merge(arr,mid+1,end);/递归地对arrmid+1.end排序 doMerge(arr,start,mid,end);/组合，将两个有序区合并为一个有序区 /组合，归并 p
4、ublic static void doMerge(int arr,int start,int mid,int end) int tempIndex = start; int Index = start; int right = mid + 1; int temp = new intarr.length; /两个子序列比较，小的放入临时数组 while(start = mid & right = end) if(arrstart = arrright) temptempIndex+ = arrstart+; else temptempIndex+ = arrright+; /剩下的右边的元素加
5、入临时数组 while(start = mid) temptempIndex+ = arrstart+; /剩下的右边的元素加入临时数组 while(right = end) temptempIndex+ = arrright+; /复制临时数据temp中的数据到arr数组 while(Index end) arrIndex = tempIndex+; public static void main(String args) / TODO Auto-generated method stub int arr = 2,4,6,8,1,3,5,9; merge(arr,0,arr.length-1
6、); for (int i = 0; i arr.length; i+) System.out.print(arri); 采用分治法进行自顶向下的算法设计，形式更为简洁。 分治法的三个步骤 设归并排序的当前区间是Rlow.high，分治法的三个步骤是： 分解：将当前区间一分为二，即求分裂点 求解：递归地对两个子区间Rlow.mid和Rmid+1.high进行归并排序； 组合：将已排序的两个子区间Rlow.mid和Rmid+1.high归并为一个有序的区间Rlow.high。 递归的终结条件：子区间长度为1。 具体算法 void MergeSortDC(SeqList R，int low，int high) /用分治法对Rlow.high进行二路归并排序 int mid； if(lowhigh)/区间长度大于1 mid=(low+high)/2； /分解 MergeSortDC(R，low，mid); /递归地对Rlow.mid排序 MergeSortDC(R，mid+1，high)； /递归地对Rmid+1.high排序 Merge(R，low，mid，high)； /组合，将两个有序区归并为一个有序区 /MergeSortDC
