欢迎光临北京国标标准舞学院网!

服务热线:010-69453013

从数组中查找最值(三种基本算法)

程序中,我们经常使用数组(列表)存储给定的线性序列(例如 {1,2,3,4}),那么如何查找数组(序列)中的最大值或者最小值呢?

所以这里简单提供了三种比较常见的算法来查找数组中的最值(这里以查找最大值为例)

  • 普通算法
  • 排序算法
  • 分治算法
1)普通算法

普通算法的解决思路是:创建两个变量 max 和 min 分别记录数组中的最大值和最小值,它们的初始值都是数组中的第一个数字。从第 2 个数字开始遍历数组,每遇到一个比 max 大的数字,就将它存储到 max 变量中;每遇到一个比 min 小的数字,就将它存储到 min 变量中。直到遍历完整个数组,max 记录的就是数组中的最大值,min 记录的就是数组中的最小值。

下面的动画,演示了找最大值的过程:
 

int get_max(int* nums,int numsSize)
{
    int max = nums[0];
    for(int i = 1;i max)
        {
            max = nums[i];
        }
    }
    return max;
}
 2)排序算法

所谓排序算法,就是先将整个数组进行排序,当排完序之后整个数组就是有序的,不管是升序还是降序都能相对的找到数组中的最值

十种排序算法都可以使用,这里采用快速排序算法(这里不太明白该算法原理的可以去查找一下快速排序算法的原理)

int partition(int* arr, int left, int right)
{
	//设置两个下标
	int index1 = left;
	int index2 = right - 1;
	int temp = 0;
	//设置为中间值
	int pivot = arr[right];
	while (1)
	{
		//index1下标向后遍历直到找到一个大于中间值的元素
		while (arr[index1] < pivot)
		{
			index1++;
		}
		//同理,index2下标向前遍历直到找到小于中间值的元素
		while (arr[index2] > pivot)
		{
			index2--;
		}
		if (index1 >= index2)
		{
			break;
		}
		//进行交换两个下标指向的值
		else
		{
			temp = arr[index1];
			arr[index1] = arr[index2];
			arr[index2] = temp;
			//index1和index2都向前移动一个单位准备下次遍历
			index1++;
			index2--;
		}
	}//

	//当跳出循环之后就将中间值pivot从最后一个位置调换到中间位置
	temp = arr[right];
	arr[right] = arr[index1];
	arr[index1] = temp;
	return index1;
}
void the_quick_sort(int* arr,int left,int right)
{
	int par;
	//数组中只存在一个数或是不存在数,数组将不在进行分割
	if (right - left <= 0)
	{
		return;
	}
	else
	{
		//调用partition函数进行分割
		par = partition(arr, left, right);
		the_quick_sort(arr, left, par - 1);
		the_quick_sort(arr, par + 1, right);
	}
}

只要进行排序完成之后,就可以清晰的找到数组的最值

3)分治算法
下图展示了用分治算法查找 {3, 7, 2, 1} 中最大值的实现过程:
 


分治算法的实现思路是:不断地等分数组中的元素,直至各个分组中元素的个数 ≤2。由于每个分组内的元素最多有 2 个,很容易就可以找出其中的最值(最大值或最小值),然后这些最值再进行两两比较,最终找到的最值就是整个数组中的最值。
如图所示,借助“分而治之”的思想,我们将“找 {3, 7, 2, 1} 中最值”的问题转换成了:先找出 {3 , 7]、[2 , 1} 中各自的最值,找出的最值再进行两两比较,最终就可以找到整个数组中的最值。

 

int get_max(int arr[], int left, int right)
{
	//left左下标 right 右下标
	//首先判断,传入的数组是不是空数组
	if (arr == NULL)
	{
		return -1;
	}
	//当数组中只有一个值的时候
	if (right - left == 0)
	{
		return arr[left];
	}
	//此时数组中只有两个值,直接比较即可
	if ((right - left) <= 1)
	{
		if (arr[left] > arr[right])
		{
			return arr[left];
		}
		return arr[right];
	}
	int middle = (right - left) / 2 + left;
	int max_left = get_max(arr, left, middle);
	int max_right = get_max(arr, middle + 1, right);
	//将数组划成两个边后,max_left 和max_right分别是两个的最大值,然后直接比较这个值就好了
	if (max_left > max_right)
	{
		return max_left;
	}
	else
	{
		return max_right;
	}

}