fzyz_sb 发表于4年前

• 发表于 4年前
• 阅读 218
• 收藏 11
• 评论 0

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

×