归并排序（拓展：递归、master公式、外排、小和、逆序对）

5.归并排序(较快,稳定,对象排序最常用)

1.归并排序:

1.将数组分为两个数组,将两个数组排序后合并;
2.子数组的排序可以递归调用归并排序(也可规模较小时用插入排序)

归并分为 mergeSort()分的过程 和merge()合的过程。

mergeSort()分将一个数组均分成左边和右边，左边和右边再递归调用各自的mergeSort();然后再将左边右边merge();

merge()合是将两个有序数组合成一个新数组的过程。通过left，mid，right；将数组分成的两个有序的范围子数组合并。

//归并排序(时间复杂度为N*logN,稳定;数据库,Java,Python的对象排序都用它)
//原因(优点):稳定,速度较快,空间复杂度为N;
//合并时看子数组规模,大时用归并,小时用插入,都稳定;
// 对应Java中的timiSort
//思想:将数组分为两个数组,将两个数组排序后合并;
//子数组的排序可以递归调用归并排序,规模较小时用插入排序
//涉及理论:插入排序,分治法,递归

//归并排序 总,入口
public static void mergeSort(int[] a){
    if(a==null||a.length<2)return;
    mergeSort(a,0,a.length-1);
}

//拆分
static void mergeSort(int[] a, int left, int right) {
    if (left == right) {
        return;
    } else {
        //取中间值,拆分
        int mid = left + ((right - left) >> 1);
        //拆分左边
        mergeSort(a, left, mid);
        //拆分右边
        mergeSort(a, mid + 1, right);
        //合并
        merge(a, left, mid , right);
    }

}

//合的过程
static void merge(int[] a, int left, int mid, int right) {
    int[] help = new int[right - left + 1];
    int r = mid+1 ;
    int i = 0;
    int l = left;
    while (l <= mid && r <= right) {
        help[i++]=a[l]<=a[r]?a[l++]:a[r++];
    }
    while (l <= mid) {
        help[i++] = a[l++];
    }
    while (r <= right) {
        help[i++] = a[r++];
    }
    for (int m = 0; m < help.length; m++) {
        a[left + m] = help[m];
    }
}

2.归并为什么快？

每次排序的结果后面合并的过程都会用到，所以每次排序没有浪费；采用了分治的思想。

通过这个思想，很多问题可以用归并的思想和算法解决:如小和问题，逆序对问题。

简单排序每次的比较都浪费了，每次循环比较多个数，只排好了一个数的位置。

归并相关扩展：

递归

总结:

（分治，自动压栈，效率低；所有递归程序可以实现非递归，提高效率）通常用栈来实现。

将原问题分解成与原问题相同、规模更小的子问题；然后通过程序自动压栈,调用函数；简化了代码,但效率会变低;

--每次递归程序会将当前函数的所有信息压入栈中，所以效率低，自己压栈可以优化。

详解：

递归，就是在运行的过程中调用自己。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

一般来说，递归需要有边界条件、递归前进段和递归返回段。

当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

构成递归需具备的条件：

1. 子问题须与原始问题为同样的事，且更为简单；(分治)

2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

递归应用

递归算法一般用于解决三类问题：

(1)数据的定义是按递归定义的。（Fibonacci函数）

(2)问题解法按递归算法实现。

这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。

(3)数据的结构形式是按递归定义的。

如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。

递归的缺点：

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

master公式

master公式的使用：
T(N) = a*T(N/b) + O(N^d)
适用范围：递归划分的子问题的规模是一样的；只考虑规模，不考虑常数。

参数说明：N为父问题的样本量；
N/b为子问题的样本量；
a为子问题递归调用的次数；（仅看一次函数体的，一步）
O(N^d)为除了递归过程外，剩下步骤的时间复杂度

T(N) = a*T(N/b) + O(N^d)

1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)

两数组合并：merge

//将两个有序数组合并
static int[] merge(int[] a, int[] b){
    int[] help=new int[a.length+b.length];
    //三个数组的初始头指针
    int l=0;
    int r=0;
    int i=0;
    //合并过程,谁小谁进入help数组
    while(l<a.length&&r<b.length){
        help[i++]=a[l]<=b[r]?a[l++]:b[r++];
    }
    //当上层循环结束后,出现一个数组已经全进入help,将另一个数组直接全装入help
    while(l<a.length){
        help[i++]=a[l++];
    }
    while(r<b.length){
        help[i++]=b[r++];
    }
    //返回
    return help;
}

外排

内排序的的记录比较少，可以将全部记录放到内存中排序。
外排序的记录比较多，不能将全部记录放到内存中，排序过程中会有多次的外存访问操作。（大文件的排序用采用外排，对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。

计算机中处理数据的为中央处理器（CPU），如若需要访问外存中的数据，只能通过将数据从外存导入内存，然后从内存中获取。同时由于内存读写速度快，外存读写速度慢的差异，更加影响了外部排序的效率。

对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多。）

小和问题（merge过程中返回小和）

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：
[1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16

思想：merge的过程中压榨出小和，在归并排序的merg中返回每次merge的小和；

仅在merg中添加三行代码。

1.核心代码：在merge中当左边小于右边时，累加小和

static int merge(int[] a, int left, int mid, int r) {
    int[] help = new int[r - left + 1];
    int p2 = mid + 1;
    int i = 0;
    int p1 = left;
    int sum = 0;//小和初始化
    while (p1 <= mid && p2 <= r) {
        sum += a[p1] < a[p2] ? a[p1] * (r - p2+1) : 0;//merge的小和累加
        help[i++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
    }
    while (p1 <= mid) {
        help[i++] = a[p1++];
    }
    while (p2 <= r) {
        help[i++] = a[p2++];
    }
    for (int j = 0; j < help.length; j++) {
        a[left + j] = help[j];
    }
    return sum;//返回小和
}
  static int mergeSort(int[] a, int left, int right) {
        if (left == right) {
            return 0;
        } else {//返回所有过程的小和并相加
            int mid = left + ((right - left) >> 1);
            return mergeSort(a, left, mid) +
                    mergeSort(a, mid + 1, right) +
                    merge(a, left, mid, right);
        }
    }

逆序对问题

在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对。

举个栗子：3 5 2 1 0 4 9

枚举法：枚举待测位置i，从i+1~n遍历，找出比他小的数的个数，枚举法可得的解有(3,2)，(3,1)，(3,0)，(5,2)，(5,1)，(5,0)，(5,4)，(2,1)，(2,0)，(1,0)。

思想：在merge的过程中返回所有逆序对

static void merge(int[] a, int left, int mid, int r) {
    int[] help = new int[r - left + 1];
    int p2 = mid + 1;
    int i = 0;
    int p1 = left;
    while (p1 <= mid && p2 <= r) {
        /////////////////////////////////////////
        //相比归并排序多增加三行代码，返回所有的逆序对
        if(a[p2]<a[p1]){
            for(int j= p1;j<=mid;j++){
            System.out.println(" "+a[j]+" "+a[p2]);}
        }
        //////////////////////////////////////////
        help[i++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
    }
    while (p1 <= mid) {
        help[i++] = a[p1++];
    }
    while (p2 <= r) {
        help[i++] = a[p2++];
    }
    for (int j = 0; j < help.length; j++) {
        a[left + j] = help[j];
    }
}