fzyz_sb 发表于4年前

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

1. 快速排序

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

#define SIZE 100

void	quicksort( int *A, int p, int r );
int		partition( int *A, int p, int r );
void	swap( int *px, int *py );

int main( void )
{
int		A[ SIZE ];
int		i = 0;
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");
}
}

quicksort( 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");
}
}

return 0;
}

void quicksort( int *A, int p, int r )
{
if ( p < r ){
int		q = partition( A, p, r );
quicksort( A, p, q - 1 );
quicksort( A, q + 1, r );
}
}

int partition( int *A, int p, int r )
{
int		x = A[ r ];
int		i = p - 1;
int		j = p;
for ( ; j <= r - 1; j++ ){
if ( A[ j ] <= x ){
i += 1;
swap( &A[ i ], &A[ j ] );
}
}
swap( &A[ i + 1 ], &A[ r ] );

return i + 1;
}

void	swap( int *px, int *py )
{
int temp = *px;
*px = *py;
*py = temp;
}``````

×