程序中，我们经常使用数组（列表）存储给定的线性序列（例如 {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} 中最大值的实现过程：
文章来源：https://www.toymoban.com/news/detail-727864.html
分治算法的实现思路是：不断地等分数组中的元素，直至各个分组中元素的个数 ≤2。由于每个分组内的元素最多有 2 个，很容易就可以找出其中的最值（最大值或最小值），然后这些最值再进行两两比较，最终找到的最值就是整个数组中的最值。
如图所示，借助“分而治之”的思想，我们将“找 {3, 7, 2, 1} 中最值”的问题转换成了：先找出 {3 , 7]、[2 , 1} 中各自的最值，找出的最值再进行两两比较，最终就可以找到整个数组中的最值。
文章来源地址https://www.toymoban.com/news/detail-727864.html
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;
}
}到了这里，关于从数组中查找最值（三种基本算法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
