欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(排序二)归并排序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)但是很难

(快排与堆排序不能达到稳定性)

相关标签: 递归