Java教程

归并排序java

本文主要是介绍归并排序java,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

左边排好序,右边排好序,整体排好序

归并排序

private void mergeSort(int[] arr){
	if (null == arr || arr.length < 2){
		return;
	}
	mergeSort(arr,0,arr.length-1);
}


private void mergeSort(int[] arr, int left, int right){
	if (left == right){
		return;
	}
	int mid = left + ((right-left)>>1);
	mergeSort(arr, left, mid);
	mergeSort(arr, mid+1, right);
	merge(arr,left,right,mid);
}

private void merge(int[] arr, int left, int right, int mid){
	int pos1 = left;
	int pos2 = mid+1;
	int[] temp = new int[right-left+1];
	int index = 0;
	while(pos1<=mid&& pos2<=right){
		temp[index++] = arr[pos1] <= arr[pos2] ? arr[pos1++] : arr[pos2++];
	}
	while(pos1<=mid){
		temp[index++] = arr[pos1++];
	}
	while(pos2<=right){
		temp[index++] = arr[pos2++];
	}
	//将排序好的数组合并到原数组中
	//System.arraycopy(temp, 0, arr, left, temp.length);
	//上面的代码等价于
	for(int j=0; j<temp.length; j++){
		arr[left+j] = temp[j];
	}
}

小和问题

【题目】
在一个数组中,每一个数左边比当前数小的数字累加起来,叫做这个数组的小和。

【例子】
[1,3,4,2,5],1左边比1小的数为0,3左边比3小的数,1;4左边比4小的数,1和3;2左边比2小的数字,2,5左边比5小的数字,1,3,4,2,所以小和为
1+1+3+1+1+3+4+2=16

【思路】
每次递归,左侧数据和右侧数据必定是已经排好序的,只是需要将两侧数据进行合并。所以当左侧a数据比右侧b数据小时,必定也小于b右侧的数据,假设参与整合排序的左侧数据是[1,3,6],右侧堆数据是,[2,4,5],可以看出1比右侧的2小,那么1必定比2后面的数都小,所以需要加起来的1的个数是右侧数组里比1大的数据的个数,也就是3个,同理,3小于4,以及4后面的5,有2个,那么这部分的小和就是31+23=9

【代码】

private int getSmallSum(int[] arr){
	int sum = mergeSort(arr);
	System.out.print("小和是="+sum);
}

private int mergeSort(int[] arr){
	if(null == arr || arr.length < 2){
		return 0;
	}
	return mergeSort(arr, 0, arr.length-1);
}

private int mergeSort(int[] arr, int left, int right){
	if (left == right){
		return 0;
	}
	int mid = left + ((right-left)>>1);
	int sumLeft = mergeSort(arr, left, mid);
	int sumRight = mergeSort(arr, mid+1, right);
	int mergeSum = merge(arr, left, right, mid);
	return sumLeft+sumRight+mergeSum;
}

private int merge(int[] arr, int left, int right, int mid){
	int pos1 = left;
	int pos2 = mid + 1;
	int sum = 0;
	int[] temp = new int[right-left+1];
	int index = 0;
	while(pos1<=mid && pos2<=right){
		sum += arr[pos1]<arr[pos2] ? arr[pos1]*(right-pos2+1) : 0;
		temp[index++] = arr[pos1]<arr[pos2] ? arr[pos1++] : arr[pos2++];
	}
	while(pos1<=mid){
		temp[index++] = arr[pos1++];
	}
	while(pos2<=right){
		temp[index++] = arr[pos2++];
	}
	System.arraycopy(temp, 0, arr, left, temp.length);
	return sum;
}

逆序对

【题目】
在一个数组中,如果左边的数比右边的数大,则这两个数字构成一个逆序对,打印所有逆序对

【思路】
与归并排序类似,只不过是逆序,归并排序时按照由大到小的顺序排序,左侧和右侧作比较,左侧大于右侧某一数字时,必定也大于该数字右侧的所有数字。因为归并排序左右两侧必定是排好序的,倒序。

private void printInversion(int[] arr){
	mergeSort(arr);
}

private void mergeSort(int[] arr){
	if (null == arr || arr.length < 2){
		return;
	}
	mergeSort(arr, 0, arr.length-1);
}

private void mergeSort(int[] arr, int left, int right){
	if(left == right){
		return;
	}
	//此处一定记得加(),>>的优先级远低于+,如果没有括号或导致先算加号,再进行位运算
	int mid = left + ((right-left)>>1);
	mergeSort(arr, left, mid);
	mergeSort(arr, mid+1, right);
	merge(arr, left, right, mid);
}

private void merge(int[] arr, int left, int right, int mid){
	int[] temp = new int[right-left+1];
	int index = 0;
	int pos1 = left;
	int pos2 = mid + 1;
	while(pos1<=mid && pos2<=right){
		if (arr[pos1] > arr[pos2]){
			int len = right-pos2;//pos2包括pos2右侧的都是小于arr[pos1]的。
            int i = 0;
			while(i<=len){
				System.out.print(arr[pos1]+"-"+arr[pos2+i]+" , ");
				i++;
			}
			temp[index++] = arr[pos1++];
		} else {
			temp[index++] = arr[pos2++];
		}
	}
	while(pos1<=mid){
		temp[index++] = arr[pos1++];
	}
	while(pos2<=right){
		temp[index++] = arr[pos2++];
	}
	System.arraycopy(temp, 0, arr, left, temp.length);
}
这篇关于归并排序java的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!