文档章节

C++STL之归并排序

Lambda8421
 Lambda8421
发布于 2015/01/15 18:29
字数 332
阅读 248
收藏 0
/******************************
*mergeSort
******************************/
#include "stdafx.h"
#include <vector>
using namespace std;

template <typename T>
void mergeSort(vector<T>& vec)
{
	vector<T> tempVec(vec.size());
	mergeSort(vec, tempVec, 0, vec.size()- 1);
}

template <typename T>
void mergeSort(vector<T>& vec, vector<T> tempVec, int left, int right)
{
	if (left < right)
	{
		int center = (left + right)/2;
		mergeSort(vec, tempVec, left, center);
		mergeSort(vec, tempVec, center+1, right);
		mergeFunc(vec, tempVec, left, center+1 , right);  //合并
	}
};

//合并函数
template <typename T>
void mergeFunc(vector<T>& vec, vector<T> tempVec, int left, int  Pos,int right)
{
	int leftPos		= left;          //左边序列的位置,初始为左序列起点
	int leftEnd		= Pos-1 ;    //左边序列的终点   
	int rightPos	= Pos;           //右边序列的位置,初始为右序列起点
	int rightEnd	= right;	//右边序列的终点
	int tempPos		= left;         //临时数组的位置,初始为临时数组的起点
	int numElements = right - left + 1;          //数组元素的个数

	//两段数组合并
	//两段数组已有序
	while (leftPos <= leftEnd && rightPos <= rightEnd) //左边数组和右边数组都没有到终点
	{
		//比较左边数组和右边数组值的大小
		//把较小者放入临时数组
		if (vec[leftPos] <= vec[rightPos])           
		{
			tempVec[tempPos++] = vec[leftPos++];
		}
		else
			tempVec[tempPos++] = vec[rightPos++];
	}

	// 只剩一个序列时,直接复制到临时数组
	while (leftPos <= leftEnd)
	{
		tempVec[tempPos++] = vec[leftPos++];
	}
	while (rightPos <= rightEnd)
	{
		tempVec[tempPos++] = vec[rightPos++];
	}

	//将临时数组的值复制回源数组
	int i = 0;
	for (; i< numElements; i++, rightEnd--)  //这里从后向前复制,因为前面有很多垃圾数据
	{
		vec[rightEnd] = tempVec[rightEnd];
	}
}


© 著作权归作者所有

Lambda8421
粉丝 10
博文 121
码字总数 121640
作品 0
闸北
程序员
私信 提问
数据结构基础(1) --Swap & Bubble-Sort & Select-Sort

Swap的简单实现 //C语言方式(by-pointer):template bool swapByPointer(Type pointer1, Type pointer2){ } //C++特有方式(by-reference):template void swapByReference(Type &value1, Type......

翡青
2015/01/01
0
0
C++stl难点是什么?

听说C++STL很难,我学了大概一个月感觉不难。而且我基础很差,是不会到后期很难呢?为什么说STL难呢?

个性签名
2015/02/04
165
6
c语言有没有类似于c++stl的库?

想问一下有c语言开发经验的大虾,c语言有没有类似于c++stl的库?如果没有的话,是不是都要自己去实现。一般的商业开发是采用什么解决方案。

nerds
2012/05/03
6.8K
19
关于Windows下的Clang的编译环境设置

在Windows下配置LLVM-GCC编译链,可以编译C程序,也可以编译C++程序,但是无法解析C++ STL没有后缀名的头文件,怎么解决?

Force武装卫队
2012/04/04
12K
13
java泛型中使用的排序算法——归并排序及分析

一、引言 我们知道,java中泛型排序使用归并排序或TimSort。归并排序以O(NlogN)最坏时间运行,下面我们分析归并排序过程及分析证明时间复杂度;也会简述为什么java选择归并排序作为泛型的排序...

9龙
04/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

同名依赖,多次引入导致的程序错误

表现: 本地测试正常,打包上线后报错找不到某个方法(缺少依赖),检测依赖发现,同名依赖有两个版本。 解决:删除一个,程序正常

避难所
27分钟前
3
0
在HTML中的下拉框中实现超连接

<!DOCTYPE html><html lang="zh-CN"><head> <meta charset="UTF-8"> <link rel="canonical" href="https://blog.csdn.net/weixin_34228617/article/details/86130280"/> ......

mickelfeng
32分钟前
3
0
Content7关闭防火墙命令

在外部访问CentOS中部署应用时,需要关闭防火墙。 关闭防火墙命令:systemctl stop firewalld.service 开启防火墙:systemctl start firewalld.service 关闭开机自启动:systemctl disable f...

无名氏的程序员
33分钟前
3
0
分布式存储原理:TiDB

浮躁的码农
46分钟前
7
0
CSS实现圆角边框的完美解决方案

css实现图片圆角,兼容所有浏览器: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 <style type= "text/css" > /*通用样式--容器宽度值*/ .s......

前端老手
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部