文档章节

算法导论复习:第二章

fzyz_sb
 fzyz_sb
发布于 2014/01/01 17:02
字数 817
阅读 221
收藏 11

1. 插入排序

#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 = j - 1;
		while ( i >= 0 && A[ i ] > key ){
			A[ i + 1 ] = A[ i ];
			i -= 1;
		}
		A[ i + 1 ] = key;
	}
}

int main( void )
{
	int			A[ 100 ];
	int			i = 0;
	srand( ( unsigned int )time( NULL ) );
	for ( i = 0; i < 100; i++ ){
		A[ i ] = rand() % 100;
	}
	printf("the array is:\n");
	for ( i = 0; i < 100; i++ ){
		printf("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	insert_sort( A, 100 );
	printf("\nafter sort, the array is:\n");
	for ( i = 0; i < 100; i++ ){
		printf("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	printf("\n");

	return 0;
}



程序输出:

2. 分治法排序

这里我换了一种思路,就是先用一个数组存储排序后的结果,然后在copy到原数组中去.

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

#define SIZE 100
void merge( int *A, int p, int q, int r );
void merge_sort( int *A, int p, int r );

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("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	merge_sort( 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");
		}
	}
	printf("\n");

	return 0;
}

void merge( int *A, int p, int q, int r )
{
	int		*B = ( int * )malloc( sizeof( int ) * ( r - p + 1 ) );
	int		start1 = p, end1 = q + 1;
	int		start2 = q + 1, end2 = r + 1;
	int		*startA = A + p;
	int		*startB = B;
	int		i = 0;
	while ( start1 < end1 && start2 < end2 ){
		if ( *( A + start1 ) <= *( A + start2 ) ){
			*B++ = *( A + start1 );
			start1++;
		}
		else{
			*B++ = *( A + start2 );
			start2++;
		}
	}
	while ( start1 < end1 ){
		*B++ = *( A + start1 );
		start1++;
	}
	while ( start2 < end2 ){
		*B++ = *( A + start2 );
		start2++;
	}
	for ( i = 0; i < r - p + 1; i++ ){
		*startA++ = *startB++;
	}
}

void merge_sort( int *A, int p, int r )
{
	if ( p < r ){
		int		q = ( p + r ) / 2;
		merge_sort( A, p, q );
		merge_sort( A, q + 1, r );
		merge( A, p, q, r );
	}
}



程序输出:

指针这东西很令人抓狂的,一出错很难找到原因.但是你也因此获得编程能力的提高.所以,刚开始,就去享受那种痛苦吧.

3. 冒泡排序

原理就是:把最小值放在最开头.

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

#define SIZE 100

void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void bubbleSort( int *A, int len )
{
	int i = 0;
	int j = 0;
	for ( i = 0; i < len; i++ ){
		for ( j = len - 1; j > i; j-- ){
			if ( *( A + j ) < *( A + j - 1 ) ){
				swap(  A + j, A + j - 1 );
			}
		}
	}
}

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("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	bubbleSort( A, SIZE );
	printf("\nafter sort, the array is:\n");
	for ( i = 0; i < SIZE; i++ ){
		printf("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	printf("\n");

	return 0;
}



程序输出:

4. 判断逆序对

这里简单的使用插入排序方法(如果时间复杂度想要为nlgn,则使用排序复杂度为nlgn的方法即可)

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

int insertSort( int *A, int len )
{
	int i = 0;
	int j = 0;
	int key;
	int count = 0;
	for ( j = 1; j < len; j++ ){
		key = A[ j ];
		i = j - 1;
		while ( i >= 0 && A[ i ] > key ){
			count++;
			A[ i + 1 ] = A[ i ];
			i -= 1;
		}
		A[ i + 1 ] = key;
	}

	return count;
}

int main( void )
{
	int A[ 5 ] = { 2, 3, 8, 6, 1 };
	int count = 0;
	count = insertSort( A, 5 );

	printf("%d\n", count );

	return 0;
}



程序输出:


© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 408
博文 209
码字总数 447144
作品 0
武汉
程序员
考研-专业课-c语言

为了我家娘子,猪猪臭 本人计划考研:报考学校北京工业大学--计算机 专业课编号985:教材为C语言程序设计案例教程和严蔚敏的数据结构那本 我知道 本书是没有答案的 下面的全都是 自己写的 并在...

20111564
2014/10/16
0
0
数据结构算法书籍推荐

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

modernizr
2014/05/22
28.1K
13
算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于恨,是因为它在进行算法分析的时候所体现的数学思想...

chambai
2015/09/11
0
0
支持向量机通俗导论 ——理解 SVM 的三层境界

AI 菌 今天要推荐的不是一本书,而是一篇关于向量机的超详细博文: http://blog.csdn.net/vjulyv/article/details/7624837 PDF版:链接:http://pan.baidu.com/s/1c9911O 密码:rzmq 目录 目...

x1kz18nkbqg
2017/11/16
0
0
《TCP/IP详解.卷1:协议》读书笔记

从大学的时候就听余老师介绍过stevens这三卷书,还听说最后一卷没写完作者就去世了,工作后也一直听人谈起, 但还是没去真正读它。最近因为工作上很多涉及到网络,捉包,各种tcpdump的使用,...

suit
2014/10/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

@SpringBootApplication 注解

@SpringBootApplication注解是一个组合注解,包含以下注解 @Target(ElementType.TYPE) 注解的作用目标 @Retention(RetentionPolicy.RUNTIME) Reteniton的作用是定义被它所注解的注解保留多久,...

java.刘
34分钟前
0
0
sentinel自定义DataSource实战

序 本文主要研究一下如何自定义sentinel的DataSource,这里以jdbc为例。 maven <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-sen......

go4it
50分钟前
1
0
xgboost/gbdt在调参时为什么树的深度很少就能达到很高的精度?

问题: 用xgboost/gbdt在在调参的时候把树的最大深度调成6就有很高的精度了。但是用DecisionTree/RandomForest的时候需要把树的深度调到15或更高。用RandomForest所需要的树的深度和Decisio...

tantexian
51分钟前
0
0
php-fpm的pool - 慢执行日志 - 进程管理 - open_basedir

php-fpm的pool : 为避免多站点使用同一个pool时因一个站点故障导致php资源耗尽,牵连使用同一个pool的其他站点的正常工作,可对每一个站点设置独立pool。 增加pool: 1.编辑php-fpm配置文件...

ZHENG-JY
今天
0
0
Linux之ssh服务默认端口修改

导读 SSH是标准的网络协议,可用于大多数UNIX操作系统,能够实现字符界面的远程登录管理,它默认使用22号端口,采用密文的形式在网络中传输数据,相对于通过明文传输的Telnet,具有更高的安全...

问题终结者
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部