归并排序的递归与非递归实现

浅浅的花香味﹌ 2024-03-27 15:13 83阅读 0赞

#### 文章目录 ####

*  归并排序
 *   *  1. 基本思想
     *  2.归并排序的递归实现
     *   *  2.1 原理
         *  2.2 代码实现
     *  3.归并排序的非递归实现
     *   *  3.1 原理
         *  3.2 代码实现

## 归并排序 ##

### 1. 基本思想 ###

1.**归并排序**（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序核心步骤：

![在这里插入图片描述][26822484aa444705850412db44429990.png]

2.总结：

1.  归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2.  时间复杂度：O(N\*logN)
3.  空间复杂度：O(N)
4.  稳定性：稳定

### 2.归并排序的递归实现 ###

#### 2.1 原理 ####

1.由归并排序的步骤我们可以发现，他类似于一棵完全二叉树，所以我们可以采用递归去实现，此时递归分解时时间复杂度为树的高度O(logN)。  
2.通过对序列进行不断二分，当我们将序列分解到不能再分的时候（也就是一个），再通过比较分解成的最小有序序列头的大小，确定合并顺序。  
3.我们通过申请一个临时数组tmp，将小的有序序列依次添加其中，全部添加完毕后，拷贝一下，就得到一个有序序列了，合并时我们是对每一层n个段进行合并，由于树的深度为logN所以总的时间复杂度是O(N\*logN）。

#### 2.2 代码实现 ####

public static void mergeSort(int[] array){
        
            mergeSortFunc(array,0,array.length-1);
        }
        //分解过程
        private static void mergeSortFunc(int[]array,int left,int right){
        
            //分解到只有一个元素时结束
            if (left>=right){
        
                return;
            }
            //二分
            int mid = (left+right)/2;
            //递归分解左边和右边
            mergeSortFunc(array,left,mid);
            mergeSortFunc(array,mid+1,right);
            //全部分解结束后合并
            merge(array,left,right,mid);
    
        }
        //合并过程,mid可以知道下一个区间在哪
        //比较两段的开头大小，来确定合并
        private static void merge(int[] array,int start,int end,int mid){
        
            int s1 = start;
            //下一段的开始
            int s2 = mid+1;
            //定义一个临时数组存储，比较后的序列
            int[] tmp = new int[end -start+1];
            int k=0;
            //段不为空时比较
            while(s1<=mid&&s2<=end){
        
                if (array[s1]<=array[s2]){
        
                    tmp[k++] = array[s1++];
                }else {
        
                    tmp[k++] = array[s2++];
    
                }
            }
            //当比较完,将剩余数据加入
            while (s1<=mid){
        
                tmp[k++] = array[s1++];
            }
            while (s2<=end){
        
                tmp[k++] = array[s2++];
            }
            //拷贝到array
            for (int i = 0; i < tmp.length; i++) {
        
                //注意拷贝的位置是start之后的不是从零开始
                array[i+start] = tmp[i];
            }
    
        }

### 3.归并排序的非递归实现 ###

#### 3.1 原理 ####

在递归方法中，我们通过递归的方法递归到最底层，然后进行归并排序；而在非递归方法中，我们首先把序列每个数字看成一个一个有序，然后两个两个有序，四个四个有序以此类推直到全部有序，合并方法与递归实现一致。

代码思路：  
1.gap代表一个段的长度，left，right代表段的头尾，mid可以用来确定归并时下一个段的位置，mid就等于一个段的头加上段长-1，就是下一个的段头的前一个。  
2.在一个有序段的段长下，for循环遍历数组，对每段进行归并。然后段长\*2，再次遍历对新的有序段进行合并，直到段长＝数组长度

![在这里插入图片描述][124ac6472ddb4bba8977602f84e10c17.png]

#### 3.2 代码实现 ####

//归并排序，非递归实现
        public static void mergeSort1(int[] array){
        
            int gap = 1;
            while (gap<array.length){
        
                for (int i = 0; i < array.length; i+=gap*2) {
        
                    int left = i;
                    int mid = left+gap-1;
                    //防止越界
                    if (mid>=array.length){
        
                        mid=array.length-1;
                    }
                    int right = mid+gap;
                    //防止越界
                    if (right>=array.length){
        
                        right=array.length-1;
                    }
                    //合并
                    merge(array,left,right,mid);
    
                }
                gap *= 2;
            }
    
        }

[26822484aa444705850412db44429990.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ad445328be7d4b2b9b4154d149f53b92.png
[124ac6472ddb4bba8977602f84e10c17.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5179d4715608458c8d6cf08ac5cb6edc.png