文档章节

算法导论复习:第七章

fzyz_sb
 fzyz_sb
发布于 2014/01/02 20:23
字数 216
阅读 43
收藏 0
点赞 0
评论 0

1. 快速排序

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

#define SIZE 100

void	quicksort( int *A, int p, int r );
int		partition( int *A, int p, int r );
void	swap( int *px, int *py );

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

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

	quicksort( A, 0, SIZE - 1 );

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

	return 0;
}

void quicksort( int *A, int p, int r )
{
	if ( p < r ){
		int		q = partition( A, p, r );
		quicksort( A, p, q - 1 );
		quicksort( A, q + 1, r );
	}
}

int partition( int *A, int p, int r )
{
	int		x = A[ r ];
	int		i = p - 1;
	int		j = p;
	for ( ; j <= r - 1; j++ ){
		if ( A[ j ] <= x ){
			i += 1;
			swap( &A[ i ], &A[ j ] );
		}
	}
	swap( &A[ i + 1 ], &A[ r ] );

	return i + 1;
}

void	swap( int *px, int *py )
{
	int temp = *px; 
	*px = *py;
	*py = temp;
}



程序输出:



© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 404
博文 209
码字总数 447144
作品 0
武汉
程序员
算法导论复习:第十二章

二叉搜索树的实现: 备注:算法导论中文版第168页中删除节点时候,y=TREEMINIMUM(z.right)是错误的,应该寻找后继结点,为y=TREESUCCESSOR(z.right). #include <stdio.h> include <stdlib.h> inc......

fzyz_sb ⋅ 2014/01/05 ⋅ 0

数据结构算法书籍推荐

学计算机的人是幸福的,因为在这个领域中有如此多的通俗易懂(相对来说)的经典好书,你需要做的只是坚持把它们一本一本读下去而已。在这里列出一些我看过或者准备看的算法书籍,以供参考。 ...

modernizr ⋅ 2014/05/22 ⋅ 13

ACM算法书籍推荐zz

我常感叹到,学计算机的人是幸福的,因为在这个领域中有如此多的通俗易懂(相对来说)的经典好书,你需要做的只是坚持把它们一本一本读下去而已。学力学就没有这样的好事了(抱怨一下),除了...

heartfly ⋅ 2010/10/03 ⋅ 1

算法导论复习:第十三章

红黑树的性质 树中每个节点包含5个属性:color,key,left,right和p.如果一个节点没有子节点或父节点,则该节点相应指针属性的值为NIL. 一棵红黑树是满足下面红黑性质的二叉搜索树: 1). 每个节点...

fzyz_sb ⋅ 2014/01/05 ⋅ 0

算法导论复习:第十章

栈的实现 #include <stdio.h> include <stdlib.h> include <limits.h> define SIZE 100 int stack[ SIZE ];int top = 0;int stackEmpty( int *S );int stackFull( int *S );void push( int *......

fzyz_sb ⋅ 2014/01/04 ⋅ 0

算法导论复习:第二章

插入排序 #include <stdio.h> include <stdlib.h> include <time.h> void insert_sort( int *A, int len ){int i = 0;int j = 0;int key = 0;for ( j = 1; j < len; j++ ){key = A[ j ];i = ......

fzyz_sb ⋅ 2014/01/01 ⋅ 0

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

定理: 在最坏情况下,任何比较排序算法都需要做nlgn次比较. 1. 计数排序 基本原理:假设n个输入元素中的每一个都是在0到k区间内的一个整数,其中k为某个整数.当k=O(n)时,排序的运行时间为n.对于...

fzyz_sb ⋅ 2014/01/04 ⋅ 0

数据结构(C语言版)第五章:树

5.2 二叉树 我们写一个二叉树,它支持树的插入,删除,查询和遍历,而且左子树的数据都小于右子树的数据(PS:树实际上很难的,想深入了解的话,可以去看看<算法导论>,什么红黑树啊,B树啊什么的,反正...

fzyz_sb ⋅ 2013/12/07 ⋅ 2

acm核心教材

Introduction to Algorithms:算法导论(4个版本) - Thomas H. Cormen,Charles E. Leiserson 本书是MIT计算机专业的经典算法教材,内容全面,语言通俗,很适合入门者学习 Introductory combina...

齐勇cn ⋅ 2015/04/02 ⋅ 1

ZOJ 3499. Median

    地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4322     题意:寻找中位数。对于一个(浮点数)数组,如果含有奇数个元素,“中位数”就是排序后位于数组中...

hoodlum1980 ⋅ 2012/06/13 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从零开始搭建Risc-v Rocket环境---(1)

为了搭建Rocke环境,我买了一个2T的移动硬盘,安装的ubuntu-16.04 LTS版。没有java8,gcc是5.4.0 joe@joe-Inspiron-7460:~$ java -version程序 'java' 已包含在下列软件包中: * default-...

whoisliang ⋅ 28分钟前 ⋅ 0

大数据学习路线(自己制定的,从零开始学习大数据)

大数据已经火了很久了,一直想了解它学习它结果没时间,过年后终于有时间了,了解了一些资料,结合我自己的情况,初步整理了一个学习路线,有问题的希望大神指点。 学习路线 Linux(shell,高并...

董黎明 ⋅ 34分钟前 ⋅ 0

systemd编写服务

一、开机启动 对于那些支持 Systemd 的软件,安装的时候,会自动在/usr/lib/systemd/system目录添加一个配置文件。 如果你想让该软件开机启动,就执行下面的命令(以httpd.service为例)。 ...

勇敢的飞石 ⋅ 36分钟前 ⋅ 0

mysql 基本sql

CREATE TABLE `BBB_build_info` ( `community_id` varchar(50) NOT NULL COMMENT '小区ID', `layer` int(11) NOT NULL COMMENT '地址层数', `id` int(11) NOT NULL COMMENT '地址id', `full_......

zaolonglei ⋅ 45分钟前 ⋅ 0

安装chrome的vue插件

参看文档:https://www.cnblogs.com/yulingjia/p/7904138.html

xiaoge2016 ⋅ 48分钟前 ⋅ 0

用SQL命令查看Mysql数据库大小

要想知道每个数据库的大小的话,步骤如下: 1、进入information_schema 数据库(存放了其他的数据库的信息) use information_schema; 2、查询所有数据的大小: select concat(round(sum(da...

源哥L ⋅ 今天 ⋅ 0

两个小实验简单介绍@Scope("prototype")

实验一 首先有如下代码(其中@RestController的作用相当于@Controller+@Responsebody,可忽略) @RestController//@Scope("prototype")public class TestController { @RequestMap...

kalnkaya ⋅ 今天 ⋅ 0

php-fpm的pool&php-fpm慢执行日志&open_basedir&php-fpm进程管理

12.21 php-fpm的pool pool是PHP-fpm的资源池,如果多个站点共用一个pool,则可能造成资源池中的资源耗尽,最终访问网站时出现502。 为了解决上述问题,我们可以配置多个pool,不同的站点使用...

影夜Linux ⋅ 今天 ⋅ 0

微服务 WildFly Swarm 管理

Expose Application Metrics and Information 要公开关于我们的微服务的有用信息,我们需要做的就是将监视器模块添加到我们的pom.xml中: 这将使在管理和监视功能得到实现。从监控角度来看,...

woshixin ⋅ 今天 ⋅ 0

java连接 mongo伪集群部署遇到的坑

部署mongo伪集群 #创建mongo数据存放文件地址mkdir -p /usr/local/config1/datamkdir -p /usr/local/config2/data mkdir -p /usr/local/config3/data mkdir -p /usr/local/config1/l......

努力爬坑人 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部