算法导论复习:第七章
博客专区 > fzyz_sb 的博客 > 博客详情
算法导论复习:第七章
fzyz_sb 发表于4年前
算法导论复习:第七章
  • 发表于 4年前
  • 阅读 37
  • 收藏 0
  • 点赞 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;
}



程序输出:



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