归并排序

代码解析 自见文中

慢慢理解 细细入深

#include
#include
void Print(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d", arr[i]);
	}
}
void merge_sort(int arr[],int sz)
{
	//开辟分配一个辅助临时数组
	int* temparr = (int*)mallco(sz * sizeof(int));
	if (temparr)
	{
		//开辟成功之后 实现归并之前的划分数组步骤
		msort(arr,temparr, 0, sz - 1);
		//利用之后 立刻释放空间
		free(temparr);
	}
	else//开辟失败
	{
		printf("error:failed to allocate memory");
	}
}
void msort(int arr[],int temparr[] ,int left, int right)
{
	int mid = (left + right) / 2;//每一次找中间值 依次划分
	if(left <= right)
	{
		msort(arr,temparr, left,mid);//递归划分后左边的新一块
		msort(arr,temparr, mid + 1, right);//递归划分后右边的一块
		merge(arr, temparr, left, right, mid);//合并已划分排序好的数组
	}
}
void merge(int arr[], int temparr[], int left, int right, int mid)
{
	//left一直为0
	int L_pos = left;//标记左半区第一个未排序的数字
	int R_pos = right;//标记右半区第一个未排序的数字
	int pos = left;//临时数组的下标
	while (L_pos <= mid && R_pos <= right)
	{
		//每次分别把左右半区的第一个元素拿出来进行比较大小
		if (arr[L_pos] > arr[R_pos])
		{
			temparr[pos] = arr[R_pos];
			pos++;
			R_pos++;
		}
		else
		{
			temparr[pos] = arr[L_pos];
			pos++;
			L_pos++;
		}
	}
	//当左半区排完之后 右半区剩余依次放进去
	while (L_pos <= mid)
	{
		temparr[pos] = arr[L_pos];
		pos++;
		L_pos++;
	}
	//同理可得
	while (R_pos <= right)
	{
		temparr[pos] = arr[R_pos];
		pos++;
		R_pos++;
	}
	//把临时数组合并后的元素放到原来的数组
	while (left <= right)
	{
		//left在这同样初始为0开始
		arr[left] = temparr[left];
		left++;
	}
}
int main()
{
	int arr[] = { 9,5,2,7,12,4,3,1,11 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Print(arr, sz);
	printf("\n");
	merge_sort(arr,sz);
	Print(arr, sz);
	return 0;
}

祝你好运

你可能感兴趣的