文章目录
查找
查找-平均查找长度
顺序查找算法及分析
折半查找算法及分析
分块查找
Hash表
Hash 冲突
常见Hash函数
冲突处理方法
Hash表的实现
Hash表的创建
Hash表的插入
Hash表的查找
排序
相关概念
插入排序
交换排序
快速排序
写在最后
查找
设记录表L=(R1 R2……Rn)，其中Ri(l≤i≤n)为记录，对给定的某个值k，在表L中确定key=k的记录的过程，称为查找。
若表L中存在一个记录Ri的key=k，记为Ri.key=k，则查找成功，返回该记录在表L中的序号i(或Ri 的地址)，否则(查找失败)返回0(或空地址Null)。
查找方法有顺序查找、折半查找、分块查找、Hash表查找等等。查找算法的优劣将影响到计算机的使用效率，应根据应用场合选择相应的查找算法。
查找-平均查找长度
对查找算法，主要分析其T(n)。查找过程是key的比较过程，时间主要耗费在各记录的key与给定k值的比较上。比较次数越多，算法效率越差（即T(n)量级越高），故用“比较次数”刻画算法的T(n)。
一般以“平均查找长度”来衡量T(n)。
平均查找长度ASL（Average Search Length）：对给定k，查找表L中记录比较次数的期望值(或平均值)，即：
顺序查找算法及分析
算法思路 设给定值为k，在表(R1 R2……Rn)中，从Rn开始，查找key=k的记录。
int sqsearch(sqlist r, keytype k) { int i; r.data[0].key = k; //k存入监视哨// i = r.len; //取表长// while(r.data[i].key != k) i--; return (i); }
故ASL = O(n)。而查找失败时，查找次数等于n+l，同样为O(n)。
对查找算法，若ASL=O(n)，则效率是很低的，意味着查找某记录几乎要扫描整个表，当表长n很大时，会令人无法忍受。
折半查找算法及分析
算法思路
对给定值k，逐步确定待查记录所在区间，每次将搜索空间减少一半(折半)，直到查找成功或失败为止。
设两个游标low、high，分别指向当前待查找表的上界(表头)和下界(表尾)。mid指向中间元素。
时间复杂度类似于一颗查找树，所以是O(logn)
分块查找
设记录表长为n，将表的n个记录分成b=⌈ n / s ⌉ \lceil n/s \rceil⌈n/s⌉个块，每块s个记录（最后一块记录数可以少于s个），即：
且表分块有序，即第i（1≤i≤b-1）块所有记录的key小于第i+1块中记录的key，但块内记录可以
无序。
分块查找(索引顺序查找）
分块索引查找分两步进行：
1.由索引表确定待查找记录所在的块；
2.在块内顺序查找。
Hash表
理想的查找方法是：对给定的k，不经任何比较便能获取所需的记录，其查找的时间复杂度为常数级O©。
这就要求在建立记录表的时候，确定记录的key与其存储地址之间的关系f，即使key与记录的存放地址H相对应：k e y ⟶ f H : 记 录 key \stackrel{f}{\longrightarrow} H:记录key
⟶
f
H:记录
当要查找key=k的记录时，通过关系f就可得到相应记录的地址而获取记录，从而免去了key的比较过程。
这个关系f就是所谓的Hash函数（或称散列函数、杂凑函数），记为H(key)。
它实际上是一个地址映象函数，其自变量为记录的key，函数值为记录的存储地址（或称Hash地址）。
Hash 冲突
不同的key可能得到同一个Hash地址，即当keyl≠key2时，可能有H(key1)=H(key2)，此时称key1和key2为同义词。这种现象称为“冲突”或“碰撞”，因为一个数据单位只可存放一条记录。
一般，选取Hash函数只能做到使冲突尽可能少，却不能完全避免。这就要求在出现冲突之后，寻求适当的方法来解决冲突记录的存放问题
常见Hash函数
选取（或构造）Hash函数的方法很多，原则是尽可能将记录均匀分布，以减少冲突现象的发生。以下介绍几种常用的构造方法。
直接地址法
平方取中法
叠加法
保留除数法
随机函数法
其中最常见的是保留除数法：
又称质数除余法，设Hash表空间长度为m，选取一个不大于m的最大质数p，令： H ( k e y ) = k e y H(key)=key%pH(key)=key
一般选取除数为质数可以得到相对较好的散列效果
冲突处理方法
冲突是指：表中某地址j∈[0，m-1]中己存放有记录，而另一个记录的H(key)值也为j。
处理冲突的方法一般为：在地址j的前面或后面找一个空闲单元存放冲突的记录，或将相冲突的诸记录拉成链表。
在处理冲突的过程中，可能发生一连串的冲突现象，即可能得到一个地址序列H1、H2……Hn，Hi∈[0，m-l]。H1是冲突时选取的下一地址，而H1中可能己有记录，又设法得到下一地址H2……直到某个Hn不发生冲突为止。这种现象称为聚积，它严重影响了Hash表的查找效率。
还有一个因素是表的装填因子α，α=n/m，其中m为表长，n为表中记录个数。一般α在0.7～0.8之间，使表保持一定的空闲余量，以减少冲突和聚积现象。
开放地址法
当发生冲突时，在H(key)的前后找一个空闲单元来存放冲突的记录，即在H(key)的基础上获取下一地址：
di为地址增量,m为表长。di的取法有多种：
di=1，2，3，……(m-1)——称为线性探查法；
di=12，-12，22，-22，……——称为二次探查法。
链地址法
生冲突时，将各冲突记录链在一起，即同义词的记录存于同一链表。
链地址法解决冲突的优点：无聚积现象；删除表中记录容易实现。
应用广泛
Hash表的实现
H(key)=key
Hash表的创建
hash *hash_create(){ hash * HT; if((HT = (hash *) malloc (sizeof(hash))) == NULL){ printf("malloc failed\n"); return NULL; } memset(HT,0, sizeof(hash)); return HT; }
Hash表的插入
int hash_insert(hash *HT, datatype key){ linklist p, q; if(HT == NULL){ printf("HT is NULL\n"); return -1; } if((p = (linklist)malloc(sizeof(listnode))) == NULL){ printf("malloc failed\n"); return -1; } p->key = key; p->value = key % N; p->next = NULL; q = &HT->data[key % N]; while (q->next && q->next->key < p->key){ q = q->next; } p->next = q->next; q->next = p; return 0; }
Hash表的查找
linklist hash_search(hash *HT, datatype key){ linklist p; if(HT == NULL){ printf("HT is NULL\n"); return NULL; } p = &HT->data[key % N]; while(p->next && p->next->key != key){ p = p->next; } if( p->next == NULL) return NULL; else return p->next; }
排序
相关概念
稳定排序和非稳定排序
若在排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称这种排序是稳定的，其含义是它没有破坏原本已有序的次序。
内排序和外排序
若待排文件f在计算机的内存储器中，且排序过程也在内存中进行，称这种排序为内排序。
若排序中的文件存入外存储器，排序过程借助于内外存数据交换（或归并）来完成，则称这种排序为外排序。
内排序的方法：
插入排序
交换排序
选择排序
归并排序
插入排序
直接插入排序
折半插入排序
链表插入排序
Shell（希尔）排序
直接插入排序
排序方法
先将文件中的（R1）看成只含一个记录的有序子文件，然后从R2起，逐个将R2至Rn按key插入到当前有序子文件中，最后得到一个有序的文件。插入的过程上是一个key的比较过程，即每插入一个记录时，将其key与当前有序子表中的key进行比较，找到待插入记录的位置后，将其插入即可。
时间复杂度T(n)=O(n2)
折半插入排序
先将（R[1]）看成一个子文件，然后依次插入R[2]……R[n]。但在插入R[i]时，子表[R[1]……R[i-1]]已是有序的，查找R[i]在子表中的位置可按折半查找方法进行，从而降低key的比较次数。
其实就是查找的时候采用折半查找罢了
链表插入排序
交换排序
“起泡”排序（Bubble Sort）
“快速”排序（Quick Sort）
快速排序
设记录的key集合k={50，36，66，76，36，12，25，95}，每次以集合中第一个key为基准的快速排序。
#include <stdio.h> #include <stdlib.h> #define N 15 int quick_sort(int *data, int low, int high); int partion(int *data, int low, int high); int main(int argc, const char * argv[]){ int data[N] = {0}; int i; srandom(10); for(i = 0;i < N; i ++){ data[i] = random() % 100; } for(i = 0;i < N; i ++){ printf("%d ", data[i]); } puts(""); quick_sort(data, 0, N-1); for(i = 0;i < N; i ++){ printf("%d ", data[i]); } puts(""); return 0; } int partion(int *data, int low, int high){ int temp = data[low]; while(low < high){ while(low < high && temp <= data[high]) high--; data[low] = data[high]; while(low < high && temp >= data[low]) low++; data[high] = data[low]; } data[low] = temp; return low; } int quick_sort(int *data, int low, int high){ int t; if(data == NULL) return -1; if ( low >= high) return 0; t = partion(data, low, high); quick_sort(data, low, t-1); quick_sort(data, t+1, high); return 0; }
写在最后
数据结构完结了！！！！但是我感觉这个专题最后俩写的太垃圾了，我尽量更新算法笔记，回头我放参考链接，我尽量一天一更，大家和我一起变强呀！明天开始文件IO，，最后三连即可提高学习效率！！！
另外我在更新的就是算法笔记的一些例题笔记，这个系列是用于提高我的算法能力，如果有兴趣对算法领域感兴趣找不到合适的入门文章也可以追更，如果我更新的太慢了请大家点赞收藏，一键三连才能更有更新的动力呀0.0
