从数组中查找最值（三种基本算法）

程序中，我们经常使用数组（列表）存储给定的线性序列（例如 {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<numsSize;i++)
    {
        if(nums[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;
	}

}