[数据结构与算法]【JAVA】自学笔记DAY6归并排序初学

归并排序主要用于两个或两个以上的有序表合并成一个新的有序表

归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。

目前只学了内排序的两路归并方法--其余后续学习了再补上

时间复杂度o(nlog2n)

由于归并排序每次划分时两个子序列的长度基本一样，所以归并排序最好、最差和平均时间复杂度都是nlog2n。

两路归并排序算法思路:

主要是分治法

分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
合并: 合并两个排好序的子序列,生成排序结果.

public class MergeSort{
	public  void merge(int a[],int left,int mid,int right)
	{
		int temp[]=new int[right-left+1];
		int p1=left,p2=mid+1,k=0;
		//指针标识,p1标识左边第一个元素，p2标识右边第一个元素，k用来放到临时数组
		while(p1<=mid&&p2<=right)
		{
			if(a[p1]<=a[p2])  //通过比较把小的放到临时数组中
			{
				temp[k++]=a[p1++];
			}
			else
			{
				temp[k++]=a[p2++];
			}
		}
		while(p1<=mid) temp[k++]=a[p1++]; //当上半部分有剩余，全部加上
		while(p2<=right) temp[k++]=a[p2++]; //下半部分有剩余，全部加上
		for(int i=0;i<temp.length;i++)//把每一次排好的数组放回去
		{
			a[i+left]=temp[i];//这里一定是i+left,不然就会无限覆盖
		}
	}
	public  void mergesort(int a[],int start,int end)
	{
		if(start<end)//当没有分到只剩一个数就二分
		{
			int mid=(start+end)/2;
			mergesort(a,start,mid);
			mergesort(a,mid+1,end);//递归二分
			merge(a,start,mid,end);//分到只剩两个数，开始递归排序合成
		}
	}
	public void test()
	{
		int []test= { 49, 38, 65, 97, 76, 13, 27, 50 };
		
		mergesort(test,0,test.length-1);
		for(int x:test)
		{
			System.out.print(x+" ");//***For循环遍历数组***//
		}
	}
	public static void main(String[] args)
	{	MergeSort test=new MergeSort();
		test.test();//学习到了 要定义main函数然后要先声明一个对象，再调用函数，不然会报错
	}

}

（1）稳定性
???? 　归并排序是一种稳定的排序。
（2）存储结构要求
??? 　可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度
??? 　对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
（4）空间复杂度
???　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。