插入排序与归并排序

        插入排序的算法原理比较简单，通过构建有序序列来达到排序的目的。比如给出一个数组a，那么首先会将第一个元素作为一个已经排序的序列，然后从第二个元素开始向已经排序的序列（就是第一个元素）从后向前扫描，如果比这个序列中的元素小的话，就插入到相应元素的前面，然后第三个元素再从这两个元素组成的有序序列的后面扫描，找到比它小的位置后就插入，否则结束扫描，以此类推。时间复杂度为O(n*n).
        归并排序的时间效率为O(n * log n),归并排序(MergeSort)的基本思想是：将待排序文件看成为n个长度为1的有序子文件，把这些子文件两两归并，使得到「n/2」个长度为2的有序子文件；然后再把这「n/2」个有序文件的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止，这种排序方法成为二路归并排序。
         插入排序具有空间原址性，任何时候都只需要常数个额外元素空间存储临时数据，但时间复杂度高，而归并排序算法时间复杂度低，但的空间效率不高，需要多耗费一倍的空间。

 

//插入排序
   public void sort(int a[]){
		for(int j = 1;j < a.length;j++){
			int temp = a[j];
			int i = j-1;
			while((i>=0)&&(a[i]>temp)){
				a[i+1] = a[i];
				i = i-1;
			}
			a[i+1] = temp;
		}

	}

  

//归并排序
public void sort(int a[]){
		for(int j = 1;j < a.length;j++){
			int temp = a[j];
			int i = j-1;
			while((i>=0)&&(a[i]>temp)){
				a[i+1] = a[i];
				i = i-1;
			}
			a[i+1] = temp;
		   }
public void merge(int a[],int p,int q,int r){
 		int n1 = q-p+1;
		int n2 = r-q;
		int []b1 = new int[n1+1];
		int []b2 = new int[n2+1];
		for(int i = 0;i < n1;i++){
			b1[i] = a[p+i];
		}
		for(int j = 0;j < n2;j++){
			b2[j] = a[q+j+1]; 
		}
	    b1[n1] = Integer.MAX_VALUE;
	    b2[n2] = Integer.MAX_VALUE;
		sort(b1);
		sort(b2);
		
		int i = 0;
		int j = 0;
		for(int k = p;k<=r;k++){
			if(b1[i]<b2[j]){
				a[k] = b1[i];
				i++;
			}else{
			    a[k] = b2[j];
			    j++;
			}
		}
	}
	
	public void mergeSort(int [] a,int p,int r){
		if(p<r){
			int q = (p+r)/2;
			mergeSort(a, p, q);
			mergeSort(a, q+1, r);
			merge(a, p, q, r);
			
		}
	}