數據結構(Java)——查找和排序（1）

1.查找的定義

    查找是這樣一個過程，即在某個項目組中尋找某一指定目標元素，或者確定該組中并不存在該目標元素。 對其進行查找的項目的組有時也成為查找池。兩種常見的查找方式：線性查找和二分查找。為了能夠查找某一對象，我們就必須將一個對象跟另一個對象進行比較。我們對這些算法的實現就是對某個Comparable對象的數組進行查找。因此，所涉及的元素實現了Comparable接口且彼此是可比較的。我們將在Searching類頭中完成這一限制。

2.算法查找

2.1 線性查找

/*** 線性查找 在沒有找到之前 需要一直遍歷* * @param data* @param min* @param max* @param target* @return*/public static <T extends Comparable<T>> 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 = (max+min)/2;if(data[mid].compareTo(target)==0){flag = true;}else if(data[mid].compareTo(target)>0){//中間大于目標if(min<=mid-1){flag = binarySearch(data, min, mid-1, target);}}else if(data[mid].compareTo(target)<0){if(mid+1<=max){flag = binarySearch(data, mid+1, 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 方法不能* 添加任何有意義的元素，但是可以接受現有的子類型List<Apple> 賦值。*/List<? extends Fruit> felist = new ArrayList<Apple>();//flist.add(new Apple());Fruit f = felist.get(0);/*** List<? super Fruit> 表示“具有任何Fruit超類型的列表”，列表的類型至少是一個 Fruit 類型，* 因此可以安全的向其中添加Fruit 及其子類型。由于List<? super Fruit>中的類型可能是任何Fruit* 的超類型，無法賦值為Fruit的子類型Apple的List<Apple>.* */List<? super Fruit> fslist = new ArrayList<Fruit>();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》