数据结构与算法--归并排序

朴灿烈づ我的快乐病毒、 2022-10-06 02:56 162阅读 0赞

归并排序 和快速排序差不多，性能没有快速排序好。但是它是稳定排序（稳定排序：集合中相等的元素在排序前后相对顺序保持不变）

下面代码就是将一个大的数组通过分治思想分解为一个个小的数组。直到数组中只有一个为止。然后依次从小的数组合并为一个大的数组返回。就达到了排序的目的。

/**
         * 归并排序
         * @param arr
         * @return
         */
       public static int[] mergeSort(int[] arr){ 
            // 结束条件 长度小于等于1 无需排序直接返回
           if(arr.length<=1) return arr;
    
           // 分解 计算中间位置 分解为左右两部分
            int m = arr.length/2;
           // 求解 左半部分 递归求解
            int[] left = Arrays.copyOfRange(arr,0,m);
            left=mergeSort(left);
           // 求解 右半部分递归求解
            int[] right = Arrays.copyOfRange(arr,m,arr.length);
            right=mergeSort(right);
           // 合并 两个排序后的数组为一个数组
    
           return merge(left,right);
       }
    
        /**
         * 合并
         * @param L
         * @param R
         * @return
         */
       private static int[] merge(int[] L,int[] R){ 
           // 创建一个数组用于存放结果
            int[] result = new int[L.length+R.length];
           // 使用两个变量分别记录两个数组的位置
            int lIndex = 0,rIndex=0;
           // 遍历两个数组每次存放最小的放入结果数组中
            for(int i =0;i<result.length;i++){ 
                if(lIndex<L.length && rIndex<R.length){ 
                    // 两个数组都还有元素，则比较取最小的。小于等于目的就是为了稳定排序的特征
                    if(L[lIndex]<=R[rIndex]){ 
                        result[i]=L[lIndex++];
                    }else{ 
                        result[i]=R[rIndex++];
                    }
                // 如果其中一个为空则另一个依次复制到结果数组中
                }else if(lIndex<L.length){ 
                    result[i]=L[lIndex++];
                }else{ 
                    result[i]=R[rIndex++];
                }
    
    
            }
            return result;
       }