您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

归并排序!

归并排序的思想:

“归并”的含义是将两个或两个以上的有序子表组合成一个新的有序表。假定待排序表含有n个记录,则可将其视为n个有序的子表,每个子表的长度为1,然后两两归并,得到 ⌈n/2⌉个长度为2或1的有序表;继续两两归并,直到合并成一个长度为n的有序表为止,这种排序称为2路归并排序。

C++实现:

//归并方法
vector<int> vec;//辅助数组
void Merge(vector<int>& A,int low,int mid,int high){
	for(int k = low;k<=high;k++)
		vec[k] = A[k];//A中所有元素复制到辅助数组
	for(i = low,j = mid+1,k = i;i <= mid&&j <= high;k++){
		if(vec[i] <= vec[j])//比较辅助数组中左右两段中的元素,较小的复制到A中
			A[k] = vec[i++];
		else
			A[k] = vec[j++];
	}
	while(i <= mid) A[k++] = vec[i++];//哪个表没检测完,将剩余元素复制回去
	while(j <= high) A[k++] = vec[j++];
}	
//递归实现归并
void MergeSort(vector<int>& A,int low,int high){
	if(low<high){
		int mid = (low + high)/2;
		MergeSort(A,low,mid);
		MergeSort(A,mid+1,high);
		Merge(A,low,mid,high);
	}
}

时空复杂度及稳定性:

空间效率:Merge方法中,辅助空间为n个单元,所以空间复杂度为O(n)

时间效率:每趟归并的时间复杂度为O(n),共需进行 ⌈ l o g 2 n log_2n log2n⌉躺归并,所以算法的平均复杂度为O(n l o g 2 n log_2n log2n)。

稳定性:由于Merge方法操作不会改变相同元素的位置,所以2路归并排序是稳定排序。


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进