数据结构与算法---- 认识O(NlogN)的排序
一、递归算法
1.1 实例代码
递归算法的求解过程是将整个问题划分为若干个子问题，然后分别求子问题，最后获得整个问题的解。这是一种分而治之的思路，通常由整个问题划分的若干子问题的求解是独立的，所以求解过程对应一颗递归树
示例：求arr[L…R]上的最大值
思路：先求出中点，把数组分为两个区域，arr[L]-arr[mid]和arr[mid+1]-arr[R]
/*
* 递归算法
* 实例：得到一个最大值
* */
public class Recursion {
public static int getMax(int[] arr){
return process(arr,0,arr.length-1);
}
//arr[L..R]范围上求最大值
public static int process(int[] arr, int L, int R) {
if (L == R){ //只有一个数的时候直接返回
return arr[L];
}
int mid = L+((R - L) >> 1); //>>:右移一位，相当于除2
int leftMax = process(arr, L, mid); //左部分
int rightMax = process(arr,mid+1,R); //右部分
return Math.max(leftMax,rightMax);
}
public static void main(String[] args) {
int[] arr ={3,2,5,6,7,4};
System.out.println(Recursion.getMax(arr));
}
/*
* master算法
* 原理：T(N)=aT(N/b)+O(N^d) 子函数范围要相等
* a:调了几次子函数 b:子函数的范围 d:看其他执行的时间复杂度
* 判断master递归
* logb^a<d o(N^d)
* logb^a>d o(N^(logb^a))
* logb^a=d o(N^d*logN)
* */
}
1.2 中点溢出问题
上面代码求中点是这行代码
int mid = L+((R - L) >> 1);
//等同于
int mid = L + (R-L)/2
为什么要这样用呢？可以不可以这样写？
int mid=（L+R）/2；
如果是这样求中点的话，会存在一个问题，如果数组的长度比较大，L+R可能会溢出
1.3 递归结构
假设测试的数组是[3,2,5,6,7,4]
运行结果：:
7
递归的每次往底层调用是这样的结构图
从这个递归结构图可以看出，所有的子节点汇总之后才能得到最终的P（0,5）。所以递归过程实际上就是用系统栈把整个过程压栈了，假设P（0,5）进栈，遇到调用P（0,2），将P（0,2）信息进栈，执行时又遇到P（0,1），再将P（0,1）进栈，以此类推。栈的空间就是整棵树的高度。
这其实就是二叉树遍历的过程。
经过调试就会发现，每一层递归得到的结果都返回给上一层，所以可以将其看做从底部不断往上汇总的一个过程
二、Master公式
Master公式是用来解决递归问题时间复杂度的公式。
公式如下：
T[N] = aT[N/b] + O(N^d)
注意：适用范围为子过程规模相等的情况，否则不适用。
分解看
T[n]：母问题的数据的规模是N
T[n/b]：子问题的规模都是N/b
a：子问题被调用的次数
O(N^d)：除去子问题调用之外过程的时间复杂度
用上面求解最大数的递归解法来看
T[N] = aT[N/b] + O(N^d)
=2T[N/2] + O(1)<–两个数最后比大小，时间复杂度为O(1)
所以上面的函数满足master公式，可以直接得到时间复杂度
①当d<log(b)a时，时间复杂度为O(N^(log(b)a))
②当d=log(b)a时，时间复杂度为O((N^d)*logN)
③当d>log(b)a时，时间复杂度为O(N^d)
证明过程略
三、归并排序
3.1 实例代码
1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
2）让其整体有序的过程用了排外序方法
3）利用master公式来求解时间复杂度
4）归并排序的实质
时间复杂度O(N*logN)，额外空间复杂度O(n)
/*
* 归并（合并）排序，整体就是一个简单递归，左边排好序，右边排好序，让其整体有序
* 左右两边都有一个指向第一个数的指针，每次进行比较，小的数放进（新）数组中，
* 一样大，默认放左边，如果哪侧越界了，就把剩下的部分拷贝过来就行了
* */
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
//递归
private 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);
}
//归并
private static void merge(int[] arr, int L, int M, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L; //指向左边的第一个指针1
int p2 = M + 1; //指向右边的第一个指针2
while (p1 <= M && p2 <= R) { //如果指针1和指针2没有越界
//新数组里依次放入，哪边指针的值小哪边放进去
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= M) { //如果p2指针（右半边）越界了，就把左半边的值全部放进去
help[i++] = arr[p1++];
}
while (p2 <= R) { //如果p1指针越界了（左半边），就把右半边所有的值全部放进去
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) { //把新数组的值
arr[L + i] = help[i];
}
}
}
归并步骤如下：
1、在process(arr,L,mid);里让左边有序
2、在process(arr,mid+1,R);里让左边有序
3、用merge方法得到新排序好的数组
很多人不太明白为什么process里面就已经排好序了。这里依然用是递归方法，所以还是用结构图来解释
调用时merge()是在process()里面的，所以每次递归的时候都会调用merge()，所以排序实际上是在每次递归调用merge()里进行的。
例如：第一次递归调用到merge()时是左部分P(0,0)和P(1,1)，也就是子问题的相对左边(3)和相对右边(2)进行归并。通过算法得2先放进新数组help[]中，3再放入。所以传递给P(0,1)父问题的时候就已经排好序了---->[2,3]---->以此类推，最终汇总到P(0,5)的时候就是所有数有序
3.2 时间复杂度
所以说归并排序就是一个简单的递归，在此题中也是满足master公示的，它的时间复杂度为：
T(N) = 2T(N/2) + O(N)
a=2 b=2 d=1 ---->d=log(b)a
所以时间复杂度为O(N*logN)
3.3 额外空间度复杂度
归并排序的额外空间复杂度是O(N)
因为最多只用N的额外空间，每一次merge的时候都准备了一个空间，然后自动释放了（java里会自动释放）。所以最多申请一个长度为N的空间就可以了，不断复用，其额外空间复杂度就是O(N)
3.4 小和问题
问题描述：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和。
例子：[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
实现O(N*logN)
解题思路：把题目转换为，右边有多少个数比该数大，则产生多少该小和
例如：
1右边比1大的数，4个，产生4个1小和；
3右边比3大的数，2个，产生2个3小和；
…
然后用归并的方法，在左右两边，对比得到需产生的小和数（具体见代码）
/*
* 小和问题
* 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和
* */
class SmallSum {
public static void main(String[] args) {
int[] arr = {1, 3, 4, 2,5};
System.out.println(SmallSum.smallSum(arr));
}
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
//arr[L,R]既要排好序，也要求小和
private static int process(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) //左侧排序并且求小和的数量
+ process(arr, mid + 1, r) //右侧排序求小和的数量
+ merge(arr, l, mid, r); //左右都排好merge时候产生小和的数量
}
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) {
//左组比右组小？是，就把把右组后面所有数的个数（r-p2+1）乘以左组，即这次比较的小和数
//这里要知道，左右两边都是有序排好了的，才可以这样
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 (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return res;
}
}
运行结果：
16
四、快速排序3.0
4.1 实例代码
package Algorithm;
//快速排序3.0
public class QuickSort {
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 ==p >p
//返回等与区域（左边界，右边界），所以返回一个长度为2的数组res,res[0] res[1]
private static int[] partition(int[] arr, int L, int R) {
int less = L -1; //<区右边界
int more = R; //>区左边界
while (L < more){
if (arr[L] < arr[R]){
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};
}
//随机选的数和最右侧的数交换位置
private static void swap(int[] arr, int random, int R) {
int temp = arr[R];
arr[R] = arr[random];
arr[random] = temp;
}
}
总结
这节课主要学习了递归算法，归并排序，用来计算递归算法时间复杂度的master公式和快速排序
湘公网安备 43102202000103号