查找演算法比較

❶ 要求設計實現一個查找演算法比較，能對順序查找、折半查找、分塊查找的平均查找長度進行比較

給你一個我曾經做過的題，不是太一樣你可以參考，希望對你有所幫助。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const int ARRSIZE= 10015;
// 從小到大排序數組元素
void asort(int *a, int s)
{
int i, j, k, t;
for (i = 0; i < s-1; ++i)
{
k = i;
for (j = i + 1; j < s; ++j)
{
if (a[k] > a[j])
{
k = j;
}
}

if (k != i)
{
t = a[i];
a[i] = a[k];
a[k] = t;
}
}
}

// 順序查找，找到返回該元素數組下標，否則返回-1
int SeqSearch(int *a, int s, int k)
{
int i;
for (i = 0; i < s; ++i)
{
if (k == a[i])
return i;
}

return -1;
}

// 折半查找，找到返回該元素數組下標，否則返回-1
int BinSearch(int *a, int s, int k)
{
int low = 0;
int high = s - 1;

while (low <= high)
{
int mid = (low + high) / 2;

if (k == a[mid])
{
return mid;
}
else
{
if (k < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}

return -1;
}

// 分塊查找，找到返回該元素數組下標，否則返回-1，bs表示數列分成的塊數
int BlkSearch(int *a, int s, int k, int bs)
{
int i, j, t = s / bs;

for (i = 0; i < bs; ++i)
{
if (k >= a[i*t] && k <= a[i*t+t-1])
{
int e = i*t+t;
for (j = i*t; j < e; ++j)
if (k == a[j])
return j;
}
}

--i;
for (i = i * bs; i < s; ++i)
{
if (k == a[i])
return i;
}
return -1;
}

void main()
{
int i, k, a[ARRSIZE];

srand(time(NULL));
for (i = 0; i < ARRSIZE; ++i)
a[i] = rand() % ARRSIZE;

asort(a, ARRSIZE);

/*
for (i = 0; i < ARRSIZE; ++i)
printf("%d ", a[i]);
*/
putchar('\n');
scanf("%d", &k);
if (SeqSearch(a, ARRSIZE, k) != -1)
printf("%d is found in array\n", k);
if (BinSearch(a, ARRSIZE, k) != -1)
printf("%d is found in array\n", k);
if (BlkSearch(a, ARRSIZE, k, 100) != -1)
printf("%d is found in array\n", k);

}

❷ 二分查找演算法

前提要求數據排好序，有遞歸和非遞歸版本
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while (left<=right) { /注釋中為遞歸演算法，執行效率低，不推薦
mid=(left+right)/2;
/* if (key<Array[mid]) {
return(binSearch(Array,left,mid,key));
}
else if(key>Array[mid]){
return (binSearch(Array,mid+1,right,key));
}
else
return mid;
*/
if (key<Array[mid]) {
right=mid-1;
}
else if(key>Array[mid]){
left=mid+1;
}
else
return mid;
}
return -1;
}

❸ 對比順序查找、二分查找和哈希查找演算法,它們各自的特點是什麼

順序查找,二分查找和哈希查找演算法,它們各自的特點是：
1.對比順序查找的特點就是從表的第一個元素開始一個一個向下查找，如果有和目標一致的元素，查找成功;如果到最後一個元素仍沒有目標元素，則查找失敗。
2.二分查找的特點就是從表中間開始查找目標元素。如果找到一致元素，則查找成功。如果中間元素比目標元素小，則仍用二分查找方法查找表的後半部分(表是遞增排列的)，反之中間元素比目標元素大，則查找表的前半部分。
3.哈希演算法的特點是是使用給定數據構造哈希表，然後在哈希表上進行查找的一種演算法。先給定一個值，然後根據哈希函數求得哈希地址，再根據哈希地址查找到要找的元素。是通過數據元素的存儲地址進行查找的一種演算法。

❹ 二分查找與分塊查找演算法的比較

我比較喜歡用二分法，這是一個比較簡單的方法，適用面也較廣，但可能出現漏解，而分塊，我以為更是一種靠運氣的演算法。

❺ 對比順序查找,二分查找和哈希查找演算法,它們各自的特點是什麼

1.對比順序查找就是順序的一個一個的比下去..1和2、1 和3、1和4...1和n
2.二分查找就是先和最中間的元素比較 大於此元素時將起始下標設置為此元素下表 繼續和右邊的中間元素比較，直到查找成功位置 相反小於則和左邊的比較（默認數組一從小到大排序完整）
3.哈希演算法是將任意長度的二進制值映射為固定長度的較小二進制值，這個小的二進哈希函數是一個數學方程式，它可用文本(如電子郵件信息)來生成稱為信息摘要的代碼。著名的哈希函數如：MD4，MD5，SHS。

❻ 常見查找和排序演算法

查找成功最多要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 比其它線性對數級別的排序演算法都要小。

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

❼ 請教：用JAVA編一個基本查找演算法效率比較的程序。

<script>
Array.prototype.swap = function(i, j)
{
var temp = this[i];
this[i] = this[j];
this[j] = temp;
}

Array.prototype.bubbleSort = function()
{
for (var i = this.length - 1; i > 0; --i)
{
for (var j = 0; j < i; ++j)
{
if (this[j] > this[j + 1]) this.swap(j, j + 1);
}
}
}

Array.prototype.selectionSort = function()
{
for (var i = 0; i < this.length; ++i)
{
var index = i;
for (var j = i + 1; j < this.length; ++j)
{
if (this[j] < this[index]) index = j;
}
this.swap(i, index);
}
}

Array.prototype.insertionSort = function()
{
for (var i = 1; i < this.length; ++i)
{
var j = i, value = this[i];
while (j > 0 && this[j - 1] > value)
{
this[j] = this[j - 1];
--j;
}
this[j] = value;
}
}

Array.prototype.shellSort = function()
{
for (var step = this.length >> 1; step > 0; step >>= 1)
{
for (var i = 0; i < step; ++i)
{
for (var j = i + step; j < this.length; j += step)
{
var k = j, value = this[j];
while (k >= step && this[k - step] > value)
{
this[k] = this[k - step];
k -= step;
}
this[k] = value;
}
}
}
}

Array.prototype.quickSort = function(s, e)
{
if (s == null) s = 0;
if (e == null) e = this.length - 1;
if (s >= e) return;
this.swap((s + e) >> 1, e);
var index = s - 1;
for (var i = s; i <= e; ++i)
{
if (this[i] <= this[e]) this.swap(i, ++index);
}
this.quickSort(s, index - 1);
this.quickSort(index + 1, e);
}

Array.prototype.stackQuickSort = function()
{
var stack = [0, this.length - 1];
while (stack.length > 0)
{
var e = stack.pop(), s = stack.pop();
if (s >= e) continue;
this.swap((s + e) >> 1, e);
var index = s - 1;
for (var i = s; i <= e; ++i)
{
if (this[i] <= this[e]) this.swap(i, ++index);
}
stack.push(s, index - 1, index + 1, e);
}
}

Array.prototype.mergeSort = function(s, e, b)
{
if (s == null) s = 0;
if (e == null) e = this.length - 1;
if (b == null) b = new Array(this.length);
if (s >= e) return;
var m = (s + e) >> 1;
this.mergeSort(s, m, b);
this.mergeSort(m + 1, e, b);
for (var i = s, j = s, k = m + 1; i <= e; ++i)
{
b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++];
}
for (var i = s; i <= e; ++i) this[i] = b[i];
}

Array.prototype.heapSort = function()
{
for (var i = 1; i < this.length; ++i)
{
for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1)
{
if (this[k] >= this[j]) break;
this.swap(j, k);
}
}
for (var i = this.length - 1; i > 0; --i)
{
this.swap(0, i);
for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1)
{
if (k == i || this[k] < this[k - 1]) --k;
if (this[k] <= this[j]) break;
this.swap(j, k);
}
}
}

function generate()
{
var max = parseInt(txtMax.value), count = parseInt(txtCount.value);
if (isNaN(max) || isNaN(count))
{
alert("個數和最大值必須是一個整數");
return;
}
var array = [];
for (var i = 0; i < count; ++i) array.push(Math.round(Math.random() * max));
txtInput.value = array.join("\n");
txtOutput.value = "";
}

function demo(type)
{
var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n");
for (var i = 0; i < array.length; ++i) array[i] = parseInt(array[i]);
var t1 = new Date();
eval("array." + type + "Sort()");
var t2 = new Date();
lblTime.innerText = t2.valueOf() - t1.valueOf();
txtOutput.value = array.join("\n");
}
</script>

<body onload=generate()>
<table style="width:100%;height:100%;font-size:12px;font-family:宋體">
<tr>
<td align=right>
<textarea id=txtInput readonly style="width:100px;height:100%"></textarea>
</td>
<td width=150 align=center>
隨機數個數<input id=txtCount value=500 style="width:50px"><br><br>
最大隨機數<input id=txtMax value=1000 style="width:50px"><br><br>
<button onclick=generate()>重新生成</button><br><br><br><br>
耗時(毫秒)：<label id=lblTime></label><br><br><br><br>
<button onclick=demo("bubble")>冒泡排序</button><br><br>
<button onclick=demo("selection")>選擇排序</button><br><br>
<button onclick=demo("insertion")>插入排序</button><br><br>
<button onclick=demo("shell")>謝爾排序</button><br><br>
<button onclick=demo("quick")>快速排序(遞歸)</button><br><br>
<button onclick=demo("stackQuick")>快速排序(堆棧)</button><br><br>
<button onclick=demo("merge")>歸並排序</button><br><br>
<button onclick=demo("heap")>堆排序</button><br><br>
</td>
<td align=left>
<textarea id=txtOutput readonly style="width:100px;height:100%"></textarea>
</td>
</tr>
</table>
</body>

這個代碼是放在DREAMWEAVER <head></head>標簽裡面

❽ 這樣的數據情況什麼查找演算法效率最高，或者是比較高

我能想到的比較合適的方法有2種。
1.計算每個事件的權值，按照權值排序，然後二分查找，排序的演算法復雜的為o(nlogn) ,查找為o(logn)，最多才1000個事件，對於計算機來說時間可以忽略不計。10W個事件都可以1秒出解的。至於權值的計算方法，設機號為i,路號為j,編號為 k,權值v=i*32*252+j*252+k;這樣就可以了，當然，權值的構造方法不止一種。空間需要開1000*int個
2.利用類似於trie樹（字典樹）的結構，不懂網路下，很簡單，很好用，構造樹的演算法復雜度為o(n),查找為o(1),極其霸道，會比第一種略浪費空間，最多需要32*32*252的BOOL型（實際上大多數情況下遠遠用不到），是第一種方法的128倍左右，但是我覺得還是很小的.利用動態的鏈表建樹，只需要1000*252的空間，時間和空間都很犀利。
樓主根據需要選擇吧，問題規模很小，高效的演算法的優勢體現的不明顯。

❾ 查找的計算機演算法

⒈順序查找的思想是：
將查找值順序逐個與結點值進行比較，相等即為查找成功，否則查找失敗.
程序如下：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
b:boolean;
place:integer;
procere search(r:arr;m,x:integer; var found:boolean;var p:integer);
begin
p:=1;found:=false;
while(p<=m) and not found do
if r[p]=x then found:=true else p:=p+1;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
search(a,n,x1,b,place);
if b then begin writeln('yes');writeln('Place of',x1:5,'is:',place); end
else writeln('no');
end. ⒈二分查找的基本思想：首先將結點按關鍵字排序，其次將查找值與中間位置的值比較，相等，查找成功；不等，則中間數據大於或小於查找值，無論怎樣查找將在一半的數據中查找。
⒉例：輸入序列數據查找指定值.
程序：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
place:integer;
procere paixv(var r:arr;m:integer);
var k,j,i,t:integer;
begin
k:=m;
while k>0 do
begin
j:=k-1;k:=0;
for i:=1 to j do
if r[i]>r[i+1] then
begin t:=r[i];a[i]:=r[i+1];r[i+1]:=t;k:=i;end;
end;
end;
procere search(r:arr;m,x:integer; var p:integer);
var low,high,mid:integer;
begin
p:=0;low:=1;high:=m;
while low<=high do
begin
mid:=(low+high) div 2;
if x>r[mid] then low:=mid+1 else
if x<r[mid] then high:=mid-1 else
begin p:=mid;exit;end;
end;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
paixv(a,n);
search(a,n,x1,place);
if place<>0 then writeln('yes') else writeln('no');
end. 因為二叉排序樹的左子樹若不為空則左子樹的所有結點的值均小於它的根結點的值，而右子樹若不為空，則右子樹的所有結點的值均不小大於它的根結點的值，根據這個性質查找演算法如下：
program pxtree;
const
a:array[1..8] of integer=（10,18,3,8,12,2,7,3）；
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i,x:integer;
procere maketr(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d>=w then maketr(d,right) else maketr(d,left);
end;
function searchtr(x:integer;p:point):boolean;
begin
if p=nil then searchtr:=false
else if x=p^.w then searchtr:=true
else if x<p^.w then searchtr:=searchtr(x,p^.left)
else searchtr:=searchtr(x,p^.right);
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do maketr(a[i],first);
write('want find data x:');read(x);
if searchtr(x,first) then writeln('yes') else writeln('No');
end. 以上講的查找方法基於比較的，查找效率依賴比較次數，其實理想的查找希望不經比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，這樣查找k時，只要根據這個對應關系f找到給定值k的像f(k）。這種對應關系f叫哈希（hash）函數。按這種思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存儲時容易沖突（collision）：即不同的關鍵字可以對應同一哈希地址。如何確定哈希函數和解決沖突是關鍵。
⒈哈希函數的構造方法
直接定址法：H(k)=k 或H(k)=a*k+b（線形函數）
如：人口數字統計表 地址 1 2 3 ... 100 年齡 1 2 3 ... 100 人數 67 3533 244 ... 4 數字分析法：取關鍵字的若干數位組成哈希地址
如：關鍵字如下：若哈希表長為100則可取中間兩位10進制數作為哈希地址。 81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537 平方取中法：關鍵字平方後取中間幾位數組成哈希地址
折疊法：將關鍵數字分割成位數相同的幾部分（最後一部分的位數可以不同）然後取幾部分的疊加和（捨去進位）作為哈希地址。
除留余數法：取關鍵字被某個不大於表長m的數p除後所得的余數為哈希地址。
H(k)=k mod p p<=m
隨機數法：H(k)=rondom(k）。
⒉處理沖突的方法
假設地址集為0..n-1，由關鍵字得到的哈希地址為j(0<=j<=n-1）的位置已存有記錄，處理沖突就是為該關鍵字的記錄找到另一個空的哈希地址。在處理中可能得到一個地址序列Hi i=1，2，...k
0<=Hi<=n-1），即在處理沖突時若得到的另一個哈希地址H1仍發生沖突，再求下一地址H2，若仍沖突，再求H3...。怎樣得到Hi呢？
開放定址法：Hi=(H(k)+di) mod m （H(k）為哈希函數；m為哈希表長；di為增量序列）
當di=1，2，3，... m-1 時叫線性探測再散列。
當di=1，-1，2，-2，3，-3，...,k,-k時叫二次探測再散列。
當di=random（m）時叫偽隨機探測序列。
例：長度為11的哈希表關鍵字分別為17，60，29，哈希函數為H(k)=k mod 11，第四個記錄的關鍵字為38，分別按上述方法添入哈希表的地址為8，4，3（隨機數=9）。
再哈希法：Hi=RHi(key) i=1,2,...,k，其中RHi均為不同的哈希函數。
鏈地址法：這種方法很象基數排序，相同的地址的關鍵字值均鏈入對應的鏈表中。
建立公益區法：另設一個溢出表，不管得到的哈希地址如何，一旦發生沖突，都填入溢出表。
⒊哈希表的查找
例：如下一組關鍵字按哈希函數H(k)=k mod 13和線性探測處理沖突所得的哈希表a[0..15]: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 01 68 27 55 19 20 84 79 23 11 10 當給定值k=84，則首先和a[6]比在依次和a[7],a[8]比結果a[8]=84查找成功。
當給定值k=38，則首先和a[12]比，再和a[13]比，由於a[13]沒有，查找不成功，表中不存在關鍵字等於38的記錄。 查找第k小元素即在n個元素中（未排序）找到第k小的元素。方法同快速排序，採用遞歸方式。
程序如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
b:arr;
i,k:integer;
function p(s,t:integer):integer;
var i,j,t1,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
p:=i;
end;
function find(s,t,k:integer):integer;
var p1,q:integer;
begin
if s=t then find:=b[s] else
begin
p1:=p(s,t);
q:=p1-s+1;
if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);
end;
end;
begin
write('input data:');
for i:=1 to n do read(b[i]);readln;
write('input k:');read(k);
write('output data:');
writeln('kthsmall:=',find（1,n,k));
end.

❿ 數據結構中，查找演算法最優的是哪一種

折半查找法的平均查找長度隨n增大而呈現對數增長趨勢，因此折半查找法為最優查找演算法