资讯专栏INFORMATION COLUMN

归并排序

hlcc / 963人阅读

摘要:代码解析自见文中慢慢理解细细入深开辟分配一个辅助临时数组开辟成功之后实现归并之前的划分数组步骤利用之后立刻释放空间开辟失败每一次找中间值依次划分递归划分后左边的新一块递归划分后右边的一块合并已划分排序好的数组一直为标记左半区第一个未排序

代码解析 自见文中

慢慢理解 细细入深

#include#includevoid 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;}

祝你好运

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/121847.html

相关文章

  • 归并排序 - Algorithms, Part I, week 3 MERGESORTS

    摘要:两个单元素数组的合并实际就是对这两个数进行了排序,即变为,同样再对后一组的两个数归并排序,即变为,再将两单元数组归并成四单元数组即和归并为。 前言 本周讲解两个50多年前发明,但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 -- 归并排序,几乎每个软件系统中都可以找到其中一个或两个的实现,并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法...

    Jokcy 评论0 收藏0
  • 归并排序就这么简单

    摘要:归并排序就这么简单从前面已经讲解了冒泡排序选择排序插入排序快速排序了,本章主要讲解的是归并排序,希望大家看完能够理解并手写出归并排序快速排序的代码,然后就通过面试了如果我写得有错误的地方也请大家在评论下指出。 归并排序就这么简单 从前面已经讲解了冒泡排序、选择排序、插入排序,快速排序了,本章主要讲解的是归并排序,希望大家看完能够理解并手写出归并排序快速排序的代码,然后就通过面试了!如果...

    ingood 评论0 收藏0
  • 【算法】归并排序

    摘要:将已有序的子序列合并,得到完全有序的序列即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 前几天卡一个警告卡了几天,vs...

    RebeccaZhong 评论0 收藏0
  • 归并排序

    摘要:概述归并排序法是将两个或两个以上有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。 概述 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 归并排序采用的是递归来实现,属于分而治之,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序...

    CoyPan 评论0 收藏0
  • 带你深入理解 归并排序

    摘要:归并排序文章目录归并排序一合并两个有序数组二递归版本三性能分析四非递归版本前言一优先级队列堆二深入了解快排以及优化归并排序在八大排序中常考的次数,可以说是名列前茅,地位也是很高的不容疏忽,在排序中快速排序,归并排序和堆 ...

    Lsnsh 评论0 收藏0
  • Java排序归并排序

    摘要:排序之归并排序简介归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表,则成为二路合并。对于一个原始的待排序数列,往往可以通过分割的方法来归结为多路合并排序。 Java排序之归并排序 1. 简介 归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表,则成为二路合并。对于一个原始的待排序数列,往往可以通过分割的方法来归结为多路合...

    gityuan 评论0 收藏0

发表评论

0条评论

hlcc

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<