七大排序算法——归并排序，通俗易懂的思路讲解与图解(完整Java代码)_归并排序 通俗

---

一、排序的概念

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

排序的稳定性

上述待排序的数中，有两个5。 将前面的5标记一个a， 将后面的5标记一个b。

通过算法进行排序后，这一组数就有序了， 但是要看两个相同的5的位置是否有改变。
5a仍在5b前面，那么这个排序算法就是稳定的 ，
5a跑到了5b后面，那么这个排序算法就是不稳定的 。
一个稳定的排序算法可以做到不稳定，
不稳定的排序算法一定做不到稳定。

至于为什么要讨论这个稳定性， 是为了以后应用到实际场景上。 比如，一场数学考试， 假设a用了30分钟做完了，并得了满分。
假设b用了一个小时做完了，并得了满分。 此时a与b都是得了满分，但是用的时间不一样，所以两个人的排名又会有所不同。

---

七大排序算法

---

二、归并排序

核心思想

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

图解

有一组待排序数列，我们进行升序排序。



拆分过程：将一个数组逐层拆分成多个子序列，直到每个子序列只剩一个数据，那么就认为这个子序列是有序的。
合并过程：再逐一将这些子序列进行有序合并，最后得到的序列就是有序的。

---

代码实现

代码实现

public class MergeSort {
    /**
     * 归并排序
     * 时间复杂度：O（n*logn）
     * 空间复杂度：O（n）
     * 稳定性：稳定
     * @param array
     */

    //递归实现的归并排序
    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);
    }
    // 合并方法
    private static void merge(int[] array,int start,int end,int mid) {
        // 创建一个新数组
        int[] ary = new int[end-start+1];
        // 左边有序数组的起始下标
        int left = start;
        // 右边有序数组的起始下标
        int right = mid+1;
        for (int i = 0; i < end-start+1; i++) {
            // 如果左边有序数组已经全部有序的存入了新数组，
            // 那就证明剩下右边有序数组的数已经有序了，不用比较直接存入
            if(left > mid) {
                ary[i] = array[right++];
            // 如果右边有序数组已经全部有序的存入了新数组，
            // 那就证明剩下左边有序数组的数已经有序了，不用比较直接存入    
            }else if (right > end) {
                ary[i] = array[left++];
            // 哪个小哪个先存进新数组    
            } else if(array[left] > array[right]) {
                ary[i] = array[right++];
            }else {
                ary[i] = array[left++];
            }
        }
        // 将新数组按位置存入需要排序的数组
        for (int i = start; i < end+1; i++) {
            array[i] = ary[i - start];
        }
    }

    

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

---

三、性能分析

归并排序总结
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(n*logn)
空间复杂度：O(n)
稳定性：稳定

---

四、七大排序算法性能对比

想学哪个点哪个
归并排序讲解
快速排序讲解
直接插入排序讲解
希尔排序讲解
直接选择排序讲解
堆排序讲解
冒泡排序讲解