您的位置:首页 > 新闻 > 热点要闻 > 大型电商网站开发方案_企业策划是什么意思_google play商店_房产网站建设

大型电商网站开发方案_企业策划是什么意思_google play商店_房产网站建设

2024/12/25 1:30:09 来源:https://blog.csdn.net/weixin_72492465/article/details/143605337  浏览:    关键词:大型电商网站开发方案_企业策划是什么意思_google play商店_房产网站建设
大型电商网站开发方案_企业策划是什么意思_google play商店_房产网站建设

归并排序(Merge Sort)

归并排序是一种分治算法(Divide and Conquer),用于将一个无序数组或链表按照一定的顺序排序(通常是升序)。归并排序的核心思想是:将数组分为两个子数组,分别排序后再合并起来,最终得到一个有序的数组。

有两种方法实现归并排序

第一种是迭代法(自底向上归并法),第二种是递归法(自顶向下归并法)

迭代法

通过增加归并排序区间,多次小区间的归并,从而实现整个数组的排序

void sort_(int*,int,int,int);
void merge_sort1(int* nums,int length)
{ int* temp=new int[length];    for(int i=1;i<length;i*=2)       //不断增加归并区间i{   int index=0;                 //归并区间距离改变 从头开始迭代 /*可以分配2个i区间*/while(index+2*i<=length)      {index+=2*i;               sort_(nums,temp,index-2*i,index-i,index); //2*i的区间 归并左i区间和右i区间}/不足以分配2个i区间/if(index+i<length)  sort_(nums,temp,index,index+i,length);}  delete []temp; 
}
void sort_(int* nums,int* temp,int start,int mid,int end) //头闭尾开
{cout<<"归并的区间为"<<start<<" "<<mid<<" "<<end<<endl;int l=start;int r=mid;int index=0;while(index<end-start){    if(l<mid&&(r==end||nums[l]<nums[r]))  //当左边小于右边或者右区间没有数据时{temp[index++]=nums[l++];   }  else temp[index++]=nums[r++];}  /*拷贝数据*/for(int i=0;i<end-start;i++){nums[i+start]=temp[i];       }
}

通过改变归并区间大小不断的扫描整个数组

递归法

void sort_(int*,int,int,int)
void merge_sort2(int* nums,int start,int end)
{if(end-start<2)  return;  //只有一个元素则退出递归int mid=(start+end)/2;merge_sort2(nums,start,mid);   //递归进入左半区间merge_sort2(nums,mid,end);     //递归进入右半区间sort_(nums,start,mid,end);     //归并当前的左右区间
}void sort_(int* nums,int start,int mid,int end) //头闭尾开
{cout<<"归并的区间为"<<start<<" "<<mid<<" "<<end<<endl;int l=start;int r=mid;int index=0;int* temp=new int[end-start];while(index<end-start){    if(l<mid&&(r==end||nums[l]<nums[r]))  //当左边小于右边或者右区间没有数据时{temp[index++]=nums[l++];   }  else temp[index++]=nums[r++];}  /*拷贝数据*/for(int i=0;i<end-start;i++){nums[i+start]=temp[i];       }delete[]temp;
}

可以看出它是不断的递归进入自己的左右区间,递归到左右只有一个元素然后再向上合并
 

两种方法的时间复杂度都为O(nlog⁡n)

这里的迭代法的空间复杂度为O(n),递归法空间复杂度为 O(nlog⁡n),你可以传一个临时数组以达到O(n)并且可以减少new和delete带来的开销

进阶版:实现对链表的归并排序

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com