归并排序 和 七大算法的总结图

目录

什么是递归排序：

        图解：

递归方法：

    代码实现：

        思路分析：

       非递归方法：

       思路：

       代码实现：

        思路分析：

---

什么是递归排序：

        先将数据分解成诺干个序列，将子序列合并排序，得到有序的序列，再与旁边子序列合并；即先使每个子序列有序，再使子序列段间有序。最后将两个有序表合并成⼀个有序表。

        图解：

        

         

递归方法：

    代码实现：

public static void mergeSort(int[] arr) {mergeSortChild(arr,0,arr.length-1);}private static void mergeSortChild(int[] arr,int left,int right) {if(left == right) {return;}int mid = (left + right) / 2;mergeSortChild(arr,left,mid);mergeSortChild(arr,mid + 1,right);//开始合并merge(arr,left,mid,right);}private static void merge(int[] arr, int left, int mid, int right) {//临时数组int[] tmpArr = new int[right - left + 1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;while(s1 <= e1 && s2 <= e2) {if(arr[s1] <= arr[s2]) {tmpArr[k++] = arr[s1++];}else {tmpArr[k++] = arr[s2++];}}while(s1 <= e1) {tmpArr[k++] = arr[s1++];}while(s2 <= e2) {tmpArr[k++] = arr[s2++];}//拷贝临时数组给到arrfor (int i = 0; i < k; i++) {arr[i + left] = tmpArr[i];}}

        思路分析：

        

         与快速排序类似，结合上图，定义一个 mid 作为 一段数据的中间下标，然后依次往下分，左边的新 left 和 right 为上一个段数据的 left 和 mid ，右边的新 left 和 right 为上一个段数据的 mid + 1 和 right。分解结束条件为 当 left 与 right 相遇了。

        对于merge方法，结合此图：

        

         此图是原数据的左边的一段数据，定义一个临时数组，把下面的两个已经有序的 一段数据合并成给到临时数组，方法是s1 与 s2 比较，哪个小先给到临时数组，直到一方为放完。之后，把没放完的一方全部给到临时数组。k就得到临时数组的元素个数。

        最后，通过for循环把临时数组的数据拷贝到原始数组里，但是有个要注意的地方：

        

         看蓝色圈出来的区域，3 9 4 2 的那段数据的 3 和 9 一段小数据，如果merge方法 的for循环是这样的：

 for (int i = 0; i < k; i++) {arr[i] = tmpArr[i];}

        那么将临时数组的数据拷贝到原始数组里，会出现问题。

        原始数组的 元素3 下标应该是 4，如果按照从 0 下标开始，  会给到原始数组 0 下标位置这样是不对的，但如果加上了 left：

 for (int i = 0; i < k; i++) {arr[i + left] = tmpArr[i];}

        这样就能确保 元素3 给到了 原始数组 4 下标的位置。

        

       非递归方法：

       思路：

        

          上图对于8个原数据，我们先把数据从 1个1个有序（6和10，1和7，3和9，2和4），一直到 2个2个 有序（（6   10和1   7 ）；（3   9 和 2   4） ）来进行排序，那么最后 4个4个 有序（（6   10   1   7 ）和（3   9   2   4））就能完成排序了。

        首先定义了 i 作为遍历数组使用，l 作为 左边起始，r 作为结束位置，m 是 他们的中间位置。

        定义一个 gap 作为 临界值，初始化为1，循环结束 gap 每次 乘以 2 ，当 gap 为 数组长度时不进入循环。

        上图是 gap 为 2 的时候，其他参数赋值如上图。

       代码实现：

public static void feidigui(int[] arr) {int gap = 1;while(gap < arr.length) {for (int i = 0; i < arr.length; i = i + 2*gap) {int left = i;int mid = left + gap - 1;if(mid >= arr.length) {mid = arr.length-1;}int right = mid+gap;if(right >= arr.length) {right = arr.length-1;}merge(arr,left,mid,right);}gap *= 2;}}private static void merge(int[] arr, int left, int mid, int right) {//临时数组int[] tmpArr = new int[right - left + 1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;while(s1 <= e1 && s2 <= e2) {if(arr[s1] <= arr[s2]) {tmpArr[k++] = arr[s1++];}else {tmpArr[k++] = arr[s2++];}}while(s1 <= e1) {tmpArr[k++] = arr[s1++];}while(s2 <= e2) {tmpArr[k++] = arr[s2++];}//拷贝临时数组给到arrfor (int i = 0; i < k; i++) {arr[i + left] = tmpArr[i];}}

        思路分析：

        

         结合代码和此图，当 gap 为 2 时，i 下一次取值为 i + 2*gap，确保后面的（3   9   2   4）也能进行有序排列。

        要注意的是：

        

         过程可能会出现上面三种情况，当 mid 超过了 数组长度 ，就越界了，就要把 mid 设置为数组的最后一个位置，right 同理。此过程不会影响 merge 方法的出现错误。（相当于处理边界值）

        

        归并排序是稳定的。

        

      七大算法的总结图：