演算法查詢

① 哈希查找演算法

散列表（Hash table，也叫哈希表），是根據鍵（Key）而直接訪問在內存存儲位置的數據結構。也就是說，它通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散列表。

通過某種轉換關系，使關鍵字適度的分散到指定大小的的順序結構中，越分散，則以後查找的時間復雜度越小，空間復雜度越高。

Hash是一種典型以空間換時間的演算法，比如原來一個長度為100的數組，對其查找，只需要遍歷且匹配相應記錄即可，從空間復雜度上來看，假如數組存儲的是byte類型數據，那麼該數組佔用100byte空間。現在我們採用Hash演算法，我們前面說的Hash必須有一個規則，約束鍵與存儲位置的關系，那麼就需要一個固定長度的hash表，此時，仍然是100byte的數組，假設我們需要的100byte用來記錄鍵與位置的關系，那麼總的空間為200byte，而且用於記錄規則的表大小會根據規則，大小可能是不定的。

通過哈希函數，我們可以將鍵轉換為數組的索引(0-M-1)，但是對於兩個或者多個鍵具有相同索引值的情況，我們需要有一種方法來處理這種沖突。

一種比較直接的辦法就是，將大小為M 的數組的每一個元素指向一個鏈表，鏈表中的每一個節點都存儲散列值為該索引的鍵值對，這就是拉鏈法。下圖很清楚的描述了什麼是拉鏈法。

「John Smith」和「Sandra Dee」 通過哈希函數都指向了152 這個索引，該索引又指向了一個鏈表， 在鏈表中依次存儲了這兩個字元串。

單獨鏈表法：將散列到同一個存儲位置的所有元素保存在一個鏈表中（聚集），該方法的基本思想就是選擇足夠大的M，使得所有的鏈表都盡可能的短小，以保證查找的效率。當鏈表過長、大量的鍵都會映射到相同的索引上，哈希表的順序查找會轉變為鏈表的查找，查找時間將會變大。對於開放定址會造成性能的災難性損失。

實現基於拉鏈表的散列表，目標是選擇適當的數組大小M，使得既不會因為空鏈表而浪費內存空間，也不會因為鏈表太而在查找上浪費太多時間。拉鏈表的優點在於，這種數組大小M的選擇不是關鍵性的，如果存入的鍵多於預期，那麼查找的時間只會比選擇更大的數組稍長。另外，我們也可以使用更高效的結構來代替鏈表存儲。如果存入的鍵少於預期，索然有些浪費空間，但是查找速度就會很快。所以當內存不緊張時，我們可以選擇足夠大的M，可以使得查找時間變為常數，如果內存緊張時，選擇盡量大的M仍能夠將性能提高M倍。

線性探測法是開放定址法解決哈希沖突的一種方法，基本原理為，使用大小為M的數組來保存N個鍵值對，其中M>N，我們需要使用數組中的空位解決碰撞沖突。如下圖所示：

對照前面的拉鏈法，在該圖中，「Ted Baker」 是有唯一的哈希值153的，但是由於153被「Sandra Dee」佔用了。而原先「Snadra Dee」和「John Smith」的哈希值都是152的，但是在對「Sandra Dee」進行哈希的時候發現152已經被佔用了，所以往下找發現153沒有被佔用，所以索引加1 把「Sandra Dee」存放在沒有被佔用的153上，然後想把「Ted Baker」哈希到153上，發現已經被佔用了，所以往下找，發現154沒有被佔用，所以值存到了154上。

單純論查找復雜度：對於無沖突的Hash表而言，查找復雜度為O(1)。

原文： 哈希查找 - 賣賈筆的小男孩 - 博客園 (cnblogs.com)

② 二分查找演算法

二分查找演算法，該演算法要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。如果一個序列是無序的或者是鏈表，那麼該序列就不能使用二分查找。

二分查找演算法原理：若待查序列為空，則返回-1，並退出演算法；若待查序列不為空，則將它的中間元素與目標數值進行比較，判斷是否相等；若相等，則返回中間元素索引，並退出演算法；此時已查找成功。若不相等，則比較中間元素與目標數值的大小。

二分查找的一個技巧是：不要出基升亮現else，而是把所有情況用else，if寫清楚，這樣可以清楚地展現所有細節。本文都會使用else，if，旨在講清楚搏寬，讀者理解後可自行簡化。

③ mysql關系型標准查詢演算法有哪些

一、單表查詢
1.帶條件的查詢
基本祥跡語法：select * from +表名稱 +where 條件;

1)范圍查詢：

eg：where 欄位 between 10 and 100;

2)模糊查詢

eg：where 欄位 like』%不確定%』

備註：嘩斗%代表多個字元，_下劃線代表一個字元，^a代表以a為開頭的數據，a$代表以a為結尾的數據，[abc]匹配所包含的任意一個字元。

2.多條件查詢

備註：當and和or同時使用時，and優先順序高於or。謹蘆並如果想要優先帶or的條件，對帶or部分條件帶括弧即可。

二、多表關聯查詢

④ 基本演算法——二分查找演算法

    二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

1.條件

（1）必須採用 順序存儲結構 。

（2）必須按關鍵字大小有序排列。

2.步奏

（1）首先，假設表中元素是按升序排列，將表中間位置記錄的 關鍵字 與查找關鍵字比較，如果兩者相等，則查找成功；

（2）否則利用中間位置 記錄 將表分成前、後和搏兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表；

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

3.舉例

    有一組元素{1，2，3，4，5，6，7，8，9}，如何查到元素為3。

（1）找到數組中中間元素值5，不等於3，所以把數組分為{1，2，3，4}，{5，6，7，8，9}；

（2）因告棚衫為5大於3，所以3在前一個數組{1，2，3，4}中查找，中間變數2，3比2大，所以在{3，4}中查詢；

（3）查詢到3=3，成襪腔功。

4.復雜度

     最好的情況下，1次查詢成功；最壞的情況下，查詢到最後兩個數或者最後也查不到相等數，時間復雜度為O(log2n)。

⑤ php一億個排好序手機號,用什麼演算法可以查詢到我的號碼出現過

使用二分查找演算法。二分查找演算法升慎是一種高效的查找演算法，可以在有序數組中快速查找指定元素，在一億個排好序的手機號中查詢自己的號碼是否出現過，可以使用二分查找演算法。要頻繁地進行插入、刪除操作，會導致數組讓飢的有序性被破壞，從而影響查找效率，因此，在實際應用中，需要吵滑敬根據具體情況選擇合適的數據結構和演算法。

⑥ 折半查找演算法的平均查詢長度為多少

首先，折半查找可以藉助於一個二叉樹來描述。
為了簡化討論，則把這棵樹近似看成滿二叉樹，設二叉樹的高度為h(h>1)
則，根據二叉樹的性質，它有最大節點數n=2^h-1，
則h=log2(n+1) (2是底數)。那麼二叉樹的第j層節點數為：2^(j-1)
假定每個元素的查找概率相等，則，pi=1/n (pi為第i個節點的查找概率)
那麼平均查找長度為 1/n*（1*2^0+2*2^1+3*2^2+……+j*2^(j-1)）
則經過化簡計算，得平均查找長度為：(（n+1）/n ) *log2(n+1)-1 (其中對數中的2為底數：即log以2為底（n+1)的對數）
注 : 當n很大時 ，可近似為 log2(n+1)-1
其中 1*2^0+2*2^1+3*2^2+……+j*2^(j-1)的求法如下：
設 S = 1*2^0 + 2*2^1+3*2^2 +……+ j*2^(j-1) ,
則 2S = 1*2^1+2*2^2 +……+ (j-1)*2^(j-1) + j*2^j
則 2S - S = -( 2^0 + 2^1 + 2 ^2 + …… + 2 ^(j-1)) + j *2^j
即 S = - (2^j-1)+j*2^j
帶入化簡即可。

⑦ 幾種常見的查找演算法之比較

二分法平均查找效率是O(logn)，但是需要數組是排序的。如果沒有排過序，就只好先用O（nlogn)的預處理為它排個序了。而且它的插入比較困難，經常需要移動整個數組，所以動態的情況下比較慢。

哈希查找理想的插入和查找效率是O(1)，但條件是需要找到一個良好的散列函數，使得分配較為平均。另外，哈希表需要較大的空間，至少要比O(n)大幾倍，否則產生沖突的概率很高。

二叉排序樹查找也是O(logn)的，關鍵是插入值時需要做一些處理使得它較為平衡（否則容易出現輕重的不平衡，查找效率最壞會降到O(n)），而且寫起來稍微麻煩一些，具體的演算法你可以隨便找一本介紹數據結構的書看看。當然，如果你用的是c語言，直接利用它的庫類型map、multimap就可以了,它是用紅黑樹實現的，理論上插入、查找時間都是O(logn)，很方便，不過一般會比自己實現的二叉平衡樹稍微慢一些。

⑧ 查找演算法的作用

查找就是在一個數據集合里查找到你需要的數據，查找演算法就是在查找過程中使用的演算法。查找演算法有好多，最基礎的就是線性表查找。
因為提到了演算法，所以需要注意的是時間復雜度跟空間復雜度，進而涉及到數據的存儲方式，比如數組，鏈表，矩陣，樹，圖等等數據結構，這些數據結構可以幫助你降低演算法的復雜度。
如果有興趣，隨便找本數據結構書翻翻，裡面或多或少都會有講解。用關鍵字標識一個數據元素，查找時根據給定的某個值，在表中確定一個關鍵字的值等於給定值的記錄或數據元素。在計算機中進行查找的方法是根據表中的記錄的組織結構確定的。順序查找也稱為線形查找，從數據結構線形表的一端開始，順序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等於k的結點，表示查找失敗。二分查找要求線形表中的結點按關鍵字值升序或降序排列，用給定值k先與中間結點的關鍵字比較，中間結點把線形表分成兩個子表，若相等則查找成功；若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結束發現表中沒有這樣的結點。分塊查找也稱為索引查找，把線形分成若干塊，在每一塊中的數據元素的存儲順序是任意的，但要求塊與塊之間須按關鍵字值的大小有序排列，還要建立一個按關鍵字值遞增順序排列的索引表，索引表中的一項對應線形表中的一塊，

⑨ 常見查找和排序演算法

查找成功最多要n 次，平均（n+1）/2次， 時間復雜度為O(n) 。
優點：既適用順序表也適用單鏈表，同時對表中元素順序無要求，給插入帶來方便，只需插入表尾即可。
缺點：速度較慢。

改進：在表尾設置一個崗哨，這樣不用去循環判斷數組下標是否越界，因為最後必然成立。

適用條件：

二分查找的判定樹不僅是二叉排序樹，而且是一棵理想平衡樹。 時間復雜度為O(lbn) 。

循環實現

遞歸實現

待排序的元素需要實現 Java 的 Comparable 介面，該介面有 compareTo() 方法，可以用它來判斷兩個元素的大小關系。

從數組中選擇最小元素，將它與數組的第一個元素交換位置。再從數組剩下的元素中選擇出最小的元素，將它與數組的第二個元素交換位置。不斷進行這樣的操作，直到將整個數組排序。

選擇排序需要 ~N2/2 次比較和 ~N 次交換，==它的運行時間與輸入無關==，這個特點使得它對一個已經排序的數組也需要這么多的比較和交換操作。

從左到右不斷 交換相鄰逆序的元素 ，在一輪的循環之後，可以讓未排序的最大元素上浮到右側。

在一輪循環中，如果沒有發生交換，那麼說明數組已經是有序的，此時可以直接退出。

每次都 將當前元素插入到左側已經排序的數組中 ，使得插入之後左側數組依然有序。

對於數組 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交換相鄰元素，令逆序數量減少 1，因此插入排序需要交換的次數為逆序數量。

==插入排序的時間復雜度取決於數組的初始順序，如果數組已經部分有序了，那麼逆序較少，需要的交換次數也就較少，時間復雜度較低==。

對於大規模的數組，插入排序很慢，因為它只能交換相鄰的元素，每次只能將逆序數量減少 1。希爾排序的出現就是為了解決插入排序的這種局限性，它通過交換不相鄰的元素，每次可以將逆序數量減少大於 1。

希爾排序使用插入排序對間隔 h 的序列進行排序。通過不斷減小 h，最後令 h=1，就可以使得整個數組是有序的。

希爾排序的運行時間達不到平方級別，使用遞增序列 1, 4, 13, 40, ... 的希爾排序所需要的比較次數不會超過 N 的若干倍乘於遞增序列的長度。後面介紹的高級排序演算法只會比希爾排序快兩倍左右。

歸並排序的思想是將數組分成兩部分，分別進行排序，然後歸並起來。

歸並方法將數組中兩個已經排序的部分歸並成一個。

將一個大數組分成兩個小數組去求解。

因為每次都將問題對半分成兩個子問題，這種對半分的演算法復雜度一般為 O(NlogN)。

先歸並那些微型數組，然後成對歸並得到的微型數組。

取 a[l] 作為切分元素，然後從數組的左端向右掃描直到找到第一個大於等於它的元素，再從數組的右端向左掃描找到第一個小於它的元素，交換這兩個元素。不斷進行這個過程，就可以保證左指針 i 的左側元素都不大於切分元素，右指針 j 的右側元素都不小於切分元素。當兩個指針相遇時，將切分元素 a[l] 和 a[j] 交換位置。

快速排序是原地排序，不需要輔助數組，但是遞歸調用需要輔助棧。

快速排序最好的情況下是每次都正好將數組對半分，這樣遞歸調用次數才是最少的。這種情況下比較次數為 CN=2CN/2+N，復雜度為 O(NlogN)。

最壞的情況下，第一次從最小的元素切分，第二次從第二小的元素切分，如此這般。因此最壞的情況下需要比較 N2/2。為了防止數組最開始就是有序的，在進行快速排序時需要隨機打亂數組。

因為快速排序在小數組中也會遞歸調用自己，對於小數組，插入排序比快速排序的性能更好，因此在小數組中可以切換到插入排序。

最好的情況下是每次都能取數組的中位數作為切分元素，但是計算中位數的代價很高。一種折中方法是取 3 個元素，並將大小居中的元素作為切分元素。

對於有大量重復元素的數組，可以將數組切分為三部分，分別對應小於、等於和大於切分元素。

三向切分快速排序對於有大量重復元素的隨機數組可以在線性時間內完成排序。

快速排序的 partition() 方法，會返回一個整數 j 使得 a[l..j-1] 小於等於 a[j]，且 a[j+1..h] 大於等於 a[j]，此時 a[j] 就是數組的第 j 大元素。

可以利用這個特性找出數組的第 k 大的元素。

該演算法是線性級別的，假設每次能將數組二分，那麼比較的總次數為 (N+N/2+N/4+..)，直到找到第 k 個元素，這個和顯然小於 2N。

堆中某個節點的值總是大於等於其子節點的值，並且堆是一顆完全二叉樹。

堆可以用數組來表示，這是因為堆是完全二叉樹，而完全二叉樹很容易就存儲在數組中。位置 k 的節點的父節點位置為 k/2，而它的兩個子節點的位置分別為 2k 和 2k+1。這里不使用數組索引為 0 的位置，是為了更清晰地描述節點的位置關系。

在堆中，當一個節點比父節點大，那麼需要交換這個兩個節點。交換後還可能比它新的父節點大，因此需要不斷地進行比較和交換操作，把這種操作稱為上浮。

類似地，當一個節點比子節點來得小，也需要不斷地向下進行比較和交換操作，把這種操作稱為下沉。一個節點如果有兩個子節點，應當與兩個子節點中最大那個節點進行交換。

將新元素放到數組末尾，然後上浮到合適的位置。

從數組頂端刪除最大的元素，並將數組的最後一個元素放到頂端，並讓這個元素下沉到合適的位置。

把最大元素和當前堆中數組的最後一個元素交換位置，並且不刪除它，那麼就可以得到一個從尾到頭的遞減序列，從正向來看就是一個遞增序列，這就是堆排序。

一個堆的高度為logN，因此在堆中插入元素和刪除最大元素的復雜度都為 logN。

對於堆排序，由於要對 N 個節點進行下沉操作，因此復雜度為 NlogN。

堆排序是一種原地排序，沒有利用額外的空間。

現代操作系統很少使用堆排序，因為它無法利用局部性原理進行緩存，也就是數組元素很少和相鄰的元素進行比較和交換。

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，==計數排序要求輸入的數據必須是有確定范圍的整數==。

當輸入的元素是 n 個 0 到 k 之間的整數時，它的==運行時間是 O(n + k)==。計數排序不是比較排序，排序的速度快於任何比較排序演算法。由於用來計數的數組C的長度取決於待排序數組中數據的范圍（等於待排序數組的最大值與最小值的差加上1），這使得計數排序對於數據范圍很大的數組，需要大量時間和內存。比較適合用來排序==小范圍非負整數數組的數組==。

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：

同時，對於桶中元素的排序，選擇何種比較排序演算法對於性能的影響至關重要。

當輸入數據均勻分配到每一個桶時最快，當都分配到同一個桶時最慢。

實間復雜度N*K

快速排序是最快的通用排序演算法，它的內循環的指令很少，而且它還能利用緩存，因為它總是順序地訪問數據。它的運行時間近似為 ~cNlogN，這里的 c 比其它線性對數級別的排序演算法都要小。

使用三向切分快速排序，實際應用中可能出現的某些分布的輸入能夠達到線性級別，而其它排序演算法仍然需要線性對數時間。

⑩ 查找演算法有哪些

查找演算法常用的有，順序查找，二分查找，哈希表查找，等等。