十大排序算法之归并排序

矫情吗；* 2023-02-25 10:14 30阅读 0赞

# 归并排序 #

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

## 算法步骤 ##

1.  不断地将当前序列平均分割成2个子序列，直到不能再分割（序列中只剩1个元素）
2.  不断地将2个子序列合并成一个有序序列，直到最终只剩下1个有序序列

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

## divide实现 ##

private E[] leftArray;
    
        @Override
        protected void sort() { 
            this.leftArray = (E[]) new Comparable[array.length >> 1];
            divide(0, array.length);
        }
    
        /** * 对索引范围为[begin,end)的元素进行拆分 * @param begin * @param end */
        private void divide(int begin, int end) { 
            if(end - begin < 2) { 
                return;
            }
    
            int middle = (begin + end) >> 1;
            divide(begin, middle);
            divide(middle, end);
    
            merge(begin, middle, end);
        }

## merge实现 ##

private void merge(int begin, int middle, int end) { 
    
            int li = 0;
            int le = middle - begin;
            int ri = middle;
            int re = end;
            int ai = begin;
    
            // 先备份左边
            for (int i = li; i < le; i++) { 
                leftArray[i] = array[begin + i];
            }
    
            while (li < le) { 
    
                if(ri < re && cmp(leftArray[li], array[ri]) > 0) { 
                    array[ai++] = array[ri++];
                } else { 
                    array[ai++] = leftArray[li++];
                }
            }
    
        }

由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是O(nlogn)，属于稳定排序。

从代码中不难看出：归并排序的空间复杂度是O(n/2+ logn)= O(n)，其中n/2用于临时存放左侧数组，logn用于递归调用。

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: /images/20230209/b4089aec368e43c69ea06335e3458878.png
[20200627175030665.jpg]: /images/20230209/160e6c7703f042939f905e3e41f6f772.png