文档章节

数据结构(C语言版)第七章:排序

fzyz_sb
 fzyz_sb
发布于 2013/12/07 21:56
字数 2685
阅读 62
收藏 0
点赞 0
评论 0

PS:对排序比较感兴趣,所以就先学习第七章排序,第六章图就先放着.

7.1 查找与表验证

1. 折半查找

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

int binsearch( int list[], int searchNum, int n );
int count = 0;
int main( void )
{
	int list[ 1000 ];
	int i = 0;
	for ( i = 0; i < 1000; i++ ){
		list[ i ] = i;
	}

	binsearch( list, 65, 1000 );

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

	return 0;
}

int binsearch( int list[], int searchNum, int n )
{
	int left = 0;
	int right = n - 1;
	int middle;
	while ( left <= right ){
		count++;
		middle = ( left + right ) / 2;
		if ( list[ middle ] == searchNum ){
			return middle;
		}
		else if ( list[ middle ] < searchNum ){
			left = middle + 1;
		}
		else{
			right = middle - 1;
		}
	}

	return -1;
}

输出为:10.说明查找了10次.复杂度为log(n),想象为一棵树就可以了,树的元素为n,深度为log(n).

2. 表验证

假设我们要验证一张表的元素是否都出现在第二张表中,且第一张表允许重复而乱序.那怎么办?

最低效的方法是:每个元素都依次验证即可,代码如下:

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

#define MAX_SIZE 100

void verify( int list1[], int list2[], int len1, int len2 );
int search( int list[], int len, int searchNum );

int main( void )
{
	int list1[] = { 1, 5, 2, 8, 3, 9, 4, 10, 7, 6 };
	int list2[] = { 10, 2, 10, 4, 9, 11 };
	int len1 = sizeof( list1 ) / sizeof( *list1 );
	int len2 = sizeof( list2 ) / sizeof( *list2 );

	verify( list1, list2, len1, len2 );

	return 0;
}

void verify( int list1[], int list2[], int len1, int len2 )
{
	int mark[ MAX_SIZE ];
	int i = 0;
	int isFind = 0;
	memset( mark, 0, sizeof( int ) * len2 );
	for ( i = 0; i < len2; i++ ){
		if ( !search( list1, len1, list2[ i ] ) ){
			mark[ i ] = 1;
		}
	}

	for ( i = 0; i < len2; i++ ){
		if ( mark[ i ] ){
			printf("%d ", list2[ i ] );
			isFind = 1;
		}
	}

	if ( isFind ){
		printf(" not in list1\n");
	}
	else{
		printf("list2 in list1\n");
	}
}

int search( int list[], int len, int searchNum )
{
	int i = 0;
	for ( i = 0; i < len; i++ ){
		if ( searchNum == list[ i ] ){
			return 1;
		}
	}

	return 0;
}



程序输出:


但是这种复杂度最高---len1 * len2.所以我们需要对其进行排序,并且删除重复项,然后进行查找(是否删除重复项,得看具体的数据.万一数据的重复项很多,则删除重复项可带来效率的提升):

书上的代码良好的诠释了排序后比较两张表的简单性:

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

#define MAX_SIZE 100

void verify( int list1[], int list2[], int len1, int len2 );
void sort( int list[], int len );
void swap( int *pa, int *pb );

int main( void )
{
	int list1[] = { 1, 5, 2, 8, 3, 9, 4, 10, 7, 6 };
	int list2[] = { 9, 3, 5, 1, 11, 14, 12, 2 };
	int len1 = sizeof( list1 ) / sizeof( *list1 );
	int len2 = sizeof( list2 ) / sizeof( *list2 );

	verify( list1, list2, len1, len2 );

	return 0;
}

void verify( int list1[], int list2[], int len1, int len2 )
{
	int i = 0;
	int j = 0;
	sort( list1, len1 );
	sort( list2, len2 );
	while ( i < len1 && j < len2 ){
		if ( list1[ i ] < list2[ j ] ){
			printf("%d is not in list 2\n", list1[ i ] );
			i++;
		}
		else if ( list1[ i ] == list2[ j ] ){
			i++;
			j++;
		}
		else{
			printf("%d is not in list 1 \n", list2[ j ] );
			j++;
		}
	}

	for ( ; i < len1; i++ ){
		printf("%d is not in list 2\n", list1[ i ] );
	}
	for ( ; j < len2; j++ ){
		printf("%d is not in list 1\n", list2[ j ] );
	}
}

/*
基础的冒泡排序法
*/
void sort( int list[], int len )
{
	int i = 0;
	int j = 0;
	for ( i = 0; i < len - 1; i++ ){
		for ( j = i + 1; j < len; j++ ){
			if ( list[ i ] > list[ j ] ){
				swap( &list[ i ], &list[ j ] );
			}
		}
	}
}

void swap( int *pa, int *pb )
{
	int temp = *pa;
	*pa = *pb;
	*pb = temp;
}



这里排序用了最简单的冒泡排序,只是为了更好的说明代码.整体来说,排序后,比较的效率提高了.程序输出:


7.3 插入排序

插入排序就像抓牌一样,我们把每张牌都放在合适的地方即可:

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

void insertSort( int list[], int len );
void show( int list[], int len );
int main( void )
{
	int list1[] = { 1, 5, 2, 8, 3, 9, 4, 10, 7, 6 };
	int len = sizeof( list1 ) / sizeof( *list1 );
	insertSort( list1, len );

	show( list1, len );

	return 0;
}

void insertSort( int list[], int len )
{
	int i = 0;
	int j = 0;
	int next = 0;
	for ( i = 1; i < len; i++ ){
		next = list[ i ];
		for ( j = i - 1; j >= 0 && next < list[ j ]; j-- ){
			list[ j+ 1 ] = list[ j ];
		}
		list[ j + 1 ] = next;
	}
}

void show( int list[], int len )
{
	int i = 0;
	for ( i = 0; i < len; i++ ){
		printf("%d ", list[ i ] );
	}
}



程序输出:

对于一般数据来说,复杂度为n^2,实际上和冒泡程序一样(冒泡排序比较好理解一些.)在小数据情况下,比如个数小于20的情况下,复杂度为n.(这里讲的复杂度为平均复杂度,而通常平均复杂度==最差复杂度).

7.4 快速排序

看过K&R C和The C++ programming language的人都知道,里面都引用了快速排序(我不确定K&R C是否引用了,但TCPPL引用了这个算法我印象深刻.).让我们来看看牛逼哄哄的快速排序(PS:叫我写,我写不出来):

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

void quicksort( int list[], int left, int right );
void show( int list[], int len );
void swap( int *pa, int *pb );
int main( void )
{
	int list1[] = { 26, 5, 37, 1, 61, 11, 59, 15, 48, 19 };
	int len = sizeof( list1 ) / sizeof( *list1 );
	quicksort( list1, 0, len - 1 );

	printf("\nthe sort list is:\n");
	show( list1, len );

	return 0;
}

void quicksort( int list[], int left, int right )
{
	int pivot;
	int i;
	int j;
	if ( left < right ){
		i = left;
		j = right + 1;
		pivot = list[ left ];
		do{
			do{
				i++;
			}while ( list[ i ] < pivot );
			do{
				j--;
			}while ( list[ j ] > pivot );
			if ( i < j ){
				swap( &list[ i ], &list[ j ] );
			}
		}while ( i < j );
		swap( &list[ left ], &list[ j ] );
		show( &list[ 0 ], 10 );
		quicksort( list, left, j - 1 );
		quicksort( list, j + 1, right );
	}
}

void show( int list[], int len )
{
	int i = 0;
	for ( i = 0; i < len; i++ ){
		printf("%d ", list[ i ] );
	}
	printf("\n");
}

void swap( int *pa, int *pb )
{
	int temp = *pa;
	*pa = *pb;
	*pb = temp;
}



程序输出:

让我们来分析一下这个诡异的快速排序.

我在快速排列里面增加了如下显示数组的代码,可以方便分析快速排序:

void quicksort( int list[], int left, int right )
{
	int pivot;
	int i;
	int j;
	if ( left < right ){
		i = left;
		j = right + 1;
		pivot = list[ left ];
		do{
			do{
				i++;
			}while ( list[ i ] < pivot );
			do{
				j--;
			}while ( list[ j ] > pivot );
			if ( i < j ){
				swap( &list[ i ], &list[ j ] );
			}
			show( &list[ 0 ], 10 );
		}while ( i < j );
		swap( &list[ left ], &list[ j ] );
		show( &list[ 0 ], 10 );
		quicksort( list, left, j - 1 );
		quicksort( list, j + 1, right );
	}
}



快速排序的基本思想是:把第一个元素26放在中间的位置,并且左边的数都小于它,而右边的数都大于它,然后进行递归.第一次的递归输出如下:

我们会发现26现在在中间了.而左边的数都小于它,右边的数都大于它.然后我们进行递归排序即可:

quicksort( list, left, j - 1 );
quicksort( list, j + 1, right );



我们来看看书上分析的时间复杂度:

具体分析也没看懂(这方面算法导论做的非常好,可以看那本书),复杂度为nlogn.算是很快了.

但是,对于小型的排序来说,插入排序可以达到n.所以,对于小型的排序,推荐使用插入排序,甚至冒泡排序都可以.如果是大型的数据,那就快速排序吧.

但是,迭代如何实现呢??

排序算法的最优的时间复杂度是nlogn.


7.6 归并排序

7.6.1 归并

假设我们要归并一个数组,数组是由两个排序好的子数组组成,那么怎么写?

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

int *merge( int list[], int start, int middle, int end )
{
	int *sorted = ( int * )malloc( sizeof( int ) * ( end - start + 1 ) );
	int *temp = sorted;
	int i = 0;
	int j = middle + 1;
	while ( i <= middle && j <= end ){
		if ( list[ i ] <= list[ j ] ){
			*sorted++ = list[ i++ ];
		}
		else{
			*sorted++ = list[ j++ ];
		}
	}
	while ( i <= middle ){
		*sorted++ = list[ i++ ];
	}
	while ( j <= end ){
		*sorted++ = list[ j++ ];
	}
	return temp;
}

int main( void )
{
	int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
	int *parr = NULL;
	int i = 0;
	parr = merge( arr, 0, 4, 9 );

	for ( i = 0; i < 10; i++ ){
		printf("%d ", parr[ i ] );
	}

	return 0;
}



程序正确的输出:

借这个程序说明以下几点:

1. 对于数组的操作,通常是需要新建一个临时的内存来存放操作好的数据的,这样不会陷入指针的危机中(因为数组本身就是指针,你通过操作地址可能会影响原本的值).

2. 数组指针是int *就可以了.这样更方便的操作.

3. 如果这道题改为改变list的话,那么将很难操作而且很容易出错.因为list的地址不能被改变,你除非一次次的赋值才可以.

7.6.2 归并排序的迭代算法

迭代算法的基本思想是:从小块排序到大:

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

#define MAX_SIZE 20
void merge( int list[], int sorted[], int i, int m, int n )
{
	int j, k, t;
	j = m + 1;
	k = i;
	while ( i <= m && j <= n ){
		if ( list[ i ] <= list[ j ] ){
			sorted[ k++ ] = list[ i++ ];
		}
		else{
			sorted[ k++ ] = list[ j++ ];
		}
	}
	if ( i > m ){
		for ( t = j; t <= n; t++ ){
			sorted[ k + t - j ] = list[ t ];
		}
	}
	else{
		for ( t = i; t <= m; t++ ){
			sorted[ k + t - i ] = list[ t ];
		}
	}
}

void merge_pass( int list[], int sorted[], int n, int length )
{
	int i, j;
	for ( i = 0; i <= n - 2 * length; i += 2 * length ){
		merge( list, sorted, i, i + length - 1, i + 2 * length - 1 );
	}
	if ( i + length < n ){
		merge( list, sorted, i, i + length - 1, n - 1 );
	}
	else{
		for ( j = i; j < n; j++ ){
			sorted[ j ] = list[ j ];
		}
	}
}

void merge_sort( int list[], int n )
{
	int length = 1;
	int extra[ MAX_SIZE ];

	while ( length < n ){
		merge_pass( list, extra, n, length );
		length *= 2;
		merge_pass( extra, list, n, length );
		length *= 2;
	}
}

int main( void )
{
	int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
	int i = 0;
	merge_sort( arr, 10 );

	for ( i = 0; i < 10; i++ ){
		printf("%d ", arr[ i ] );
	}
	printf("\n");

	return 0;
}

程序输出:

归并排序的简单分析:

在归并排序的迭代算法中,可以把输入序列看成是n个已排序序列,其中每个序列的长度为1.将这些序列两两归并,然后迭代即可.

因为我们最终排序的是list数组,所以我们需要把排序的extra重新merge_passlist数组:

void merge_sort( int list[], int n )
{
	int length = 1;
	int extra[ MAX_SIZE ];

	while ( length < n ){
		printf("\nOK-->\n");
		merge_pass( list, extra, n, length );
		printf("list: ");
		show( &list[ 0 ], 10 );
		printf("extra: ");
		show( &extra[ 0 ], 10 );
		length *= 2;
		merge_pass( extra, list, n, length );
		printf("list: ");
		show( &list[ 0 ], 10 );
		length *= 2;
	}
}



程序输出:

7.6.3 归并排序的递归算法

这个貌似有点难.我看不懂书上的算法,不知道为什么非要用链表.尝试自己写,但是又有问题.

不过还是写出来了.整体代码如下:

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

#define MAX_SIZE 20

void merge( int list[], int lower, int middle, int upper )
{
	int *sorted = ( int * )malloc( sizeof( int ) * ( upper - lower + 1 ) );
	int *start = sorted;
	int i = lower;
	int j = middle + 1;
	while ( i <= middle && j <= upper ){
		if ( list[ i ] < list[ j ] ){
			*sorted++ = list[ i++ ];
		}
		else{
			*sorted++ = list[ j++ ];
		}
	}
	while ( i <= middle ){
		*sorted++ = list[ i++ ];
	}
	while ( j <= upper ){
		*sorted++ = list[ j++ ];
	}
	for ( i = lower; i <= upper; i++ ){
		list[ i ] = *start++;
	}
}

void rmerge( int list[], int lower, int upper )
{
	int middle;
	if ( lower < upper ){
		middle = ( lower + upper ) / 2;
		rmerge( list, lower, middle );
		rmerge( list, middle + 1, upper );
		merge( list, lower, middle, upper );
	}
}

int main( void )
{
	int arr[] = { 12, 43, 2, 98, 14, 21, 66, 3, 111, 9 };
	int i = 0;
	rmerge( arr, 0, 9 );

	for ( i = 0; i < 10; i++ ){
		printf("%d ", arr[ i ] );
	}
	printf("\n");

	return 0;
}



程序输出:

首先,我们需要一个排序的算法,于是编写了:

void merge( int list[], int lower, int middle, int upper )



它将两个已序区间进行了合并(lower--middle, middle--upper).因为我们是递归的,所以可以保证从两个元素开始排序,即第一次是一个元素和另一个元素比较,然后不断的回溯上去即可.


关于剩下的堆排序和基数排序,直接略过,算法导论上有.得找段时间复习一下算法导论的前14章,真是一本好书.


© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 404
博文 209
码字总数 447144
作品 0
武汉
程序员
做游戏,学编程(C语言) 网易云课堂MOOC视频

应一些同学的要求,把这学期上C语言编程课的讲课视频录制剪辑,上传到网易云课堂,感兴趣的朋友可以在线观看,欢迎多提宝贵意见。 MOOC视频链接:http://study.163.com/course/introduction....

童晶 ⋅ 2017/11/07 ⋅ 0

酷壳陈皓:如何学好C语言

导读:本文作者陈皓在csdn上发表博客讲述《Java NIO类库Selector机制解析》。以下是他列举学习C语言的一些建议: 有人在酷壳的留言版上询问下面的问题 我相信,这可能是很多朋友的问题,我以前...

Yisen ⋅ 2011/03/30 ⋅ 1

如何学好C语言?

  C语言杂谈 如何学好C语言?为什么会有学的既不深,也不扎实,半吊子的感觉      我相信,这可能是很多朋友的问题,我以前也有这样的感觉,编程编到一定的时候,发现能力到了瓶颈,既...

编程大亨 ⋅ 2017/12/20 ⋅ 0

C语言书籍资料汇总

我汇总出自己收藏的C语言方面的书籍资料,方便后期使用,或许你也用的到。 以下内容,有链接的都可以下载。 一、书籍 元老级别的书籍: C程序设计语言.pdf (c语言之父) C Primer plus 第5...

BjarneCpp ⋅ 2017/11/06 ⋅ 0

微软面试、经典算法、编程艺术、红黑树4大系列总结

无私分享,造福天下 以下是本blog内的微软面试100题系列,经典算法研究系列,程序员编程艺术系列,红黑树系列4大经典原创系列作品与一些重要文章的集锦。 一、微软面试100题系列 横空出世,席...

长平狐 ⋅ 2013/01/06 ⋅ 0

Linux C编程如何使用联机帮助来解决编程问题?

1.背景 多次学习C语言一直无法踏入C语言的大门,每次都是在学习C语言中的那些系统调用库函数等望而却只,linux下的系统调用需要我们去记忆一些没有规律的结构体和一些大写的宏定义并且还有一...

Jeff_Linux ⋅ 2014/07/06 ⋅ 0

数据结构算法书籍推荐

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

modernizr ⋅ 2014/05/22 ⋅ 13

如何学好C语言

我相信,这可能是很多朋友的问题,我以前也有这样的感觉,编程编到一定的时候,发现能力到了瓶颈,既不深,也不扎实,半吊子。比如:你长期地使用Java和.NET ,这些有虚拟机的语言对于开发便...

邪恶的小Y ⋅ 2011/08/16 ⋅ 2

如何学好C语言

有人在酷壳的留言版上询问下面的问题 keepwalker : 今天晚上我看到这篇文章。 http://programmers.stackexchange.com/questions/62502/small-c-projects 我也遇到了和提问的老外一样的问题。...

nothingfinal ⋅ 2012/06/27 ⋅ 0

如何学好C语言?为什么会有学的既不深,也不扎实,半吊子的感觉

如何学好C语言?为什么会有学的既不深,也不扎实,半吊子的感觉 C/C++学习,解答,技术内容更多尽在:C/C++学习群:99816772 我相信,这可能是很多朋友的问题,我以前也有这样的感觉,编程编...

这个人很懒什么都没留下 ⋅ 2017/12/20 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

ARMS: 原来实时计算可以这么简单!

摘要: 业务实时监控服务( ARMS)是一款阿里云应用性能管理(APM)类监控产品。借助本产品,您可以基于前端、应用、业务自定义等服务,迅速便捷地为企业构建秒级响应的业务监控能力。 业务实...

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

Monkey入门_琉璃

先下载android sdk安装配置好路径,然后adb shell 如果给你显示这个,说明目前没有有效的移动设备链接,可以开个安卓模拟器或者使用真机,usb或wifi链接到电脑都可以,打开usb调试模式;然后...

EvanDev ⋅ 5分钟前 ⋅ 0

Idea类注释模板

一、设置类注释模板 1.选择File–>Settings–>Editor–>File and Code Templates–>Includes–>File Header. 2.设置完成后,创建类时自动生成注释,效果如下。...

Clarence_D ⋅ 7分钟前 ⋅ 0

vuejs题

1、active-class是哪个组件的属性?嵌套路由怎么定义? 答:vue-router模块的router-link组件。 2、怎么定义vue-router的动态路由?怎么获取传过来的动态参数? 答:在router目录下的index.j...

自由小鸟 ⋅ 7分钟前 ⋅ 0

2018年社交系统ThinkSNS年中大促

致各大商企事业单位及粉丝用户: 为感谢大家对ThinkSNS品牌的关注与支持,2018年6月18日官方诚推出:年中大促,限时抢购活动! “ThinkSNS 年中大促,¥6.18超值特惠 名额有限,预购从速! ...

ThinkSNS账号 ⋅ 13分钟前 ⋅ 0

MYSQL主从复制搭建及切换操作(GTID与传统)

如下: MYSQL主从复制方式有默认的复制方式异步复制,5.5版本之后半同步复制,5.6版本之后新增GTID复制,包括5.7版本的多源复制。 MYSQL版本:5.7.20 操作系统版本:linux 6.7 64bit 1、异步...

rootliu ⋅ 13分钟前 ⋅ 0

Java强软弱虚引用Reference

Java强软弱虚引用Reference 本文目的:深入理解Reference 本文定位:学习笔记 学习过程记录,加深理解,提升文字组合表达能力。也希望能给学习Reference的同学一些灵感 源码说明 源码基于jdk...

lichuangnk ⋅ 16分钟前 ⋅ 0

plsql 表中字段及注释时为乱码

在windows中创 建一个名为“NLS_LANG”的系统环境变量,设置其值为“SIMPLIFIED CHINESE_CHINA.ZHS16GBK”, 然后重新启动 pl/sql developer,这样检索出来的中文内容就不会是乱码了。如...

江戸川 ⋅ 19分钟前 ⋅ 0

Docker创建JIRA 7.2.7中文破解版

1、介绍 1.1、什么是JIRA?   关于JIRA网上的介绍有很多,以下摘自百度百科:   JIRA是Atlassian公司出品的项目与事务跟踪工具,被广泛应用于缺陷跟踪、客户服务、需求收集、流程审批、任...

谢思华 ⋅ 23分钟前 ⋅ 0

Java Class 类使用

Java Class 类使用 我们可以通过已知的包名来获取到 Class 对象,从而可以通过反射动态的来操作对象。 获取Class有三种方式 //通过对象.class直接获取Class integerClass = Integer.class;...

gaob2001 ⋅ 27分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部