（五）算法基础——分治

#include<stdio.h>
void Merge(int a[],int s,int m, int e,int tmp[]) 
{
//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序，然后再拷贝回a[s,m]
//归并操作时间复杂度：O（e-m+1),即O（n)
int pb = 0,i;
int p1 = s,p2 = m+1; // 两个指针，比较大小，把小的放入数组之后再移动 
while( p1 <= m && p2 <= e) {
	if( a[p1] < a[p2]) 
		tmp[pb++] = a[p1++];
	else 
		tmp[pb++] = a[p2++];
	}
	while( p1 <= m) // 一个数组以及完成，将另一个数组放入 
		tmp[pb++] = a[p1++];
	while( p2 <= e)
		tmp[pb++] = a[p2++];
	for(i = 0;i < e-s+1; ++i)// 拷贝 
	a[s+i] = tmp[i];
}
// 归并排序 
void MergeSort(int a[],int s,int e,int tmp[])
{
	if( s < e) {
		int m = s + (e-s)/2;
		MergeSort(a,s,m,tmp);
		MergeSort(a,m+1,e,tmp);
		Merge(a,s,m,e,tmp);
	}
}

int a[10] = { 13,27,19,2,8,12,2,8,30,89};
int b[10]; 
int main()
{
int size = sizeof(a)/sizeof(int),i;
MergeSort(a,0,size-1,b);
for(i = 0;i < size; ++i)
	printf("%d ",a[i]);
return 0;
}

#include<stdio.h>
void swap(int * a,int * b) //交换变量a,b值
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void QuickSort(int a[],int s,int e)
{
	if( s >= e)
		return;
	int k = a[s];
	int i = s,j = e;
		while( i != j ) {
			while( j > i && a[j] >= k )
				--j;
			swap(&a[i],&a[j]);
			while( i < j && a[i] <= k ) 
				++i;
			swap(&a[i],&a[j]);
	} //处理完后，a[i] = k
	QuickSort(a,s,i-1);
	QuickSort(a,i+1,e);
}
int a[] = { 93,27,30,2,8,12,2,8,30,89};
int main()
{
int size = sizeof(a)/sizeof(int),i;
QuickSort(a,0,size-1);
for(i = 0;i < size; ++i)
	printf("%d ",a[i]);
return 0;
}

#include<stdio.h>
void swap(int * a,int * b) //交换变量a,b值
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void arrangeRight(int a[],int s,int e,int m)
{
	if( s >= e)
		return;
	int k = a[s];
	int i = s,j = e;
		while( i != j ) {
			while( j > i && a[j] >= k )
				--j;
			swap(&a[i],&a[j]);
			while( i < j && a[i] <= k ) 
				++i;
			swap(&a[i],&a[j]);
	} //处理完后，a[i] = k
	
	if(e-i == m){
		return;
		//a = k return 
	}
	if(e-i > m){
		return arrangeRight(a,i+1,e,m);
		//a > k 对最右边a-1个元素再进行arrangeRigth
	}
	if(e-i < m){
		return arrangeRight(a,0,i-1,m-e+i);
		//a < k 对左边b个元素再进行arrangeRight

	}
}
// 快排其实可以用自带的函数，但我还是用了上面自己写的。 
void QuickSort(int a[],int s,int e)
{
	if( s >= e)
		return;
	int k = a[s];
	int i = s,j = e;
		while( i != j ) {
			while( j > i && a[j] >= k )
				--j;
			swap(&a[i],&a[j]);
			while( i < j && a[i] <= k ) 
				++i;
			swap(&a[i],&a[j]);
	} //处理完后，a[i] = k
	QuickSort(a,s,i-1);
	QuickSort(a,i+1,e);
}
int main(void)
{
	int i,m,n,x;
	scanf("%d",&n);
	int a[n];
	for(i = 0;i < n; ++i)
		scanf("%d",&a[i]);	
	scanf("%d",&m);
	//分治 
	arrangeRight(a,0,n-1,m);
	//排序 
	QuickSort(a,m,n-1);
	//输出 
	for(i = n-m;i < n; ++i)
		printf("%d ",a[i]);
	return 0;
}

#include<stdio.h>
int sum = 0;
void Merge(int a[],int s,int m, int e,int tmp[]) 
{
//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序，然后再拷贝回a[s,m]
//归并操作时间复杂度：O（e-m+1),即O（n)
int pb = 0,i;
int p1 = s,p2 = m+1; // 两个指针，比较大小，把小的放入数组之后再移动 
while( p1 <= m && p2 <= e) {
	if( a[p1] < a[p2]) 
		tmp[pb++] = a[p1++];
	else {
		tmp[pb++] = a[p2++];
		sum += m-p1+1; // 计数
	}
		
	}
	while( p1 <= m) // 一个数组以及完成，将另一个数组放入 
		tmp[pb++] = a[p1++];
	while( p2 <= e)
		tmp[pb++] = a[p2++];
	for(i = 0;i < e-s+1; ++i)// 拷贝 
	a[s+i] = tmp[i];
}
// 归并排序 
void MergeSort(int a[],int s,int e,int tmp[])
{
	if( s < e) {
		int m = s + (e-s)/2;
		MergeSort(a,s,m,tmp);
		MergeSort(a,m+1,e,tmp);
		Merge(a,s,m,e,tmp);
	}
}

int a[6] = { 2,6,3,4,5,1};
int b[6]; 

int main()
{
int size = sizeof(a)/sizeof(int),i;
MergeSort(a,0,size-1,b);
	printf("%d",sum); // 输出
return 0;
}