算法导论复习:第二章
博客专区 > fzyz_sb 的博客 > 博客详情
算法导论复习:第二章
fzyz_sb 发表于4年前
算法导论复习:第二章
  • 发表于 4年前
  • 阅读 217
  • 收藏 11
  • 点赞 0
  • 评论 0
摘要: 复习算法导论,不对算法进行分析,只是简单的对一些问题作出代码性解答,尽量用指针而非数组,而且尽量用malloc,尝试用free,但实际开发中这种方式并不好.第二章为算法基础

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;
}



程序输出:


标签: C 算法基础
共有 人打赏支持
粉丝 365
博文 209
码字总数 447144
×
fzyz_sb
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: