最简单的当然是一个个找进行对比的方法啦~:
int max = Integer.MIN_VALUE; for (int j = 0; j < arr.length; j++) { if (arr[j]>max) max = arr[j]; } return max;
输出
当然还是有一些有趣的操作的,代码量较少的是使用Arrays.sort(arr);:
import java.util.Arrays; public static int MAX(int[] arr) { Arrays.sort(arr); return arr[arr.length-1]; }
但是这里我查了一下,Arrays.sort(arr);的时间复杂度并不是O(n)
-
如果要对数组进行排序的话自然Arrays.sort(arr)更方便
-
但是如果只是取最大值的话,使用循环能达到小一点的O(n)的时间复杂度,
这里使用的是Java 8版本,点进Arrays.sort()方法发发现使用的是双轴快排(DualPivotQuicksort)
时间复杂度绿色字体也说了是O(nlogn),通常要比传统的快排(也叫做单轴快排)快
双轴快排(DualPivotQuicksort)双轴快排(DualPivotQuicksort),顾名思义有两个轴元素pivot1,pivot2,且pivot ≤pivot2,将序列分成三段:x < pivot1、pivot1 ≤ x ≤ pivot2、x >pivot2,然后分别对三段进行递归。这个算法通常会比传统的快排效率更高,也因此被作为Arrays.java中给基本类型的数据排序的具体实现。
2.2 Arrays.sort()在1.7中使用了经过改进的TimsortTimsort的排序过程
- 如果长度小于64直接进行插入排序
- 首先遍历数组收集每个元素根据特定的条件组成一个run
- 得到一个run之后会把他放入栈中
- 如果栈顶部几个的run符合合并条件,就会触发合并操作合并相邻的两个run留下一个run
- 合并操作会使用尽量小的内存空间和GALLOP模式来加速合并
参考:
关于Java:Arrays.sort()是否会增加时间复杂度和时空复杂度?
世界上最快的排序算法——Timsort