3. 时间复杂度为n*Log（n）的排序

递归函数

右移

我们在求中点的时候，不使用 的方式，因为这种方式可能导致溢出，计算机带符号数的最大数大概是 21亿多一点，如果有一个数组长度为20亿的数组，我们要取 （20亿-1）和（20亿-2）的中点，在相加的时候就溢出了，所以这种方式不可取。
我们推荐的写法是：

右移一位相当于是除以 2 。
怎么理解：
我们在二进制中，多一位就是多乘一个2，所以舍掉最右位，其实就是除以 2 。

递归函数时间复杂度的估算

递归中所有子问题都是等规模的时候，符合下面的公式：




在递归求最大值的时候，我们求出复杂度是：

求出来的复杂度是符合上面的那个公式的，即：
，而 , d为0，即符合（1），所以复杂度为 O(N)，这跟循环遍历是一样的。

归并排序

1. 整体就是一个简单递归，左边排好序，右边排好序，让整体有序。
2. 整体有序的过程使用了外排序的方法。
3. 使用master公式来求解时间复杂度【T[n] = aT(n/b) + O(n^d)】，a/b === n。
4. 时间复杂度为O(N*logN)，额外空间复杂度O(N)。

使用递归的方式：

// 将数组一分为二【左部分，右部分】，然后各自进行排序
function process(arr,L,R) { 
    if(L === R) return;         // 如果是只有一位，那么直接返回
    const mid = L + ((R-L)>>1); // 找到中位
    process(arr,L,mid);         // 递归，将数组一分为二【还是在原数组上】
    process(arr,mid+1,R);   
    mergeSort(arr,L,mid,R);     // 进行排序
}
// 将一分为二的数组进行排序
function mergeSort(arr,L,M,R) {
    const help = new Array(R-L+1);      // 创建一个L到R位数的数组
    let i = 0, p1 = L, p2 = M+1;        // 赋值双指针
    while(p1<=M && p2<=R){              // 在范围内，数组的两部分进行一一比较
        // help为排序后的数组，如果成功赋值了，i就右移一位
        // 数组左部分跟右部分进行比较，将小的那一位赋值给help，并且右移一位
        help[i++] = arr[p1]>arr[p2] ? arr[p2++] : arr[p1++];
    }
    // 右部分超出边界，将数组左部分剩下的值赋值给help
    while(p1<=M){
        help[i++] = arr[p1++];
    }
    // 左部分超出边界
    while(p2<=R){
        help[i++] = arr[p2++];
    }
    console.log("L为：",L,"arr:为",help);
    // 将排好序的数组重新赋值给原先的arr数组
    for(let i=0; i<help.length; i++){
        arr[L+i] = help[i];
    }
}
const arr = [100,5,2,6,9,25,10,2,4];
process(arr,0,arr.length-1);
console.log(arr);

跟时间复杂度为O（N^2）的区别，像选择排序，第一次比较只搞定了一个数，然后继续往下排序，以此类推，循环一次，只搞定了一个数，而且，每次排序跟下次排序都不相关，冒泡，插入排序都是如此。而归并排序，每次递归都会让数组的一部分变得有序，这跟下一次递归是相关的， 它的比较行为没有浪费，变成一个整体有序的部分，去跟下一个部分合并，所以它的时间复杂度会是O（NlogN）

例子：小和问题、逆序对问题
小和问题：
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和。
eg：
[1,3,4,2,5]
左边比1小的数无，3左边比1小的数：1
4左边比4小的数：1，3
2左边比2小的数：1
5左边比5小的数：1，3，4，2
1+1+3+1+1+3+4+2 = 16，所以为16。
解题思路：
逆过来想，找到右边比当前数大的数，然后使用归并排序找到。

function process(arr,L,R) {
    if(L === R) return 0;
    const mid = L + ((R-L)>>1);
    return process(arr,L,mid)+process(arr,mid+1,R)+merge(arr,L,mid,R);
}
function merge(arr,L,M,R) {
    const help = new Array(R-L+1);
    let p1 = L, p2 = M+1, i = 0, res = 0;
    while(p1<=M && p2<=R){
          // 如果在比较的过程中，左边小于右边，那就直接统计个数
        res += arr[p1] < arr[p2] ? (R-p2+1)*arr[p1] : 0;    
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while(p1<=M){
        help[i++] = arr[p1++];
    }
    while(p2<=R){
        help[i++] = arr[p2++];
    }
    for(let i=0; i<help.length; i++){
        arr[L+i] = help[i];
    }
    return res;
}
const arr = [1,3,4,2,5];
const res = process(arr,0,arr.length);
console.log(res);

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

快速排序

荷兰国旗问题

1. 给定一个数组arr，和一个数num，请把小于num的数挡在数组的左边，大于等于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。

?=> 将数组分为两部分，第一个部分是小于区域，第二部分是大于等于区域，分两种情况：

1. arr[i]<num,arr[i]和小于区域的下一个数交换，右扩小于区域，i++；
2. arr[i]>=num,i++；

1. （荷兰国旗问题）给定一个数组arr，和一个数num，请把小于num的数挡在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。

?=>将数组分为三部分，小于区域，等于区域，大于区域，分三种情况：

1. arr[i]<num,arr[i]和小于区域下一个数交换，右扩小于区域，i++；
2. arr[i]=num,i++；
3. arr[i]<num,arr[i]和大于区域前一个数交换，大于区域左扩，i不动。

当i跟大于区域撞上了，就停止。

function quickSort(arr,L,R){
    if(L<R){
        swap(arr,L+Math.floor(Math.random()*(R-L+1)),R);
        const p = partition(arr,L,R);
        quickSort(arr,L,p[0]-1);
        quickSort(arr,p[1]+1,R);
    }
}
function partition(arr,L,R){
    let less = L-1, more = R;
    while(L<more){
        if(arr[L] < arr[R]){
            swap(arr,++less,L++);
        }else if(arr[L] > arr[R]){
            swap(arr,L,--more);
        }else{
            L++;
        }
    }
    swap(arr,more,R);
    return [less+1,more];
}
function swap(arr,left,right){
    const tmp = arr[left];
    arr[left] = arr[right];
    arr[right] = tmp;
}