天天看點

常用查找算法1. 順序查找2. 二分查找3. 分塊查找4. 哈希查找

1. 順序查找

1.1 算法原理:

  順序查找是在一個已知無(或有序)序隊列中找出與給定關鍵字相同的數的具體位置。原理是讓關鍵字與隊列中的數從第一個開始逐個比較,直到找出與給定關鍵字相同的數為止,它的缺點是效率低下。

1.2 算法實作(Java):

public static int sequenceSearch(int[] array, int des) {
    for (int i = , len = array.length; i < len; i++) {
        if (array[i] == des) {
            return i;
        }
    }
    return -;
}
           

2. 二分查找

2.1 算法原理:

  二分查找又稱折半查找,優點是比較次數少,查找速度快,平均性能好;其缺點是要求待查表為有序表,且插入删除困難。是以,二分查找方法适用于不經常變動而查找頻繁的有序清單。其算法原理如下:

  首先,假設表中元素是按升序排列,将表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄将表分成前、後兩個子表,如果中間位置記錄的關鍵字大于查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。

  重複以上過程,直到找到滿足條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。

2.2 算法實作(Java):

public static int binarySearch(int[] array, int des) {
    int low = ;
    int high = array.length - ;
    while (low <= high) {
        int middle = (low + high) >> ;
        if (array[middle] == des) {
            return middle;
        } else if (array[middle] > des) {
            high = middle - ;
        } else {
            low = middle + ;
        }
    }
    return -;
}
           

3. 分塊查找

3.1 算法原理:

  分塊查找又稱索引順序查找,是折半查找和順序查找的一種改進方法,折半查找雖然具有很好的性能,但其前提條件時線性表順序存儲而且按照關鍵碼排序,這一前提條件在結點樹很大且表元素動态變化時是難以滿足的。而順序查找可以解決表元素動态變化的要求,但查找效率很低。如果既要保持對線性表的查找具有較快的速度,又要能夠滿足表元素動态變化的要求,則可采用分塊查找的方法。

  分塊查找的速度雖然不如折半查找算法,但比順序查找算法快得多,同時又不需要對全部節點進行排序。當節點很多且塊數很大時,對索引表可以采用折半查找,這樣能夠進一步提高查找的速度。

  分塊查找要求把一個大的線性表分解成若幹塊,每塊中的節點可以任意存放,但塊與塊之間必須排序。假設是按關鍵碼值非遞減的,那麼這種塊與塊之間必須滿足已排序要求,實際上就是對于任意的i,第i塊中的所有節點的關鍵碼值都必須小于第i+1塊中的所有節點的關鍵碼值。此外,還要建立一個索引表,把每塊中的最大關鍵碼值作為索引表的關鍵碼值,按塊的順序存放到一個輔助數組中,顯然這個輔助數組是按關鍵碼值非遞減排序的。查找時,首先在索引表中進行查找,确定要找的節點所在的塊。由于索引表是排序的,是以,對索引表的查找可以采用順序查找或折半查找;然後,在相應的塊中采用順序查找,即可找到對應的節點。

4. 哈希查找

4.1 算法原理:

  哈希查找是通過計算資料元素的存儲位址進行查找的一種方法。哈希查找的操作步驟如下:

  (1)用給定的哈希函數構造哈希表;

  (2)根據選擇的沖突處理方法解決位址沖突;

  (3)在哈希表的基礎上執行哈希查找。

  哈希查找的本質是先将資料映射成它的哈希值。哈希查找的核心是構造一個哈希函數,它将原來直覺、整潔的資料映射為看上去似乎是随機的一些整數。

  哈希查找的産生有這樣一種背景——有些資料本身是無法排序的(如圖像),有些資料是很難比較的(如圖像)。如果資料本身是無法排序的,就不能對它們進行比較查找。如果資料是很難比較的,即使采用折半查找,要比較的次數也是非常多的。是以,哈希查找并不查找資料本身,而是先将資料映射為一個整數(它的哈希值),并将哈希值相同的資料存放在同一個位置——即以哈希值為索引構造一個數組。

  在哈希查找的過程中,隻需先将要查找的資料映射為它的哈希值,然後查找具有這個哈希值的資料,這就大大減少了查找次數。

4.2 解決哈希沖突:

  影響哈希查找效率的一個重要因素是哈希函數本身。當兩個不同的資料元素的哈希值相同時,就會發生沖突。為減少發生沖突的可能性,哈希函數應該将資料盡可能分散地映射到哈希表的每一個表項中。解決沖突的方法有以下兩種:

  (1) 開放位址法

  如果兩個資料元素的哈希值相同,則在哈希表中為後插入的資料元素另外選擇一個表項。

  當程式查找哈希表時,如果沒有在第一個對應的哈希表項中找到符合查找要求的資料元素,程式就會繼續往後查找,直到找到一個符合查找要求的資料元素,或者遇到一個空的表項。

  (2) 鍊位址法

  将哈希值相同的資料元素存放在一個連結清單中,在查找哈希表的過程中,當查找到這個連結清單時,必須采用線性查找方法。

繼續閱讀