汕头网站设计定制,上海网络推广竞价公司,公司网站建设个人总结,东莞专业网站建设1.查找的定义 查找是这样一个过程#xff0c;即在某个项目组中寻找某一指定目标元素#xff0c;或者确定该组中并不存在该目标元素。 对其进行查找的项目的组有时也成为查找池。两种常见的查找方式#xff1a;线性查找和二分查找。为了能够查找某一对象#xff0c;我们就必… 1.查找的定义 查找是这样一个过程即在某个项目组中寻找某一指定目标元素或者确定该组中并不存在该目标元素。 对其进行查找的项目的组有时也成为查找池。两种常见的查找方式线性查找和二分查找。为了能够查找某一对象我们就必须将一个对象跟另一个对象进行比较。我们对这些算法的实现就是对某个Comparable对象的数组进行查找。因此所涉及的元素实现了Comparable接口且彼此是可比较的。我们将在Searching类头中完成这一限制。2.算法查找 2.1 线性查找 /*** 线性查找 在没有找到之前 需要一直遍历* * param data* param min* param max* param target* return*/public static T extends ComparableT boolean linearSearch(T[] data,int min, int max, T target) {int index min;boolean found false;while (!found index max) {found data[index].equals(target);index;}return false;} 2.2 二分查找 /*** 二分查找二分查找需要实现数组列表有序然后每次考察中间元素排除一半最好的方法是使用递归实现。* param data* param min* param max* param target* return* * 二分查找方法是递归实现的如果没有找到目标元素且有更多待查找数据则该方法将调用自身同时传递参数* 这些参数缩减了数组内可行候选项的规模。* * min和max索引用于确定是否还具有更多的待查找数据这就是说如果削减后的查找区间一个元素没有则该方法* 不会调用其自身且返回一个false值。* * * */public static T extends Comparable? super T boolean binarySearch(T[] data, int min, int max, T target) {boolean flag false;int mid (maxmin)/2;if(data[mid].compareTo(target)0){flag true;}else if(data[mid].compareTo(target)0){//中间大于目标if(minmid-1){flag binarySearch(data, min, mid-1, target);}}else if(data[mid].compareTo(target)0){if(mid1max){flag binarySearch(data, mid1, max, target);}}return flag;} 2.3 查找比较 线性查找最好情形是目标元素刚好是我们考察项目组的第一个项目。最糟糕的情形是出现在目标不再该组的时候且在我们确定它不在之前不得不考察每一个元素。算法的期望是n/2因此线性查找算法具有线性时间复杂度O(n)。 二分查找因为我们每比较一回我们就能够将剩余数据削减一半所以我们可以更快的找到元素。最好的情况一次找到最差是排除所有元素我们不得不进行log2n 次比较。因此找到位于该查找池中某一元素的预期情形是大约(log2n)/2次比较。 线性查找比较简单编程调试更容易实现。 线性查找无需花费额外成本来排序该查找列表。 二分查找的复杂度是对数级的这使得它对于大型查找池非常有效率。 3.排序简介 排序基于某一个标准将某一组项目按照某个规定顺序排列。 基于效率排序算法通常分为两类顺序排序和对数排序。 顺序排序它通常使用一对嵌套循环对n个元素进行排序需要大约n2 次比较。 对数排序它对n个元素进行排序大约需要nlog2n 次比较。 在n较小的时候这两类算法之间几乎不存在任何实际差别。 4.泛型补充资料 package ds.java.ch09;import java.util.ArrayList;
import java.util.Collection;
import java.util.List;/*** author LbZhang* version 创建时间2015年11月19日 上午11:16:20* description 类说明* * 综合分析* extends 可用于的返回类型限定不能用于参数类型限定。* super 可用于参数类型限定不能用于返回类型限定。* * 带有super超类型限定的通配符可以向泛型对易用写入带有extends子类型限定的通配符可以向泛型对象读取.*/
public class Genertic {public static void main(String[] args) {/*** List? extends Frut 表示 “具有任何从Fruit继承类型的列表”编译器无法确定List所持有的类型* 所以无法安全的向其中添加对象。可以添加null,因为null 可以表示任何类型。所以List 的add 方法不能* 添加任何有意义的元素但是可以接受现有的子类型ListApple 赋值。*/List? extends Fruit felist new ArrayListApple();//flist.add(new Apple());Fruit f felist.get(0);/*** List? super Fruit 表示“具有任何Fruit超类型的列表”列表的类型至少是一个 Fruit 类型* 因此可以安全的向其中添加Fruit 及其子类型。由于List? super Fruit中的类型可能是任何Fruit* 的超类型无法赋值为Fruit的子类型Apple的ListApple.* */List? super Fruit fslist new ArrayListFruit();fslist.add(new Apple());//Fruit fs fslist.get(0);}}class Food {
}class Fruit extends Food {
}class Apple extends Fruit {
}class RedApple extends Apple {
}总结 extends 可用于的返回类型限定不能用于参数类型限定。 super 可用于参数类型限定不能用于返回类型限定。 带有super超类型限定的通配符可以向泛型对易用写入带有extends子类型限定的通配符可以向泛型对象读取。——《Core Java》 转载于:https://www.cnblogs.com/mrzhang123/p/5365832.html
