算法之5分治法实现合并排序

2.5 合并排序(merge sort)

2.5.1 算法思路

总体步骤：

• ① 拆分
• ② 合并，边合并边排序

详细的解释在2.5.2代码注释中

2.5.2 代码及注释

public static int[] mergeSort(int[] originalData){
	int [] sortedData=originalData.clone;//拷贝一份原数组，用来存排好序的数组
	int [] tempData=originalData.clone;//辅助数组，用来保存排序好的一部分数组，
	mergeSort(SortedData,0,sortedData.length-1,tempData);
	return SortedData;
}
/////////////////////////////////////
private static void mergeSort(int[] sortedData,int head,int tail,int[] tempData){
	/*较为重要的代码*/
	if(head==tail)return;//拆分到只剩一个元素时
	mergeSort(sortedData,head,head+(tail-head)/2,tempData);//前半段
	mergeSort(sortedData,head+(tail-head)/2+1,tail,tempData);//后半段
	merge(sortedData,head,tail,tempData);//合并
}
///////////////////////////////////
private static void merge(int[] sortedData,int head,int tail,int[] tempData){
	int firstPartIndex=head;//指向前半段的第一个元素
	int secondPartIndex=head+(tail-head)/2+1;//指向后半段的第一个元素
	int mergeIndex=head;
	/*核心代码*/
	for(;mergeIndex<=tail;mergeIndex++){//遍历地比较前半段和后半段的元素大小，并赋值到辅助数组里
		if(firstPartIndex<=head+(tail-head)/2&&secondPartIndex<=tail){//如果前半部分和后半部分都还没比完
			if(sortedData[firstPartIndex]<sortedData[secondPartIndex]){
				tempData[mergeIndex]=sortedData[firstPartIndex];
				firstPartIndex++;	
			}
			else{
				tempData[mergeIndex]=sortedData[secondPartIndex];
				secondPartIndex++;	
			}
		}
		else if(firstPartIndex<=head+(tail-head)/2){//如果前半段还有数，而后半段没有了，就把前半段的数全部赋值给辅助数组
			while(firstPartIndex<=head+(tail-head)/2){
				tempData[mergeIndex++]=sortedData[firstPartIndex++];//这里因为是在while循环里，所以mergeIndex也要记得+1
			}
		}
		//如果后半段还有数，而前半段没有了。或者，两者均无。则无需任何操作。
		//为什么后半段还有数，却无需任何操作？
		//后半段如果还有数，按照之前的思路，我们应该先把后半段剩下的数存到tempData，可是所有tempData的数，最后我们还是要赋值给sortedData数组呀。那么，这种情况下，也就意味着当前sortedData中保存的后半段剩余元素的排序是正确的，即无需任何操作.
		else{
			break;
		}
	}
	for(int i=head;i<=Math.min(tail,mergeIndex);i++){
		sortedData[i]=tempData[i];//把前面得到的辅助函数的值重新赋值给sortedData
	}
}

2.4.3 时间复杂度

时间复杂度：Θ(nlog₂n)
分析：下图中“合并排序”操作对应mergeSort()，“合并”操作对应merge()