算法渣-归并排序

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

定义

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

算法

归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式

从上往下的归并排序：

1. 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2
2. 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1
3. 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]

从下往上的归并排序：

1. 将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；
2. 得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；
3. 直接合并成一个数列为止。这样就得到了我们想要的排序结果。

归并步骤

• 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
• 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
• 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
• 重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾

比如合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤

演示

实现

/**
 * 归并排序
 * @param array
 * @param left
 * @param right
 */
private static void mergeSort(int []array,int left,int right){
    if(left < right) {
        //分解
        int mid = (left + right) / 2;
        mergeSort(array,left,mid);
        mergeSort(array,mid + 1,right);
        //合并
        merge(array,left,mid,right);
    }
}

static void merge(int []array,int left,int mid,int right) {
    System.out.println("merge->left:"+left+" mid:"+mid+" rgiht:"+right);
    int i = left;
    int j = mid +1;
    int tmp[] = new int[right-left+1];//构建tmp数组
    int t = 0;//tmp数组索引
    //填充tmp数组
    for (;i<=mid && j<=right;) {
        if(array[i] < array[j]) {
            tmp[t++] = array[i++];
        } else {
            tmp[t++] = array[j++];
        }
    }
    while (i<=mid) {
        tmp[t++] = array[i++];
    }
    while (j<=right) {
        tmp[t++] = array[j++];
    }

    //再把tmp复制到array
    t = 0;
    while (left<=right) {
        array[left++] = tmp[t++];
    }
    System.out.println("  tmp:"+ Arrays.toString(tmp));
    System.out.println("merge:"+ Arrays.toString(array));
}

复杂度

归并排序的时间复杂度是O(N*lgN)

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？

归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(N*lgN)

VS 快速排序

归并排序（MergeSort）和快速排序(QuickSort)都是用了分治算法思想。

所谓分治算法，顾名思义，就是分而治之，就是将原问题分割成同等结构的子问题，之后将子问题逐一解决后，原问题也就得到了解决。

同时，归并排序（MergeSort）和快速排序(QuickSort)也代表了两类分治算法的思想。

对于归并排序，我们对于待处理序列怎么分的问题上并没有太多关注，仅仅是简单地一刀切，将整个序列分成近乎均匀的两份，然后将子序列进行同样处理。但是，我们更多的关注点在于怎么把分开的部分合起来，也就是merge的过程。

对于快速排序来说，我们则是花了很大的功夫放在了怎么分这个问题上，我们设定了枢轴（标定点），然后通过partition的过程将这个枢轴放在合适的位置，这样我们就不用特别关心合起来的过程，只需要一步一步地递归下去即可。

归并排序是由下向上的，先处理子数组然后再合并。而快速排序正好相反，它的过程是由上向下的，先分出两个子区间，再对子区间进行排序。归并排序是稳定的时间复杂度为 O(n)O(n)，但它是非原地算法，在进行子数组合并的时候，我们需要临时申请一个数组来暂时存放排好序的数据。因为这个临时空间是可以重复利用的，因此归并排序的空间复杂度为 O(n)，最多需要存放 n 个数据； 而快排则是原地排序算法