- 前言
- 二、归并排序
- 1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
- 1.调用了三个函数，一个防止数组长度小于等于一。
- 2.一个函数用来递归调用子问题
- 3. 一个函数用来合并
- 2）让其整体有序的过程里用了外排序方法
- 2.1外排序指的是额外利用了bigO（N）的空间来储存排序结果
- 2.2这里在合并的函数中额外利用了空间，其中利用的空间，每次不一定相等，但是最大的空间为N
- 3）利用master公式来求解时间复杂度
- 4）归并排序的实质
- 时间复杂度O(N*logN)，额外空间复杂度O(N)代码
- 总结
前言 这次学习到了归并排序它的思想，减少比较，目的是达到更好的时间复杂度，但是有额外的空间O(N)；
二、归并排序 1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序 1.调用了三个函数，一个防止数组长度小于等于一。
public static void mergeSortt(int []arr) {
if(arr == null&& arr.length < 2) {
return;
}
process(arr,0,arr.length - 1);
}
2.一个函数用来递归调用子问题
public static void process(int [] arr,int L, int R) {
if(L == R) {
return;
}
int mid;
mid = L + ((R - L)>>1);
process(arr,L,mid);
process(arr,mid+1,R);
Merge(arr,L,mid,R);
}
3. 一个函数用来合并
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];
}
}
2）让其整体有序的过程里用了外排序方法
2.1外排序指的是额外利用了bigO（N）的空间来储存排序结果
2.2这里在合并的函数中额外利用了空间，其中利用的空间，每次不一定相等，但是最大的空间为N
3）利用master公式来求解时间复杂度
这里调用了两次子函数 a=2;
将问题规模平分了 b =2;
而其他部分的时间复杂度为bigO（N）所以d=1；
所以log（b,a）=d=1
所以时间复杂度为：bigO（N^d*logN）=bigO(NlogN)
4）归并排序的实质归并排序为什么能够实现时间复杂度减少，其实质是减少了比较，在每一次process过程中都能一定程度上继承上次排序的结果比较次数少。从而与冒泡，选择，插入排序不一样，实现了O(NlogN)
时间复杂度O(N*logN)，额外空间复杂度O(N)代码public class mergesort {
public static void mergeSortt(int []arr) {
if(arr == null&& arr.length < 2) {
return;
}
process(arr,0,arr.length - 1);
}
public static void process(int [] arr,int L, int R) {
if(L == R) {
return;
}
int mid;
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];
}
}
public static void main(String[] args) {
int []a= {1,9,4,3,8,5,9,2};
mergeSortt(a);
for(int i = 0 ;i
总结
简单的归并算法就不多说了
