算法学习---归并算法简单记录

1、核心思想

• 将难以一次性解决的原始问题（大问题），分割为较为容易处理的小问题（此步骤一般递归、迭代均可实现），计算结果；
• 然后将小问题的计算结果合并（汇聚or统计）；
• 最终得到问题答案。

2、应用

经典应用，数组排序算法（递归实现方式）如下：
在学习过程中，应该先理解算法整个流程，在掌握整个流程之前，如果在某一点的实现上有问题，可以暂时放下，后续把它研究透彻。

• mergeSort方法开启数组分割流程
• recusion方法具体分割实现
• merge方法具体小问题结果合并成大问题答案算法

 /*** 2路归并排序 1、首先将整体分成两部分，* 对每一部分进行排序，(递归),将每一部分再进分成两部分，直至不可再分* 2、将左右两部分进行合并，最终合并成有序数组* @param arr* @return*/public static int[] mergeSort(int[] arr) {if (null == arr || arr.length == 0 || arr.length == 1)return arr;int start = 0;int end = arr.length - 1;recusion(arr, start, end);return arr;}/*** 递归调用方法，对确定范围内分左右两侧进行排序* * @param arr* @param start* @param end*/private static void recusion(int[] arr, int start, int end) {if (start >= end)return;int mid = start + (end - start) / 2;recusion(arr, start, mid);recusion(arr, mid + 1, end);merge(arr, start, mid, mid + 1, end);}/*** 合并两个有序数组* * @param arr* @param start* @param mid* @param mid_plus* @param end*/private static void merge(int[] arr, int start, int mid, int mid_plus, int end) {if (mid_plus > end)return;for (int i = mid_plus; i <= end; i++) {for (int j = i; j >= start;) {while ((j - 1) >= start && arr[j] < arr[j - 1]) {swap(arr, j - 1, j);--j;}break;}}}

迭代算法与递归算法思想一致，不列出具体代码。¹

算法复杂度

这块理的不太顺，目前直接记住完事
时间：O( nlogn )
空间：O(n)