算法-排序-归并排序

文章将会同步到个人微信公众号:Android部落格

1.1 描述

归并排序不断缩小比较范围,每次分为两部分,首先从数组中间分成两边比较,再分别将两边再分割成两部分,直到每个部分为2个元素。

这两个元素比较完成之后,再合并;合并之后再与其他合并部分做比较,再合并,以此循环。

先分开,比较之后在合并成一个整体。最后整体有序。

1.2 代码

static int[] numbers = {5,4,3,7,2,5,1,9,12,6,8,1,34};
public static void merge(int[] array,int left,int right){
	if(left < right){
		int middle = (left + right) / 2;
		merge(array,left ,middle);
		merge(array,middle + 1,right);
		sort(array,left,middle,right);
	}
}

public static void sort(int[] array,int left,int middle,int right){
	int i = left;
	int j = middle + 1;
	int temp = 0;
	while(i <= middle && j <= right){
		if(numbers[i] > numbers[j]){
			array[temp++] = numbers[j++];
		}else {
			array[temp++] = numbers[i++];
		}
	}
	while(i <= middle){
		array[temp++] = numbers[i++];
	}
	while(j <= right){
		array[temp++] = numbers[j++];
	}
	for(int value:array){
		System.out.println("mergeSort array value is:" + value);
	}
	System.out.println("-----------------");
	temp = 0;
	while(left <= right){
		numbers[left++] = array[temp++];
	}
}

public static void mergeSort(){
	int size = numbers.length;
	int[] curArray = new int[size];
	merge(curArray,0,size - 1);
	for(int value:numbers){
		System.out.println("mergeSort value is:" + value);
	}
}

public static void main(String[] args) {
	mergeSort();
}

1.3 总结

  • merge

通过不断递归调用merge方法,确定left,middle,right的值,然后以middle为界,不断递归确定元素的比较范围。

  • sort

将左右范围的元素按照各自的起始序号逐个比较,较小的元素排在前面,较大元素排在后面。

不断加大左右比较范围,然后重复上一步的比较。

sort其实是一个并的过程。

图片来自https://www.cnblogs.com/chengxiao/p/6194356.html