Tow Pointers

1. 给定一个正整数序列和一个正整数M，求序列中的两个不同位置的数a和b，使a+b=M

    while(i<j){
		if(a[i]+a[j]==m){
			printf("%d %d\n",i,j);
			i++;
			j--;
		}else if(a[i]+a[j]<m){
			i++;
		}else{
			j--;
		}
	}

2.序列合并问题，假设有两个递增序列A和B，要求将它们合并为一个递增序列C

int merge(int A[],int B[],int C[],int n,int m){
	int i=0,j=0,index=0 ; //i指向A[0],j指向B[0]
	while(i<n && j<m){
		if(A[i]<=B[j])
			C[index++]=A[i++];
		else
			C[index++]=B[j++];
	}
	while(i<n) C[index++] = A[i++];  // 将序列A的剩余元素加入序列C
	while(j<m) C[index++] = B[j++];  // 将序列B的剩余元素加入序列C
	return index; //返回序列C的长度
}

3.归并排序

//递归实现
const int maxn=100;
	//将数组A的[L1,R1]与[L2,R2]区间合并为有序区间（此处L2即为R1+1）
void merge(int A[],int L1,int R1,int L2,int R2){
	int i = L1,j=L2; //i指向A[L1],j指向A[L2]
	int temp[maxn],index=0; // temp临时存放合并后的数组，index为下标
	while(i<=R1 && j<=R2){
		if(A[i]<=A[j]) 
			temp[index++]=A[i++]; //将A[i]加入序列temp
		else
			temp[index++]=A[j++]; //将A[j]加入序列temp  
	}
	while(i<=R1) temp[index++] = A[i++]; //将[L1,R1]的剩余元素加入序列temp
	while(j<=R2) temp[index++] = A[j++];
	for(i=0;i<index;i++){
		A[L1+i]=temp[i];  //将合并后的序列赋值回数组A
	}
}
//将array数组当前区间[left,right]进行归并排序
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);
	}
}

4.快速排序

//对区间[left,right]进行划分
int Partition(int A[],int left,int right){
	int temp=A[left]; //将A[left]存放至临时变量temp
	while(left<right){ //只要left与right不相遇
		while(left<right && A[right]>temp) right--;  //反复左移right
		A[left] = A[right];				//将A[right]挪到A[left]
		while(left<right && A[left]<=temp) left++; //反复右移left
		A[right] = A[left]; //将A[left]挪到A[right]
	}
	A[left] = temp; //把temp放到left与right相遇的地方
	return left;    // 返回相遇的下标
}
//快速排序
void quickSort(int A[],int left,int right){
	if(left<right){   //当前区间的长度超过1
		//将[left,right]按A[left]一分为二
		int pos = Partition(A,left,right);
		quickSort(A,left,pos-1);  //将左子区间递归进行快速排序
		quickSort(A,pos+1,right); //将右子区间递归进行快速排序
	}
}