文档章节

几种常见算法

 悠米海
发布于 2015/03/01 16:46
字数 810
阅读 221
收藏 20
点赞 0
评论 0

#include <iostream>
using namespace std;

void paopao_sort(int arr[], int nSize)
{
	for(int i=0;i<nSize;i++)
	{
		for(int j=0;j<nSize-1-i;j++)
		{
			if(arr[j] > arr[j+1])
			{
				int nTmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = nTmp;
			}
		}
	}
}

void select_sort(int arr[], int nSize)
{
	for(int i=0;i<nSize;i++)
	{
		for(int j=i;j<nSize;j++)
		{
			if(arr[i] > arr[j])
			{
				int nTmp = arr[i];
				arr[i] = arr[j];
				arr[j] = nTmp;
			}
		}
	}
}

void insert_sort(int arr[], int nSize)
{
	for(int i=0;i< nSize;i++)
	{
		int nTmp = arr[i];
		int j = i;
		for(;j>0 && arr[j-1] > nTmp;j--)
		{
			arr[j] = arr[j-1];
		}
		arr[j] = nTmp;
	}
}

void quick_sort(int arr[], int low,int high)
{
	if(low >= high)
		return;
	int first = low,last = high;
	int key = arr[first];
	while(first < last){
		while(first < last && arr[last] >= key){
			--last;
		}
		arr[first] = arr[last];
		while(first < last && arr[first] <= key){
			++first;
		}
		arr[last] = arr[first];
	}
	arr[first] = key;
	quick_sort(arr, low, first -1);
	quick_sort(arr, first+1, high);
}

void merge(int sour[], int tmp[], int st, int md, int ed)
{
	if(st >= ed)
		return;
	int i=st,j=md+1,k=st;
	while(i!=md+1 && j!=ed+1){
		if(sour[i] > sour[j]){
			tmp[k++] = sour[j++];
		}else{
			tmp[k++] = sour[i++];
		}
	}
	while(i!=md+1){
		tmp[k++] = sour[i++];
	}
	while(j!=ed+1){
		tmp[k++] = sour[j++];
	}
	for(i=st;i<=ed;i++){
		sour[i] = tmp[i];
	}
}

void merge_sort(int sour[],int tmp[],int st, int ed){
	if(st >= ed)
		return;
	int md = (st + ed)/2;
	merge_sort(sour,tmp,st,md);
	merge_sort(sour,tmp,md+1,ed);
	merge(sour,tmp,st,md,ed);
}

void heapAdjust(int arr[],int i,int nLen){
	int nChild, nTmp;
	for(;i*2+1 < nLen;i = nChild){
		nChild = i*2+1;
		if(nChild < nLen - 1 && arr[nChild] < arr[nChild +1]){
			nChild ++;
		}
		if(arr[nChild] > arr[i]){
			nTmp = arr[nChild];
			arr[nChild] = arr[i];
			arr[i] = nTmp;
		}else{
			break;
		}
	}
}

void heap_sort(int arr[], int nLen)
{
	for(int i=nLen/2-1;i>=0;i--){
		heapAdjust(arr,i,nLen);
	}
	int nTmp = 0;
	for(int i=nLen-1;i>0;i--)
	{
		nTmp = arr[i];
		arr[i] = arr[0];
		arr[0] = nTmp;
		heapAdjust(arr,0,i);
	}
}

void heapAdjustS(int arr[], int i, int nLen)
{
	int nChild, nTmp;
	for(;i*2+1 < nLen;i = nChild){
		nChild = i*2+1;
		if(nChild < nLen -1 && arr[nChild] > arr[nChild+1] ){
			nChild ++;
		}
		if(arr[i] > arr[nChild]){
			nTmp = arr[nChild];
			arr[nChild] = arr[i];
			arr[i] = nTmp;
		}else{
			break;
		}
	}
}

void heaps_sort(int arr[], int nLen)
{
	for(int i=nLen/2-1;i>=0;i--){
		heapAdjustS(arr,i,nLen);
	}
	int temp;
	for(int i=nLen-1;i>0;i--)
	{
		temp=arr[i];
		arr[i]=arr[0];
		arr[0]=temp;
		heapAdjustS(arr,0,i);
	}
}

struct tree{
	int		node;
	tree*	left;
	tree*	right;
};

tree* treeAdjust(tree*& root, int key)
{
	if(root == NULL){
		root = new tree;
		root->node = key;
		root->left = root->right = NULL;
		return root;
	}
	if(root->node == key){
		return root;
	}else if(root->node > key){
		return treeAdjust(root->left, key);
	}else{
		return treeAdjust(root->right, key);
	}
}

void treeDel(tree* root, int arr[], int& index)
{
	if(root == NULL)
		return;
	if(root->left != NULL){
		treeDel(root->left, arr, index);
	}
	arr[index++] = root->node;
	if(root->right != NULL){
		treeDel(root->right, arr, index);
	}
	delete root;
}

void tree_sort(int arr[], int nLen)
{
	tree* root = NULL;
	for(int i=0;i<nLen;i++)
	{
		treeAdjust(root,arr[i]);
	}
	int nIndex = 0;
	treeDel(root, arr, nIndex);
}


void arrCopy(int base[], int to[], int nLen)
{
	for(int i=0;i<nLen;i++)
		to[i] = base[i];
}

void arrShow(int arr[], int nLen)
{
	for(int i=0;i<nLen;i++)
		cout<<arr[i]<<",";
	cout<<endl;
}

int main()
{
	int base[] = {3,6,4,1,2,5,8,7,10,9};
	int nLen = sizeof(base)/sizeof(int);
	int* ptr = new int[nLen];

	cout<<"原始数组:"<<endl;
	arrShow(base, nLen);

	cout<<"冒泡:"<<endl;
	arrCopy(base, ptr, nLen);
	paopao_sort(ptr, nLen);
	arrShow(ptr, nLen);

	cout<<"选择:"<<endl;
	arrCopy(base, ptr, nLen);
	select_sort(ptr, nLen);
	arrShow(ptr, nLen);

	cout<<"插入:"<<endl;
	arrCopy(base, ptr, nLen);
	insert_sort(ptr, nLen);
	arrShow(ptr, nLen);

	cout<<"快速:"<<endl;
	arrCopy(base, ptr, nLen);
	quick_sort(ptr, 0, nLen-1);
	arrShow(ptr, nLen);

	cout<<"归并:"<<endl;
	arrCopy(base, ptr, nLen);
	int* pTmp = new int[nLen];
	merge_sort(ptr, pTmp, 0, nLen-1);
	arrShow(ptr, nLen);
	delete[] pTmp;

	cout<<"最大堆:"<<endl;
	arrCopy(base, ptr, nLen);
	heap_sort(ptr, nLen);
	arrShow(ptr, nLen);

	cout<<"最小堆:"<<endl;
	arrCopy(base, ptr, nLen);
	heaps_sort(ptr, nLen);
	arrShow(ptr, nLen);

	cout<<"二叉树:"<<endl;
	arrCopy(base, ptr, nLen);
	tree_sort(ptr, nLen);
	arrShow(ptr, nLen);

	delete[] ptr;
	return 0;
}



运行结果:



© 著作权归作者所有

共有 人打赏支持
粉丝 12
博文 92
码字总数 37069
作品 0
浦东
程序员
JVM有几种常见GC算法?常见的调节参数有哪些?

JVM有几种常见GC算法?常见的调节参数有哪些? JVM调优或者trouble shoot的基本方法有哪些?

文心雕码 ⋅ 2014/02/14 ⋅ 1

路过的大神进来帮忙解答一下这几个笔试题,能说几个说几个

2、nsobjective和uiview的默认构造方法 3、block的工作原理,从内存来看可分哪几种 4、输入网址按下回车 5、消息队列 6、函数模板与模板函数 7、stdcall和cdecl 8、static的作用 9、常见内存...

SuAdrenine ⋅ 2015/10/14 ⋅ 1

浙大的游戏设计教程

第一部分 游戏程序设计概览 计算机游戏简介:什么是游戏、游戏的分类等 游戏的基本开发流程? 游戏开发的基本理念及方法 游戏软件的体系结构:包括三维游戏引擎的架构分析 游戏的调试与测试 ...

Matrix4X4 ⋅ 2012/08/19 ⋅ 2

百度海量日志处理——任务调度实践与优化

作者简介 运小军 百度高级研发工程师 负责百度运维部大规模日志处理、海量事件数据存储相关设计研发工作,在分布式系统架构、大数据存储计算、高性能网络服务和即时通讯服务有广泛实践经验。...

g2v13ah ⋅ 2017/11/02 ⋅ 0

Python中time模块和datetime模块的常用操作以及几种常用时间格式间的转换

最常见以及常用的几种时间格式 1、时间戳(timestamp),时间戳表示的是从1970年1月1日00:00:00开始按秒计算的偏移量。 2、时间元组(struct_time),共有九个元素组。 3、格式化时间(format tim...

OMCloud ⋅ 2017/07/14 ⋅ 0

PHP常见排序算法学习

题记: 常见的排序算法有:冒泡排序法,快速排序法,选择排序法,插入排序法,此处作为自己最近面试准备进行的学习笔记,同时也希望能帮到你。 需求:将一个有多个数字的数组进行从小到大的排...

moTzxx ⋅ 2017/10/27 ⋅ 0

数据结构(python)

数据结构学会更有思路,效率,节约开销 算法实现的语言并不重要,重要的是思想,算法是独立存在的一种解决问题的方法和思想 算法的五大特性 输入: 算法具有0个或多个输入 输出: 算法至少有1...

sinat_23880167 ⋅ 2017/10/31 ⋅ 0

不使用synchronized和lock,如何实现一个线程安全的单例?(二)

如果不那么吹毛求疵的话,可以使用枚举、静态内部类以及饿汉模式来实现单例模式。见:不使用synchronized和lock,如何实现一个线程安全的单例? 但是,上面这几种方法其实底层也都用到了,那...

⋅ 2017/09/12 ⋅ 0

PHP常见排序算法整理学习

题记: 常见的排序算法有:冒泡排序法,快速排序法,选择排序法,插入排序法,此处作为自己最近面试准备进行的学习笔记,同时也希望能帮到你。 需求:将一个有多个数字的数组进行从小到大的排...

u011415782 ⋅ 2017/10/24 ⋅ 0

Java开发岗位面试题归类汇总

一、Java基础 String类为什么是final的 HashMap的源码,实现原理,底层结构。 说说你知道的几个Java集合类:list、set、queue、map实现类。 描述一下ArrayList和LinkedList各自实现和区别 Ja...

天天顺利 ⋅ 2016/03/11 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Mahout推荐算法之SlopOne

一、 算法原理 有别于基于用户的协同过滤和基于item的协同过滤,SlopeOne采用简单的线性模型估计用户对item的评分。如下图,估计UserB对ItemJ的偏好 图(1) 在真实情况下,该方法有如下几个...

xiaomin0322 ⋅ 6分钟前 ⋅ 0

LVM讲解

LVM是什么 LVM是 Logical Volume Manager(逻辑卷管理)的简写,它是Linux环境下对磁盘分区进行管理的一种机制,Linux用户安装Linux操作系统时遇到的一个常见的难以决定的问题就是如何正确地...

李超小牛子 ⋅ 16分钟前 ⋅ 0

mysql更改密码、连接mysql、mysql常用命令

1. 更改mysql的root账户密码: mysql中root账户和系统root不是一个账户 1.1 更改环境变量PATH,增加mysql绝对路径 由于mysql安装目录为/usr/local/mysql/,所以系统不能直接使用mysql,需把/...

laoba ⋅ 17分钟前 ⋅ 0

阿里云发布企业数字化及上云外包平台服务:阿里云众包平台

摘要: 阿里云正式发布旗下众包平台业务(网址:https://zhongbao.aliyun.com/),支持包括:网站定制开发,APP、电商系统等软件开发,商标、商品LOGO、VI、产品包装设计、营销推广、大数据人...

猫耳m ⋅ 17分钟前 ⋅ 0

阿里云发布企业数字化及上云外包平台服务:阿里云众包平台

摘要: 阿里云正式发布旗下众包平台业务(网址:https://zhongbao.aliyun.com/),支持包括:网站定制开发,APP、电商系统等软件开发,商标、商品LOGO、VI、产品包装设计、营销推广、大数据人...

阿里云云栖社区 ⋅ 20分钟前 ⋅ 0

1.03-Maven中使用ueditor富文本编辑器

起因:在maven仓库未找到百度的ueditor的jar包 操作: 1.下载百度的ueditor的jar包 2.打开命令行,切换到ueditor的下载位置,运行一下命令: mvn install:install-file -Dfile=ueditor-1.1....

静以修身2025 ⋅ 26分钟前 ⋅ 0

几道Spring 面试题

1、BeanFactory 接口和 ApplicationContext 接口有什么区别? ApplicationContext 接口继承BeanFactory接口 Spring核心工厂是BeanFactory BeanFactory采取延迟加载,第一次getBean时才会初始...

职业搬砖20年 ⋅ 35分钟前 ⋅ 0

包饺子

http://storage.slide.news.sina.com.cn/slidenews/77_ori/2018_24/74766_826131_625489.gif

霜叶情 ⋅ 37分钟前 ⋅ 0

xml解析

方法一: String s_xml1 = "<xml>" + "<head>lalalalal</head>" + "<body>1234</body>" + "</xml>"; try { DocumentBuilderFactory documentBuilderFactory......

GithubXD ⋅ 49分钟前 ⋅ 0

reuse stream

Although Java streams were designed to be operated only once, programmers still ask how to reuse a stream. From a simple web search, we can find many posts with this same issue ......

idoz ⋅ 49分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部