归并排序详细解说

喜欢ヅ旅行 2022-10-29 06:24 207阅读 0赞

## 思路分析 ##

归并排序：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使  
子序列段间有序。

## 图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]

## 代码示例 ##

1）递归方法

//有两个重要的特点，可以适用于外部排序（数据在磁盘上），也可以适用于链表排序
        // （希尔，堆排序，快速排序依赖随机访问能力，都不适合链表排序）
        //基本思路来源于基本问题：把两个有序链表/数组合并成一个
    
        //[low,mid) 有序区间
        //[mid,high) 有序区间
        //两个区间进行合并
        public static void  merge(int[] array,int low, int mid, int high){
        
            int[] output = new int[high - low];
            int outputIndex = 0;//记录当前output数组中被放入了多少元素
            int cur1 = low;//第一个区间的起始下标
            int cur2 = mid;//第二个区间的起始下标
    
            while (cur1 < mid && cur2 < high){
        
                //以下条件写成小于等于，才能保证稳定性
                if (array[cur1] <= array[cur2]){
        
                    output[outputIndex] = array[cur1];
                    outputIndex++;
                    cur1++;
                }else {
        
                    output[outputIndex] = array[cur2];
                    outputIndex++;
                    cur2++;
                }
            }
            //当以上循环结束的时候，肯定有一个cur到达末尾，另一个还剩下一些内容
            //把剩余的内容老被到output中
            while (cur1 < mid){
        
                output[outputIndex] = array[cur1];
                outputIndex++;
                cur1++;
            }
            while (cur2 < high){
        
                output[outputIndex] = array[cur2];
                outputIndex++;
                cur2++;
            }
    
            //把output的元素搬运到原来的数组
            for (int i = 0; i < high - low; i++){
        
                array[low + i] = output[i];
            }
    
        }
    
        public static void mergeSort(int[] array){
        
            mergeSortHelper(array,0,array.length);
        }
    
        //[low,high)前闭后开区间
        private static void mergeSortHelper(int[] array, int low, int high) {
        
            if (high - low <= 1){
        
                return;
            }
            int mid = (low + high) / 2;
            mergeSortHelper(array,low,mid);
            mergeSortHelper(array,mid,high);
    
            //当我们把左右区间归并排序完了，说明左右区间已经是有序区间了
            merge(array,low,mid,high);
        }

2）非递归方法

public static void mergrSortByLoop(int[] array){
        
            //引入一个gap变量进行分组
            //当gap为1的时候，0 1是一组  2 3是一组  4 5是一组。。。
            //当gap为2的时候，就是[0，1]和【2，3】是一组。。。。
            //当gap为4的时候，【0，1，2，3】和【4，5，6，7】是一组
            for (int gap = 1; gap < array.length; gap *= 2){
        
                //接下来进行具体的分组合并
                for (int i = 0; i < array.length; i+= 2*gap){
        
                    int beg = i;
                    int mid = i + gap;
                    int end = i + 2*gap;
                    //防止下标越界
                    if (mid > array.length){
        
                        mid = array.length;
                    }
                    if (end > array.length){
        
                        end = array.length;
                    }
                    merge(array,beg,mid,end);
                }
            }
        }

## 性能分析 ##

**时间复杂度：**  
O(n \* log(n))

**空间复杂度：**  
O(n)

**稳定性：**  
稳定排序

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]: /images/20221024/5fd9030760c04f9298b10d70069a7c99.png