归并排序(mergeSort)及其拓展_归并算法求最大值

归并排序(mergeSort)

• 在学习归并排序之前，我们先考虑一下如何求一个数组的最大值呢？
  我们首先想到的是将数组遍历一遍比较大小记录最大值，但如果要使用递归实现呢？我们可以将数组分割等长的两部分，求出两侧各自的最大值，最后取其中的最大值，对分割两部分进一步分割（递归）直到数组只有一个值返回即可。

public class GetMax {
	//递归求最大值
	//将一个数组分割成两部分通过递归求出
	//求出左边的最大值，和左边的最大值，最后取一个最大值
	public static void main(String[] args) {
		int arr[] = {1,3,5,2,3,7,4};
		System.out.println(getMax(arr));
	}
	public static int getMax(int[] arr) {
		return process(arr, 0, arr.length-1);
	}
	public static int process(int[] arr,int L,int R) { 
		//arr为需要查找最大值的数组，L为数组的开始位置，R为数组的结束位置
		if(L==R) {
			//递归结束条件，到L==R使分割数组中只有一个值当然是最大值
			return arr[L];
		}
		//mid数组的中间位置 即（R+L)/2 为防止R+L过大超范围（int有范围） 开始位置加上一半也是中间值
		// >> 右移运算符 >>n相当于除以2的n次方 << 左移运算符 <<n相当于乘以2的n次方
		int mid = L + ( (R-L)>>1 );
		int rightMax = process(arr, L, mid);//递归求左侧最大值
		int leftMax = process(arr, mid+1, R);//递归求右侧最大值
		return Math.max(rightMax,leftMax); //返回左右两侧的最大值
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

到这里我们利用这种思想我们可以将一个数组分成两个数组，如果这两个数组已经排好序了那我们就只需将这两个数组从小到大归并到一个新的数组中即可，最后将归并好的数组保存到需要排序的数组中就可以完成排序。

画的丑，作者就这水平了，不喜勿喷！！！

package Sort;

public class MergeSort {
	//归并排序
	public static void main(String[] args) {
		int [] arr = {1,5,3,2,7,4};
		mergeSort(arr);
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
	}
	public static void mergeSort(int[] arr) {
		if(arr==null||arr.length<1) {
			//如果数组为空则无法进行排序，如果arr的长度只有一个则不需要排序
			return ;
		}
		process(arr,0,arr.length-1);
	}
	public static void process(int[] arr,int L,int R) {
		if(L==R) {
			//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 mid, int R) {
		//创建一个辅助数组，将两侧数组归并到help辅助数组中在将其保存到arr数组中
		int help[] = new int[R-L+1];
		int p1=L;//左侧数组指针，即向左侧角标
		int p2=mid+1;//右侧数组针织，即右侧角标
		int i=0;//辅助数组角标
		while(p1<=mid&&p2<=R) {
			help[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
			//三元运算符前面条件成立冒号前的语句执行，否则冒号后的语句执行
		}
		while(p1<=mid) {
			help[i++] = arr[p1++];
		}
		while(p2<=R) {
			help[i++] = arr[p2++];
		}
		//这两个while最多只会执行其中一个，因为在第一个while中已经有一个条件不成立了
		for(i =0;i<help.length;i++) {
			arr[L+i] = help[i];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

注意：归并排序的时间复杂度为O(N*logN)，空间复杂度为O(N)
原因去搜一下其他作者的吧，作者懒加上作者也不太明白

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

    当我们看到这问题是首先想得就是暴力解决，两层for循环直接完事，(嗯我也是这么想得)但是这种方法的时间复杂度是O(N^2) 对这个问题我们完全可以用归并排序一并解决，这种方法时间复杂度只是O(NlogN)。
    我们首先要转变思想求每一个数左边比当前数小，那不就是右侧比这个数大的之和

有了这个思想之后我们只需要在归并时，如果左侧的数小于右侧的数，那么我们就可以直接数出(R-p2+1)比这个数(arr[p1]大的个数，如果左侧大于右侧就不用变了，因为在之前的归并是这个数已经计算过了，所以才不会重(这里作者也不知道该怎么说了/头秃反正就这样,直接看代码吧)

	package Sort;

public class smallSum {
	//求小和
//	static int res=0;可以保存结果这样就可以不用设置返回值
	public static void main(String[] args) {
		int[] arr = {1,3,5,2,4};
		int res=getSmallSum(arr);//记录结果
		System.out.println(res);
	}
	public static int getSmallSum(int[] arr) {
		if(arr==null||arr.length<1) return 0; //数组不存在或者长度为一的时候小和为0
		return process(arr, 0, arr.length-1);
	}
	public 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);
	}
	private static int merge(int[] arr, int L, int mid, int R) {
		int[] help = new int[R-L+1];
		int res=0;//记录被分割数组的小和
		int p1=L,p2=mid+1,i=0;//见mergeSort
		while(p1<=mid&&p2<=R) {
			res+= arr[p1]<arr[p2]? (R-p2+1) * arr[p1] :0;
			//因为右侧数组已经排好序了所以p2以后的数都比p1大所以直接R-p2+1乘以arr[p1]即可
			help[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];//排序
		}
		//两个while处理以越界但为保存的数
		while(p1<=mid) {
			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;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

最后告知一下各位，作者也是小白，这篇文章只是记录自己的思路，可能有许多地方说的不对或者理解不正确，不喜勿喷！！不喜勿喷
最后的最后附上左神讲解的地址左神讲解的算法B站左神讲的很明白可以去看一下