排序算法(4)--归并排序
排序算法(4)--归并排序
haoran_10 发表于1年前
排序算法(4)--归并排序
  • 发表于 1年前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

简介:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

 

一、主要步骤

将待排序数组[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。

综上可知:

归并排序其实要做两件事:

(1)“分解”——将序列每次折半划分

(2)“合并”——将划分后的序列段两两合并后排序

 

二、演示过程

1、先看合并

(1)、两端相邻的有序子数组,arr[start]~arr[mid] 称为数组A和arr[mid+1]~arr[end] 称为数组B

(2)、每次各从数组A和数组B中取出一个值相比较,小的一个放到临时数组C

(3)、最后数组A和数组B中的数据取完时,数组C就是一个有序的合并后的数组。

(4)、最后在临时数组复制到原数组中

2、在看分解

(1)、先把数组分成最细,gap=1,然后把相邻的两个数据合并排序

(2)、然后设置gap=2,继续把相邻的两个数组合并。若子表个数为奇数,则最后一个子表无须和其他子表归并(即本趟处理轮空);

            若子表个数为偶数,则要注意到最后一对子表中后一个子表区间的上限为n-1。

(3)、直到gap等于数组的长度,数组合并完成

 

如图所示:



 

 

 

三、代码实现

@Override
public void sort(int[] arr) {
	mergeSort(arr);
}

private void merge(int[] array,int start,int mid,int end){
	int temp[] = new int[end-start+1];//临时数组
	
	int firstArrIndex = start;//第一段数组序列的下标
	int secondArrIndex = mid+1;//第二段数组序列的下标
	int tempArrIndex = 0;//临时存放数组的下标
	
	//1.扫描第一个数组序列和第二个数组序列
	while(firstArrIndex <=mid && secondArrIndex<=end){
		//1.1 当第一段数组小于第二段数组 未排序的首个元素时
		if(array[firstArrIndex] <=array[secondArrIndex]){
			temp[tempArrIndex] = array[firstArrIndex];
			firstArrIndex++;
		}else{//1.2 当第二段数组小于第一段数组 未排序的首个元素时
			temp[tempArrIndex] = array[secondArrIndex];
			secondArrIndex++;
		}
		
		tempArrIndex++;
	}
	
	//2.当第一段没有复制完全时,将剩余的数组全部复制到临时数组
	while(firstArrIndex<=mid){
		temp[tempArrIndex] = array[firstArrIndex];
		firstArrIndex++;
		tempArrIndex++;
	}
	
	
	//3.当第二段没有复制完全时,讲剩余的数组全部复制到临时数组
	while(secondArrIndex<=end){
		temp[tempArrIndex] = array[secondArrIndex];
		secondArrIndex++;
		tempArrIndex++;
	}
	
	//4.将临时数组复制到原始数组
	for(tempArrIndex=0,firstArrIndex=start;firstArrIndex<=end;tempArrIndex++,firstArrIndex++){
		array[firstArrIndex] = temp[tempArrIndex];
	}
}

private void mergeSort(int[] arr){
	for (int gap = 1; gap < arr.length; gap = 2 * gap) {
		int i=0;
		//归并gap长度的两个相邻子数组
		for(i=0; i+2*gap-1< arr.length; i = i + 2*gap) {
			merge(arr, i, i+gap-1, i+2*gap-1);
		}
		
		// 余下不足两个合并的子数组。保证第一个数组gap存在。
		if(i + gap - 1 < arr.length){
			merge(arr, i, i + gap - 1, arr.length - 1);
		}
	}
}

 

 

标签: 归并排序
共有 人打赏支持
粉丝 27
博文 88
码字总数 80846
×
haoran_10
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: