深圳 电子政务网站建设方案,东莞cms建站模板,广州品牌营销策划公司排名,北京动画视频制作公司归并排序(Merge Sort)是利用归并技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。归并排序有两种方式#xff1a;1): 自底向上的方法 2):自顶向下的方法 1、 自底向上的方法#xff08;1#xff09; 自底向上的基本思想 自底向上的基… 归并排序(Merge Sort)是利用归并技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。归并排序有两种方式1): 自底向上的方法 2):自顶向下的方法 1、 自底向上的方法1 自底向上的基本思想 自底向上的基本思想是第1趟归并排序时将待排序的文件R[1..n]看作是n个长度为1的有序子文件将这些子文件两两归并若n为偶数则得到n/2个长度为2的有序子文件若n为奇数则最后一个子文件轮空(不参与归并)。故本趟归并完成后前n/2 - 1个有序子文件长度为2但最后一个子文件长度仍为1第2趟归并则是将第1趟归并所得到的n/2个有序的子文件两两归并如此反复直到最后得到一个长度为n的有序文件为止。 上述的每次归并操作均是将两个有序的子文件合并成一个有序的子文件故称其为二路归并排序。类似地有k(k2)路归并排序。 2、自顶向下的方法(本文主要介绍此种方法下面的文字都是对此种方法的解读) 1 自顶向下的基本思想 采用分治法进行自顶向下的算法设计形式更为简洁。 自顶向下的归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表再对半子表排序最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列归并排序包括两个步骤分别为 1划分子表 2合并半子表 1分治法的三个步骤 设归并排序的当前区间是R[low..high]分治法的三个步骤是①分解将当前区间一分为二即求分裂点②求解递归地对两个子区间R[low..mid]和R[mid1..high]进行归并排序③组合将已排序的两个子区间R[low..mid]和R[mid1..high]归并为一个有序的区间R[low..high]。 递归的终结条件子区间长度为1一个记录自然有序。 如下演示递归的整个过程 递归便是深度遍历如下由左至右进行遍历假设有这样的一列数组{9,8,7,6,5,4,3,2,1}进行划分的顺序如下 {9,8,7,6,5,4,3,2,1} -- {9,8,7,6,5}{4,3,2,1} {9,8,7,6,5} -- {9,8,7}{6,5} {9,8,7} -- {9,8}{7} {9,8} -- {9}{8} {6,5} --{6}{5} {4,3,2,1} -- {4,3}{2,1} {4,3} --{4}{3} {2,1} --{2}{1} 当深度划分到左右数组都只剩1个元素的时候进行上述逆序的合并 {9}{8} -- {8,9} 然后和 {7} -- {7,8,9} {6}{5} -- {5,6} 然后 {7,8,9}和{5,6} -- {5,6,7,8,9} {2}{1} -- {1,2} {4}{3} -- {3,4} 然后 {1,2}和 {3,4} -- {1,2,3,4} 最终{5,6,7,8,9}和{1,2,3,4} -- {1,2,3,4,5,6,7,8,9} 具体实现代码如下所示 //归并排序目标数组子表的起始位置子表的终止位置 private static void MergeSortFunction(int[] array, int first, int last) {try {if (first last) //子表的长度大于1则进入下面的递归处理 {int mid (first last) / 2; //子表划分的位置 MergeSortFunction(array, first, mid); //对划分出来的左侧子表进行递归划分 MergeSortFunction(array, mid 1, last); //对划分出来的右侧子表进行递归划分 MergeSortCore(array, first, mid, last); //对左右子表进行有序的整合归并排序的核心部分 } }catch (Exception ex) { } }//归并排序的核心部分将两个有序的左右子表以mid区分合并成一个有序的表 private static void MergeSortCore(int[] array, int first, int mid, int last) {try {int indexA first; //左侧子表的起始位置 int indexB mid 1; //右侧子表的起始位置 int[] temp new int[last 1]; //声明数组暂存左右子表的所有有序数列长度等于左右子表的长度之和。 int tempIndex 0;while (indexA mid indexB last) //进行左右子表的遍历如果其中有一个子表遍历完则跳出循环 {if (array[indexA] array[indexB]) //此时左子表的数 右子表的数 { temp[tempIndex] array[indexA]; //将左子表的数放入暂存数组中遍历左子表下标 }else//此时左子表的数 右子表的数 { temp[tempIndex] array[indexB]; //将右子表的数放入暂存数组中遍历右子表下标 } }//有一侧子表遍历完后跳出循环将另外一侧子表剩下的数一次放入暂存数组中有序 while (indexA mid) { temp[tempIndex] array[indexA]; }while (indexB last) { temp[tempIndex] array[indexB]; }//将暂存数组中有序的数列写入目标数组的制定位置使进行归并的数组段有序 tempIndex 0;for (int i first; i last; i) { array[i] temp[tempIndex]; } }catch (Exception ex) { } } 对于N个元素的数组来说, 如此划分需要的层数是以2为底N的对数, 每一层中, 每一个元素都要复制到结果数组中, 并复制回来, 所以复制2N次, 那么对于归并排序,它的时间复杂度为O(N*logN), 而比较次数会少得多, 最少需要N/2次,最多为N-1次, 所以平均比较次数在两者之间. 它的主要问题还是在于在内存中需要双倍的空间.转载于:https://www.cnblogs.com/kloseking/p/3165710.html
