分治法-绝对值排序

大佬原文 原文链接

特此记录，便于复习

#include<stdio.h> 
// malloc() 动态分配
#include<malloc.h>
// fabs() 绝对值函数 
#include<math.h>
 
void input(int *A, int n);
void Mesort(int *A, int *B, int left, int right);
void Merge(int *A, int *B, int left, int middle, int right);
void copy(int *A, int *B, int left, int right);
void output(int *A, int n);

int main(){
	int *A, *B, n;
	while(scanf("%d", &n) != EOF && n != 0){
		// 开辟空间
		A = (int *)malloc(sizeof(int) * n);
		B = (int *)malloc(sizeof(int) * n);
		// 输入
		input(A, n);
		// 递归 分治法 先拆分 再合并排序 
		Mesort(A, B, 0, n - 1); 
		// 输出
		output(A, n); 
		// 释放空间
		free(A);
		free(B); 
	}
	return 0;
}

// 输入
void input(int *A, int n){
	for(int i = 0; i < n; i++){
		scanf("%d", &A[i]);
	}
} 

// 递归 分治法 先拆分 再合并排序
void Mesort(int *A, int *B, int left, int right){
	// 当左侧少于右侧说明没有拆分到底 继续拆分 
	if(left < right){
		// 求出中间值 进行拆分
		int middle = (left + right) / 2;
		// 左右两侧同时递归 继续拆分 直至不再满足要求为止
		// 递归左侧 
		Mesort(A, B, left, middle);
		// 递归右侧 
		Mesort(A, B, middle + 1, right);
		// 合并排序
		Merge(A, B, left, middle, right);
		// 将数组B[]  复制给A[]
		copy(A, B, left, right); 
	}
}

// 合并排序
void Merge(int *A, int *B, int left, int middle, int right){
	// i 表示左侧数组第一个数的位置 
	int i = left;
	// j 表示右侧数组第一个数的位置 
	int j = middle + 1;
	// 相当于一个指针记录位置 给它初始左侧第一个数的位置 
	int m = left; 
	// 左右两端同时遍历  进行排序合并 
	while(i <= middle && j <= right){
		// 左右两端比较，大的数值先放入到B[] 进行保存 
		if(fabs(A[i]) >= fabs(A[j])){
			// m++ 该位置存放上以后 +1 让下一个好继续存放 
			//  左侧i位置的数大于右侧j位置的数值 存放完后 位置加一 方便下次循环的时候下一个位置与右侧j位置数值进行比较 从而做到合并排序 
			B[m++] = A[i++];
		}else{
			//  右侧j位置的数大于左侧i位置的数值 存放完后 位置加一 方便下次循环的时候下一个位置与左侧i位置数值进行比较 
			B[m++] = A[j++]; 
		}
	} 
	// 当一侧的数值都比较完后，将剩余的部分插入到数组后面即可
	if(i > middle){
		// 当i大于middle 说明左侧比较完了，右侧有剩余,将右侧插入数组
		for(int q = j; q <= right; q++){
			B[m++] = A[q];
		}	
	}else{
		// 当i小于middle 说明右侧比较完了，左侧有剩余,将左侧插入数组
		for(int q = i; q <= middle; q++){
			B[m++] = A[q];
		} 
	}
}

// 把排好序的部分B[],复制回A[]、
void copy(int *A, int *B, int left, int right){
	for(;left <= right; left++){
		A[left] = B[left];
	}
} 

// 输出
void output(int *A, int n){
	for(int i = 0; i < n; i++){
		printf("%d ", A[i]);
	}
	printf("\n");
}