# 算法导论复习:第二章 原

fzyz_sb

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. 分治法排序

``````#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. 判断逆序对

``````#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

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

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：协议》读书笔记

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高并发配置调优

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

52分钟前
2
0

3
0