二路归并排序 Implemented With C++

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二路归并排序 Implemented With C++，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1896字，纯文字阅读大概需要3分钟。

内容图文

Definition

对于一个长度为 $n$n 的表，我们可以把这张表看成是由 $n$n 个长度为 $1$1 的表组成的集合，然后我们对这些表两两合并——也就是所谓的归并，然后再对归并后得到的长度为原来的两倍（具体情况和 $n$n 是偶数还是奇数有关）的新表中的元素进行排序，这样，我们就得到了 $n/2$n/2 个长度为 $2$2 的表。重复上述过程，最终可以归并得到完整的长度为 $n$n 的有序表，这就是归并排序（merge sort），而一次归并排序的过程称为一趟归并排序。显然，对于 $n$n 的表来说，我们总共需要 $\log n$logn 趟，每趟排序的时间复杂度为 $O(n)$O(n)，所以我们可以得到归并排序的时间复杂度为：
$T(n)=O(n\log n)\tag{0}$T(n)=O(nlogn)(0)

Implementation

合并的算法可以考虑空间换取时间的方法：申请一个长度为两个待合并有序表长度之和的一个空表，采用合并有序表的算法，此时时间复杂度为 $O(max(m,n))$O(max(m,n))，其中 $m,n$m,n 为两个有序表的长度：

void merge(ElementType* seq, int low, int mid, int high){
	int* temp = new int[high - low + 1];
	// initialized ptr for the empty list and two lists going to be merged
	int k = 0, i = low, j = mid;
	for(;i < mid && j <= high;k++){
		if(seq[j] < seq[i]){
			temp[k] = seq[j];
			j++;
		}
		else{
			temp[k] = seq[i];
			i++;
		}
	}
	// move rest elements into temp if necessary.
	// only one of the loops below will process
	while(i < mid){
		temp[k++] = seq[i++];
	}
	while(j <= high){
		temp[k++] = seq[j++];
	}
	// copy back into original list
	for(i = low; i <= high;i++){
		seq[i] = temp[i];
	}
	return;
}

void mergeSort(ElementType* seq, int low, int high){
	if(high < low){
		int mid = (low + high) / 2;
		// sort sub part
		mergeSort(seq, low, mid);
		mergeSort(seq, mid + 1, high);
		// merge the two sorted parts
		merge(seq, low, mid, high);
	}
	return;
}

Performance

二路归并排序的性能：

• 时间复杂度：$O(n\log n)$O(nlogn)
• 空间复杂度：用到 $n$n 个单元的辅助空间，所以空间复杂度为 $O(n)$O(n)
• 稳定性：在合并过程中，我们判断条件采用的是当且仅当严格小于时将后面部分元素放置在前，因此当遇到值相同的情况时不会改变原有的相对次序，所以二路归并排序是一个稳定的算法

内容总结

以上是互联网集市为您收集整理的二路归并排序 Implemented With C++全部内容，希望文章能够帮你解决二路归并排序 Implemented With C++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---