文档章节

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

fzyz_sb
 fzyz_sb
发布于 2013/12/07 21:56
字数 2685
阅读 62
收藏 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
粉丝 408
博文 209
码字总数 447144
作品 0
武汉
程序员
做游戏,学编程(C语言) 网易云课堂MOOC视频

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

童晶
2017/11/07
0
0
C语言书籍资料汇总

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

BjarneCpp
2017/11/06
0
0
Linux C编程如何使用联机帮助来解决编程问题?

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

Jeff_Linux
2014/07/06
0
0
微软面试、经典算法、编程艺术、红黑树4大系列总结

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

长平狐
2013/01/06
262
0
数据结构算法书籍推荐

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

modernizr
2014/05/22
28.1K
13

没有更多内容

加载失败,请刷新页面

加载更多

《Netkiller Java 手札》· 二进制文件操作大全

本文节选自《Netkiller Java 手札》 Netkiller Java 手札 Mr. Neo Chan, 陈景峯(BG7NYT) 中国广东省深圳市望海路半岛城邦三期 518067 +86 13113668890 <netkiller@msn.com> $Id: book.xml 6......

netkiller-
13分钟前
0
0
Fiddler Debugger post请求

常用的两种: 第一种默认的 对应URL为www 的要用请求头为:Content-Type: application/x-www-form-urlencoded 请求参数为 :param1=1234¶m2=12345 注:有些接口是指定用这种的第二方式并不...

轻量级赤影
20分钟前
1
0
如何搭建母婴亲子类知识社区

近期社交领域融资动作频繁,海尔高管、海尔医疗有限公司总裁管礼庆创办的母婴知识分享社区平台Alwayslove于上月获得700万天使轮融资。 Alwayslove是一个母婴知识分享社区平台,采用UGC模式,...

ThinkSNS账号
22分钟前
0
0
Android 自定义构建类型 BuildType

最近接触到自定义构建类型 BuildType,发现这一块有些地方稍不注意的话会被绕进去浪费点时间,既然我这边已经花费时间了,如果正好你也需要接触到 BuildType,也许接下来分享的 tips 可能会帮...

猴亮屏
23分钟前
1
0
美团点评基于 Flink 的实时数仓建设实践

引言 近些年,企业对数据服务实时化服务的需求日益增多。本文整理了常见实时数据组件的性能特点和适用场景,介绍了美团如何通过 Flink 引擎构建实时数据仓库,从而提供高效、稳健的实时数据服...

美团技术团队
26分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部