归并排序出现栈溢出及解决方案

浅浅的花香味﹌ 2022-04-13 13:17 182阅读 0赞

在实现归并排序的过程中，出现了栈溢出的情况，如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70]

因为归并排序就是一个递归的过程，中间值都是存放在栈中，所以容易出现栈溢出的问题。

下面是归并排序的核心代码：

public static void mergeSort(int[] arr){ 
            //数组为空或数组长度过短时
            if(arr==null||arr.length<=2){ 
                return;
            }
            mergeSort(arr,0,arr.length-1);
        }
    
        public static void mergeSort(int[] arr,int l,int r){ 
            //需要判断r==l的情况，否则会导致栈溢出的问题
            if(r==l){ 
                return;
            }
            int m=l+(r-l)/2;
            mergeSort(arr,l,m);
            mergeSort(arr,m+1,r);
            merge(arr,l,m,r);
        }
    
        public static  void merge(int[] arr,int l ,int m,int r){ 
            int[] help=new int[r-l+1];
            int i=0;
            int p1=l;
            int p2=m+1;
            while(p1<=m&&p2<=r){ 
                help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
            }
            while (p1<=m){ 
                help[i++]=arr[p1++];
            }
            while (p2<=m){ 
                help[i++]=arr[p2++];
            }
            for(i=0;i<help.length;i++){ 
                arr[i]=help[i];
            }
        }

一开始我并没有判断递归到只剩下一个值的情况，即左右两边都指向一个数的时候，如下：

public static void mergeSort(int[] arr,int l,int r){ 
            int m=l+(r-l)/2;
            mergeSort(arr,l,m);
            mergeSort(arr,m+1,r);
            merge(arr,l,m,r);
        }

我直接进行排序过程，就出现了栈溢出的情况，加上判断以后就正确了。  
加上判断就是：

public static void mergeSort(int[] arr,int l,int r){ 
            //需要判断r==l的情况，否则会导致栈溢出的问题
            if(r==l){ 
                return;
            }
            int m=l+(r-l)/2;
            mergeSort(arr,l,m);
            mergeSort(arr,m+1,r);
            merge(arr,l,m,r);
        }

另外，归并排序还要注意，每次递归时都是在栈中进行，当满足base case条件时，即问题划分到最小规模不再划分的时候，就开始各自部分的比较。当左右两部分各自比较完后，才是整体的比较，这里我们用一个指针指向左右两部分的第一个值，然后比较值的大小，将小的值放入数组，并且指针移动。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70]: /images/20220413/356b40b59dcc4fc5ae266da3cc6c897d.png