找出数据集合中的最小值和最大值的两种算法比较

最小值和最大值

                                                                                                                   —— 算导笔记

实现太过于简单以至于算导里面都不讲代码实现，只是简单介绍了理论.

通常寻找最大值最小值的方法

方法一：

void max_min(int* array,int size,int* max)
{
	int tmp = 0;

	for(tmp = 0,*max = array[0];tmp < size;tmp++)
	{
		*max = *max > array[tmp] ? *max : array[tmp];
	}
}
           

这里如果寻找最小值同理

可以发现如果同时要求找到最小值和最大值需要比较2*size次

有没有更快的方法呢？

方法二:

/**************************************************************************
code writer	:	EOF
code date	:	2014.09.21
code file	:	min_max.c
e-mail		:	[email protected]

code description:
	
	A faster way to find min and max value in 
data array.

#BUG1:
	for(tmp = 0,*min = array[0],array[1];tmp < size;tmp += 2)

fix it up by:	licoderli 

	for(tmp = 0,*min = array[0],*max = array[1];tmp < size;tmp += 2)

Thanks licoderli.

**************************************************************************/
#include <stdio.h>

void max_min(int* array,int size,int* min,int* max)
{
	int tmp = 0;

	for(tmp = 0,*min = array[0],*max = array[1];tmp < size;tmp += 2)
	{
		if(array[tmp] < array[tmp+1])
		{
			*min = *min < array[tmp]   ? *min : array[tmp];
			*max = *max > array[tmp+1] ? *max : array[tmp+1];
		}
		else
		{
			*min = *min < array[tmp+1]   ? *min : array[tmp+1];
			*max = *max > array[tmp]     ? *max : array[tmp];
		}
	}
}

int main()
{
	int array[10] = {2,3,7,1,9,6,4,5,8,0};

	int size = sizeof(array)/sizeof(array[0]);

	int tmp = 0;
	int min = 0;
	int max = 0;

	for(tmp = 0;tmp < size;tmp++)
	{
		printf("%3d",array[tmp]);
	}

	printf("\n");

	max_min(array,size,&min,&max);

	printf("min:%4d max:%4d\n",min,max);

	return 0;
}
           

而这种方法会把比较次数降低到3*size/2 次

感谢licoderli, ta在2014.09.28. 发现并修正了代码中*max 没有初始化的问题

能够认真看程序的人很难得

                                                                                                  —— EOF