首页 > 代码库 > 递归分治算法（一）-归并排序算法
递归分治算法（一）-归并排序算法
前言：
分治法是一种算法设计思想，所谓分治，意为分而治之，是指将一个难以直接解决的大问题，递归的分割成一些规模的较小的问题，以便逐个解决。采用分治法设计的算法通常用到递归算法来实现，故标题为递归分治。
归并排序算法
归并就是将两个或两个以上的有序表合并成一个新的有序表。归并排序就是将无序的待排序的序列分解成若干个有序的子序列，并把有序子序列合并为整体有序序列的过程。一般分为2-路归并排序和多路归并排序。
他的大概流程如下图：
我们来看看java代码怎么写的：
package guibing;/*** * @author 文聪 * @date 2016/9/26 * 归并排序算法 **/public class Sort { public static void main(String[] args) { int[] a = {42,30,68,98,86,15,57}; sort(a, 0, a.length-1); for (int i : a) { System.out.print(i+" "); }} public static void sort(int[] a, int left, int right) { if (left >= right) return; int center = (left + right) >> 1; sort(a, left, center); sort(a, center + 1, right); merge(a, left, center, right);} public static void merge(int[] data, int left, int center, int right) { int[] tmpArr = new int[right+1]; int mid = center + 1; int index = left; // index记录临时数组的索引 int tmp = left; // 从两个数组中取出最小的放入中临时数组 while (left <= center && mid <= right) { tmpArr[index++] = (data[left] <= data[mid]) ? data[left++]: data[mid++]; } // 剩余部分依次放入临时数组 while (mid <= right) { tmpArr[index++] = data[mid++]; } while (left <= center) { tmpArr[index++] = data[left++]; } // 将临时数组中的内容复制回原数组 for (int i = tmp; i <= right; i++) { data[i] = tmpArr[i]; }}}
总结：对归并排序算法进行分析发现，每一层归并排序都是将区间[left，right]划分为两个大致相等的子序列，然后进行归并。排序过程需要进行[logn]层的递归分解和归并，由此的归并排序的算法时间复杂度为O（nlogn）,空间复杂度也为O（n）
递归分治算法（一）-归并排序算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。