Java常用基本算法….docVIP

4.1 算法 前面我们已经讲过，程序=数据结构+算法。 什么是算法？对一个现有的问题我们采取的解决过程及方法，即为算法。一个用算法实现的程序会耗费两种资源：处理时间和内存。 算法的效率分析标准： 时间复杂度 空间复杂度 简单性和清晰性 对于时间复杂度，可以通过System.currentTimeMillis()方法来测试。例如： public class Test { public static void main(String args[]) { System.out.println(System.currentTimeMillis()); fun(); System.out.println(System.currentTimeMillis()); } public static void fun() { double a = 0; for(int i = 0; i 10000; i++) for(int j = 0; j 10000; j++) for(int k = 0; k 100; k++) a++; } } 前后两次获得当前系统时间的差值就是运行所消耗的时间（毫秒为单位）。 通过System.currentTimeMillis()方法来测试的缺点： a.不同的平台执行的时间不同 b.有些算法随着输入数据的加大，测试时间会变得不切实际！ 4.2 查找 4.2.1 查找之线性查找（直接查找） 算法思路：从数组的第一个元素开始查找，并将其与查找值比较，如果相等则停止，否则继续下一个元素查找，直到找到匹配值。 注意：被查找的数组中的元素可以是无序的、随机的。 实例： import java.util.*; public class Demo1 { public static void main(String args[]) { int iArr[] = {32, 9, 78, 44, 29, 18, 97, 49, 56, 61}; System.out.println(数组的所有元素为：); for(int i : iArr) System.out.print(i + ); System.out.println(); System.out.print(请输入你要查找的元素：); Scanner scan = new Scanner(System.in); int iNum = scan.nextInt(); int index = straightSearch(iArr, iNum); if(index == -1) System.out.println(没有找到元素 + iNum); else System.out.println(找到元素 + iNum + , 下标为: + index); } public static int straightSearch(int[] arr, int num) { int i = 0; for(; i arr.length; i++) { if(arr[i] == num) return i; } return -1; } } 4.2.2 查找之折半查找（二分查找） 算法思路：假设被查找数组中的元素是升序排列的，那我们查找值时，首先会直接到数组的中间位置(数组长度/2)，并将中间值和查找值比较，如果相等则返回，否则，如果当前元素值小于查找值，则继续在数组的后面一半查找(重复上面过程)；如果当前元素值大于查找值，则继续在数组的前面一半查找，直到找到目标值或者无法再二分数组时停止。 注意：二分查找只是针对有序排列的各种数组或集合。 实例： //不利用递归实现 import java.util.*; public class Demo1 { public static void main(String args[]) { int iArr[] = {1, 2, 3, 4, 6, 8, 22, 44, 99, 111, 112, 116}; System.out.println(数组的所有元素为：); for(int i : iArr) System.out.print(i + ); System.out.println(); System.out.print(请输入你要查找的元素：); Scanner scan = new Scanner(System.in); int iNum = scan.nextInt(); int index