目录

4、归并排序

4.1 归并排序

4.2 315. 计算右侧小于当前元素的个数

5、快速排序

5.1 荷兰国旗问题

5.2 快速排序

---

4、归并排序

4.1 归并排序

1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序

2）让其整体有序的过程里用了排外序方法

3）利用master公式来求解时间复杂度

4）归并排序的实质 时间复杂度0（N*IogN），额外空间复杂度0（N）

public static void process(int[] arr, int L, int R) {
    if(L ==R){
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int M, int R) {
    int[] help = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R) {
        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 (i = 0; i < help.length; i++) {
        arr[L + i] = help[i];//将临时数组的值赋值给原数组，注意是从L开始的
    }
}

4.2 315. 计算右侧小于当前元素的个数

        给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量

输入：nums = [5,2,6,1] 输出：[2,1,1,0] 解释： 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元素 (1) 1 的右侧有 0 个更小的元素

利用归并排序简化思想： 每合并一次就进行一次小于的比较，使得遍历一次就能拿到所有小于当前元素的个数（和）

下面代码是计算左侧小于当前元素的和

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子:[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

public static int process(int[] arr, int i, int r) {
    if(i==r){
        return 0;
    }
    int mid = i +((r -i)>> 1);
    return process(arr, i, mid) + process(arr, mid + 1, r) + merge(arr, i, mid, r);
}
public static int merge(int[] arr, int L, int m, int r) {
    int[] help = new int[r -L + 1];//开辟空间
    int i =0;
    int p1 = L;
    int p2=m+ 1;
    int res = 0;
    while (p1 <= m && p2 <= r){
        res+=arr[p1]< arr[p2]?(r-p2+1)*arr[p1]:0;//只要该值大于左边数组，那么该值右边的一定大于
        help[i++] = anr[p1] < arr[p2] ? arr[pl++]: arr[p2++];//当两值相等的时候必须先插入右边的，否则无法计算右边数组中到底有多少个大于该数的
    }
    while (p1<= m){
        help[i++] = arr[pl++];
    }
    while (p2 <= r) {
        help[i++] =arr[p2++];
    }
    for (i = 0;i < help.length;i++) {
        arr[L + i] = help[i];//会放到arr数组当中，方便下次递归使用
    }
    return res;
}

5、快速排序

5.1 荷兰国旗问题

问题一

快排1.0版本，一次排一个数

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

解题思路：
1）[i] <= num, [i] 与 <=区 的下一个数交换，<=区右扩，i++
2）[i] > num, i++

左侧为 <=区 ，右侧为待定区

问题二（荷兰国旗问题）

快排2.0版本，一次排一堆相同的数

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

解题思路：
1）[i] < num, [i]和<区下一个交换，<区右移，i++
2) [i] == num, i++
3) [i] > num, [i]和>区前一个交换，>区右移，i原地不动（因为交换后还未进行比较）

5.2 快速排序

        快速排序也是一种较为基础的排序算法，其效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一趟只能选出一个最值，有n个元素最多就要执行n - 1趟比较。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。

  快速排序的思想是：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。

  快速排序的步骤如下：

1）先从数列中取出一个数作为基准数。        

2）分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3）再对左右区间重复第二步，直到各区间只有一个数。

        在选择基准值的时候，越靠近中间，性能越好；越靠近两边，性能越差。3.0版本 随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件。把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N。那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望。   

        时间复杂度O(N*logN)，额外空间复杂度O(logN)都是这么来的。

public static void quickSort(int[] arr) {
    if (arr == null || arr.length <2){
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}
​
// arr[1..r]排好序
public static void quickSort(int[] arr, int L, int R) {
    if(L< R){
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0]-1); // < 区
        quickSort(arr, p[1]+1, R); // > 区
    }
}
//这是一个处理arr[1..r]的函数
//默认以arr[r]做划分，arr[r]->p    
p
//返回等于区域（左边界，右边界），所以返回一个长度为2的数组res，res[o]res[1]
public static int[] partition(int[] arr, int L, int R) {
    int less=L-1；//<区右边界
    int more=R;//>区左边界
    while(L< more){ // L表示当前数的位置 arr[R] -> 划分值,当当前位置大于等于>区左边界时跳出
        if(arr[L]//当前数‹划分值
            swap(arr, ++less, L++);
        }else if(arr[L]>arr[R]){//当前数>划分值
            swap(arr, --more, L);
        } else {
            L++;
         }
    }
    swap(arr, more, R);
    return new int[] { less + 1, more };
}