插入排序与归并排序

引用自*：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直至全部序列有序。

归并排序进行如下迭代操作：首先将原始序列看成N个只包含1个元素的有序队列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下一个有序的子序列。

插入排序（直接插入）：

int A[maxn],n;//数组下标为1~n 
void insertsort(){
	for(int i=2;i<=n;i++){//进行n-1趟排序 
		int temp=A[i],j=i;
		while(j>1&&temp<A[j-1]){
			A[j] = A[j-1];
			j--;
		}
		A[j]=temp;
	}
}

 归并排序（2-路归并排序,时间复杂度为O(nlogn))

递归实现

const int maxn=100;
void merge(int A[],int L1,int R1,int L2,int R2){
	int i=L1,j=L2;
	int temp[maxn],index=0;
	while(i<=R1&&j<=R2){
		if(A[i]<=A[j])
			temp[index++]=A[i++];
		else
			temp[index++]=A[j++];
	}
	while(i<=R1)
		temp[index++]=A[i++];
	while(j<=R2)
		temp[index++]=A[j++];
	for(i=0;i<index;i++)
		A[L1+i]=temp[i];
}
void mergeSort(int A[],int left,int right)
{
	if(left<right){
		int mid=(left+right)/2;
		mergeSort(A,left,mid);
		mergeSort(A,mid+1,right);
		merge(A,left,mid,mid+1,right);
	}
}