(排序二)归并排序java代码加时间复杂度分析
程序员文章站
2022-05-08 22:52:32
...
归并排序时间复杂度分析:
归纳法:
T(n)<2 T(n/2)+cn
T(n)<4 T(n/4)+2 cn
T(n)<8 T(n/8)+3 cn
n个数,依次分层如:
假如n为16,
分为左右,归并的时候遍历次数:n(8+8)
分为4份时(4,4,4,4),归并的时候,先4+4,4+4一次,然后 8+8一次故为2*n次
分为8份时(2,2,2,2, 2,2 ,2,2)归并的时候(2+2,2+2,2+2,2+2)然后(4+4,4+4)然后8+8故为3*n次
当n=2^k时
T(n)<2^K*T(n/(2^k))+k c n =n T(1)+c n log2n=Θ(nlogn)
也可理解为:
16+ 8+8 +4+4+4+4 +2+2+2+2+2+2+2+2(到每层两个数之后不用再细分,递归的时候遇见一个数直接return,遇见两个数直接比较了,已经是最底层)
实际运算的时候并不是一层一层遍历的,而是类似于遍历二叉树(左右中依次遍历的顺序)
额外空间复杂度为O(n)借助了辅助数组
归并排序代码:
递归部分:
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
合并代码:
两个数组进行合并成一个数组:arr数组范围是l,r。分为左数组为l,mid,右数组为mid+1,r,
新建一个数组用来遍历合并,空间复杂度为O(n),常数项的时间复杂度为O(n),遍历完再拷贝回原数组arr,相当于用了两个O(n)(所以从此角度考虑,略输于快排)
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,6,3,5,9,3,4,8,4,0};
mergeSort(a,0,a.length-1);
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
归并排序可以达到稳定性。另外归并排序的额外空间复杂度可以降为O(1)但是很难
(快排与堆排序不能达到稳定性)