数据结构学习小记8（查找+排序1）

散列查找法时，有以下方式解决冲突：

开放地址法：

（1）线性探测法：将散列表假想成一个循环表，发生冲突时，从冲突地址的下一单元开始,顺序查找空单元，如果到最后也没有找到空单元，则回到表头开始继续查找，直到找到一个空位，就把此元素放入到此空位中，若找不到空位，则说明散列表已满，需要进行溢出处理。

（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）伪随机探测法：di=伪随机数序列

链地址法：把具有同样散列地址的记录放在同一个链表中。有m个散列地址就有m个单链表。

接下来就直接放图说话啦~

直接插入排序

（）中为已排好序的记录的关键字

通过此过程发现，虽然黑色的49和绿色的49数值大小相等，且经过一轮排序后，绿色的49仍然在黑色的49后面，所以这是一个稳定排序。

【算法描述】

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]; //将待插入的记录暂存到监视哨中

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

for(j=i-2;L.r[0].key<L.r[j].key;--j) //将哨兵位和“括号”里的比较，放在比自己小的数后面

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

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

}

}

【算法分析】

（1）时间复杂度为O(n^2),空间复杂度为O(1)

（2）对存储结构没有要求，适用于初始记录基本有序，当基本无序且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越来越小