文档章节

算法导论复习:第八章和第九章

fzyz_sb
 fzyz_sb
发布于 2014/01/04 16:23
字数 1188
阅读 160
收藏 5
点赞 0
评论 0

定理: 在最坏情况下,任何比较排序算法都需要做nlgn次比较.

1. 计数排序

基本原理:假设n个输入元素中的每一个都是在0到k区间内的一个整数,其中k为某个整数.当k=O(n)时,排序的运行时间为n.对于每一个输入元素x,确定小于x的元素个数.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define SIZE 100

void countingSort( int *A, int *B, int k, int len );

int main( void )
{
	int		A[ SIZE ];
	int		B[ SIZE ];
	int		k = 0;
	int		i = 0;
	memset( B, 0, sizeof( int ) * SIZE );
	k = SIZE - 5;
	srand( ( unsigned int )time( NULL ) );
	for ( i = 0; i < SIZE; i++ ){
		A[ i ] = rand() % k;
	}

	printf("the array is:\n");
	for ( i = 0; i < SIZE; i++ ){
		printf("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}

	countingSort( A, B, k, SIZE );

	printf("\nafter sort,the array is:\n");
	for ( i = 0; i < SIZE; i++ ){
		printf("%d ", B[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	printf("\n");

	return 0;
}

void countingSort( int *A, int *B, int k, int len )
{
	int		*C = ( int * )malloc( sizeof( int ) * k );
	int		i = 0;
	memset( C, 0, sizeof( int ) * k );

	for ( i = 0; i < len; i++ ){
		C[ A[ i ] ] += 1;
	}
	for ( i = 1; i < k; i++ ){
		C[ i ] += C[ i - 1 ];
	}
	for ( i = 0; i < k; i++ ){
		C[ i ] -= 1;		//下标从0开始,否则B会存在下标越界情况
	}

	for ( i = len - 1; i >= 0; i-- ){
		B[ C[ A[ i ] ] ] = A[ i ];
		C[ A[ i ] ] -= 1;
	}
	free( C );
}



程序输出:

备注:在算法的讨论中,一般下标是从1开始的,而实际的编码却是从0开始,所以要小心下标的越界情况.

2. 基数排序

我们用基数排序对以下英文单词进行排序:COW,DOG,SEA,RUG,ROW,MOB,BOX,TAB,BAR,EAR,TAR,DIG,BIG,TEA,NOW,FOX.

#include <stdio.h>

void radixSort( char *A[], int len, int keyLen );
int main( void )
{
	int		i = 0;
	char		*A[] = { "COW", "DOG", "SEA", "RUG", "ROW", "MOB", "BOX", "TAB", "BAR", "EAR", "TAR", "DIG", "BIG", "TEA", "NOW", "FOX" };
	int		len = sizeof( A ) / sizeof( *A );
	int		keyLen = 3;		//每个单词的长度,这里不考虑长度不同的情况,只是为了更好的说明基数排序
	radixSort( A, len, keyLen );

	for ( i = 0; i < len; i++ ){
		printf("%s ", A[ i ] );
		if ( 0 == ( i + 1 ) % 5 ){
			printf("\n");
		}
	}
	printf("\n");

	return 0;
}

void radixSort( char *A[], int len, int keyLen )
{
	int		i = 0;
	int		j = 0;
	int		k = 0;
	for ( i = keyLen - 1; i >= 0; i-- ){
		//插入排序
		for ( j = 1; j < len; j++ ){
			char		keyValue = A[ j ][ i ];
			char		*key = A[ j ];
			k = j - 1;
			while ( k >= 0 && A[ k ][ i ] > keyValue ){
				A[ k + 1 ] = A[ k ];
				k -= 1;
			}
			A[ k + 1 ] = key;
		}
	}
}



程序输出:

3. 桶排序

假设有100个数据,放在10个桶中,对每个桶进行排序,然后再合并10个桶.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <limits.h>

#define SIZE 100
#define LENBUCKET		10		

typedef struct NODE{
	int						data;
	struct NODE		*link;
}Node;

void bucketSort( int *A, int len );
void insertNode( Node *node, int value );

int main( void )
{
	int		A[ SIZE ];
	int		i = 0;
	srand( ( unsigned int )time( NULL ) );
	for ( i = 0; i < SIZE; i++ ){
		A[ i ] = rand() % SIZE;
	}

	printf("the array is:\n");
	for ( i = 0; i < SIZE; i++ ){
		printf("%3d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}

	bucketSort( A, SIZE );

	printf("after sort, the array is:\n");
	for ( i = 0; i < SIZE; i++ ){
		printf("%3d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	printf("\n");

	return 0;
}

void bucketSort( int *A, int len )
{
	Node		*B[ LENBUCKET ];
	int			i = 0;
	int			j = 0;
	for ( i = 0; i < LENBUCKET; i++ ){
		Node *node = ( Node * )malloc( sizeof( Node ) );
		node->link = NULL;
		node->data = INT_MIN;
		B[ i ] = node;
	}
	for ( i = 0; i < len; i++ ){
		int			index = A[ i ] / ( SIZE / LENBUCKET );
		insertNode( B[ index ], A[ i ] );
	}

	for ( i = 0, j = 0; j < LENBUCKET; j++ ){
		Node *node = ( Node * )malloc( sizeof( Node ) );
		node = B[ j ]->link;
		while ( NULL != node ){
			A[ i++ ] = node->data;
			node = node->link;
		}
	}
}

void insertNode( Node *node, int value )
{
	Node *tempNode = ( Node * )malloc( sizeof( Node ) );
	tempNode->data = value;
	tempNode->link = NULL;
	//为空结点
	if ( NULL == node->link ){
		node->link = tempNode;
	}
	else{
		//插入头部
		if ( value <= node->link->data ){
			tempNode->link = node->link;
			node->link = tempNode;
		}
		else{
			Node *prevNode = ( Node * )malloc( sizeof( Node ) );
			node = node->link;
			while ( NULL != node && value > node->data ){
				prevNode = node;
				node = node->link;
			}
			tempNode->link = node;
			prevNode->link = tempNode;
		}
	}
}



程序输出:

备注:1.一定要模块化,比如插入链表就应该封装成insertNode函数.

2. 对于链表的插入,初始化一个头节点专门用来标识这个链表是良好的设计方法,毕竟C语言只支持传值不支持传址(没有C++中引用).


4. 同时查找最小值和最大值

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE	100

void searchMinMax( int *A, int *minValue, int *maxValue, int len );

int main( void )
{
	int		A[ SIZE ];
	int		i = 0;
	int		minValue = 0;
	int		maxValue = 0;
	srand( ( unsigned int )time( NULL ) );
	for ( i = 0; i < SIZE; i++ ){
		A[ i ] = rand() % SIZE;
	}

	searchMinMax( A, &minValue, &maxValue, SIZE );

	printf("the array is:\n");
	for ( i = 0; i < SIZE; i++ ){
		printf("%3d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}

	printf("\nthe min value is: %3d\nthe max value is:%3d\n", minValue, maxValue );

	return 0;
}

void searchMinMax( int *A, int *minValue, int *maxValue, int len )
{
	int		i = 0;
	if ( 0 == len % 2 ){
		*minValue = A[ 0 ] < A[ 1 ] ? A[ 0 ] : A[ 1 ];
		*maxValue = A[ 0 ] > A[ 1 ] ? A[ 0 ] : A[ 1 ];
	}
	else{
		*minValue = *maxValue = A[ 0 ];
	}

	for ( i = 2; i < len; i += 2 ){
		if ( A[ i ] < A[ i + 1 ] ){
			if ( *minValue > A[ i ] ){
				*minValue = A[ i ];
			}
			if ( *maxValue < A[ i + 1 ] ){
				*maxValue = A[ i + 1 ];
			}
		}
		else{
			if ( *minValue > A[ i + 1 ] ){
				*minValue = A[ i + 1 ];
			}
			if ( *maxValue < A[ i ] ){
				*maxValue = A[ i ];
			}
		}
	}
}



程序输出:




© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 404
博文 209
码字总数 447144
作品 0
武汉
程序员
哪里可以找到 Kali Linux 的教程?

Kali Linux 秘籍 原书:Kali Linux Cookbook 译者:飞龙 在线阅读 PDF格式 EPUB格式 MOBI格式 Github Git@OSC 目录: 第一章 安装和启动Kali 第二章 定制 Kali Linux 第三章 高级测试环境 第...

wizardforcel0 ⋅ 2016/11/08 ⋅ 0

javascript入门经典【推荐】—新手必备、零基础学习

本书目录 第一章: JavaScript语言基础第二章: JavaScript内置对象 第三章: 窗口window对象 第四章: 文档document对象 第五章: 表单form对象 第六章: History与Navigator对象 第七章: ...

a125138 ⋅ 2012/08/01 ⋅ 0

MyBatis3.2.x从入门到精通系列

Java框架篇---Mybatis 入门 MyBatis3.2.x从入门到精通之第一章 MyBatis3.2.x从入门到精通之第二章 MyBatis3.2.x从入门到精通之第三章 MyBatis3.2.x从入门到精通之第四章 MyBatis3.2.x从入门到...

HenrySun ⋅ 2016/10/07 ⋅ 0

13篇文章,教你学会ES6知识点

ES6 深入理解ES6》学习笔记 本文用于汇总链接到各个子章节的内容,github 欢迎大家题issues和PR,如果对你有帮助,也可以给 star 支持 :) 目录 第一章 块级绑定 第二章 字符串和正则表达式 ...

你听___ ⋅ 05/08 ⋅ 0

【原创】《深入剖析Tomcat》读书笔记

第一章 一个简单的Web服务器 第二章 一个简单的servlet容器 第三章 连接器 第四章 Tomcat的默认连接器 第五章 servlet容器 第六章 生命周期 第七章 日志记录器 第八章 载入器 第九章 Sessio...

pandudu ⋅ 2015/12/22 ⋅ 0

零基础学习机器学习(Python语言、算法、Numpy库、MatplotLib)视频

机器学习作为人工智能的一部分,已经应用于很多领域,远超过人们的想象,垃圾邮件的过滤,在线广告的推荐系统,还有目前发展飞快的物体识别、人脸识别和语音识别的发展,都是机器学习的应用的...

qq_38472149 ⋅ 05/28 ⋅ 0

《掌控Windows SErver 2008 活动目录》 电子文档 下载 清华出版社

Windows Server 2008 视频突击系列 作者原发 《掌控Windows Server 2008活动目录》下载网址 http://down.51cto.com/400469 出版社文章 视频下载 ftp://ftp.hebeijd.com 第一章 搭建单域环境 ...

onesthan ⋅ 2010/02/09 ⋅ 0

《Knockout应用开发指南》系列技术文章整理收藏

《Knockout应用开发指南》系列技术文章整理收藏 Knockout是一个轻量级的UI类库,通过应用MVVM模式使JavaScript前端UI简单化,Knockout应用开发指南系列整理了Knockout方面的技术文章,供学习...

开元中国2015 ⋅ 2015/06/22 ⋅ 0

《Windows Server 2008 系统管理之道》 视频突击 电子文档 视频教程 下载

《Windows Server 2008 系统管理之道》 视频突击 清华出版社 系列 系统学习 彻底掌握Windows Server 2008 Windows Server Core 电子文档 下载网址 http://www.91xueit.com 视频教程下载网址 ...

onesthan ⋅ 2010/02/09 ⋅ 0

团队拙作《Python机器学习实战》

之前看国内外的 Python 机器学习的书,鲜有将机器学习到底怎么做人脸识别、怎么做风险控制、怎么做 OCR 算法模型列出的,并且真正的一个 Python 应用,不止是从机器学习库中导入一下配置一下...

yijun2018 ⋅ 04/20 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

Spring JDBC使用方法

普通实现: 1、创建数据表customer。 可以使用任何数据库实现,在项目中要引入相应数据库驱动包并配置相应数据库连接。 2、创建Customer pojo。 Customer类的属性对应数据库的属性,除了为每...

霍淇滨 ⋅ 今天 ⋅ 0

Contos 7 安装Jenkins

Jenkins是一款能提高效率的软件,它能帮你把软件开发过程形成工作流,典型的工作流包括以下几个步骤 开发 提交 编译 测试 发布 有了Jenkins的帮助,在这5步中,除了第1步,后续的4步都是自动...

欧虞山 ⋅ 今天 ⋅ 0

revel

revel install go get github.com/revel/revelgo get github.com/revel/cmd create new app revel new git.oschina.net/zdglf/myapp run app revel run git.oschina.net/zdglf/myapp ot......

zdglf ⋅ 今天 ⋅ 0

49. Group Anagrams - LeetCode

Question 49. Group Anagrams Solution 思路:维护一个map,key是输入数组中的字符串(根据字符排好序) Java实现: public List<List<String>> groupAnagrams(String[] strs) { Map<Strin......

yysue ⋅ 今天 ⋅ 0

spring Email

使用spring发Email其实就是使用spring自己封装携带的一个javamail.JavaMailSenderImpl类而已。这个类可以当一个普通的java对象来使用,也可以通过把它配置变成spring Bean的方式然后注入使用...

BobwithB ⋅ 今天 ⋅ 0

spark 整理的一些知识

Spark 知识点 请描述spark RDD原理与特征? RDD全称是resilient distributed dataset(具有弹性的分布式数据集)。一个RDD仅仅是一个分布式的元素集合。在Spark中,所有工作都表示为创建新的...

tuoleisi77 ⋅ 今天 ⋅ 0

思考

时间一天天过感觉自己有在成长吗?最怕的是时光匆匆而过,自己没有收获!下面总结下最近自己的思考。 认识自己 认识另一个自己,人们常说要虚心听取别人意见和建议。然而人往往是很难做到的,...

hello_hp ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部