文档章节

算法导论复习:第二章

fzyz_sb
 fzyz_sb
发布于 2014/01/01 17:02
字数 817
阅读 223
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

6. Python3源码—List对象

6.1. List对象 List对象是“变长对象”。 6.1.1. Python中的创建 Python中List对象最重要的创建方法为PyList_New,如下Python语句最终会调用到PyList_New: test = [1, 2, 3, 4, 5] 6.1.2. ...

Mr_zebra
10分钟前
1
0
nginx屏蔽指定接口(URL)

Step1:需求 web平台上线后,需要屏蔽某个服务接口,但又不想重新上线,可以采用nginx屏蔽指定平台接口的办法 Step2:具体操作 location /dist/views/landing/UNIQUE_BEACON_URL { re...

Linux_Anna
17分钟前
2
0
tomcat高并发配置调优

作者:Joker-pan 原文:https://blog.csdn.net/u011622226/article/details/72510385?utm_source=copy --------------------- tomcat 解压就使用的,配置都没动过,肯定不能支持高并发了; ...

imbiao
36分钟前
2
0
mysql 联结,级联查询总结区分

其实我对 数据库的级联或者联结查询一直都是会用,项目能查询出来自己想要的结果即可。 毕竟SQL使用复杂的查询毕竟比较少,而且不难使用。 至于区分他们,我还真的有点模糊。 在看 《SQL必知...

之渊
52分钟前
2
0
区块链入门教程分享区块链POW证明代码实现demo

兄弟连区块链入门教程分享区块链POW证明代码实现demo 这里强调一下区块链的协议分层 应用层 合约层 激励机制 共识层 网络层 数据层 上 一篇主要实现了区块链的 数据层,数据层主...

兄弟连区块链入门教程
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部