散列查找法時，有以下方式解決沖突：

開放地址法：

（1）線性探測法：將散列表假想成一個循環(huán)表，發(fā)生沖突時，從沖突地址的下一單元開始,順序查找空單元，如果到最后也沒有找到空單元，則回到表頭開始繼續(xù)查找，直到找到一個空位，就把此元素放入到此空位中，若找不到空位，則說明散列表已滿，需要進(jìn)行溢出處理。

（2）二次探測法：H(H(key)+di)%m? ? ?i=1,2,3,...,k(k<=m-1)

di=1^2,-1^2,2^2,-2^2,3^2,...,+k^2,-k^2(k<=m/2)

（3）偽隨機(jī)探測法：di=偽隨機(jī)數(shù)序列

鏈地址法：把具有同樣散列地址的記錄放在同一個鏈表中。有m個散列地址就有m個單鏈表。

接下來就直接放圖說話啦~

直接插入排序

（）中為已排好序的記錄的關(guān)鍵字

通過此過程發(fā)現(xiàn)，雖然黑色的49和綠色的49數(shù)值大小相等，且經(jīng)過一輪排序后，綠色的49仍然在黑色的49后面，所以這是一個穩(wěn)定排序。

【算法描述】

void InsertSort(SqList &L)

{

for(i=2;i<=L.length;++i)//從2開始

if(L.r[i].key<L.r[i-1].key)//小于即插入

{L.r[0]=L.r[i]; //將待插入的記錄暫存到監(jiān)視哨中

L.r[i]=L.r[i-1]; //r[i-1]后移

for(j=i-2;L.r[0].key<L.r[j].key;--j) //將哨兵位和“括號”里的比較，放在比自己小的數(shù)后面

?????L.r[j+1]=L.r[j];

L.r[j+1]=L.r[0];?

}

}

【算法分析】

（1）時間復(fù)雜度為O(n^2),空間復(fù)雜度為O(1)

（2）對存儲結(jié)構(gòu)沒有要求，適用于初始記錄基本有序，當(dāng)基本無序且n較大時，時間復(fù)雜度高，不宜采用。

折半插入排序：利用折半查找操作實現(xiàn)查找操作，再進(jìn)行插入排序

【算法描述】

void BInsertSort(SqList &L)

{

for(i=2;i<=L.length;++i)

{ L.r[0]=L.r[i];

?low=1;high=i-1;

while(low<=high)

{

? m=(low+high)/2;

?if(L.r[0].key<L.r[m].key)

? ?high=m-1;

else low=m+1;

}

for(j=i-1;j>=high+1;--j)?

L.[j+1]=L.[j]; //記錄后移

L.r[high+1]=L.r[0];

}

}

希爾排序：即為縮小增量排序，a[i]與a[i+di]比較,di為增量，每一輪比較完成后，di越來越小