排序与查找

 一、排序 排序是将一个数据元素的任意序列重新排列成一个关键字有序的序列。 分类：外部排序、内部排序(内部排序：排序发生在随机存储器内部，外部排序：排序需要访问外部存储器)； 稳定性：如果同样键值的记录在重新排序后次序没有发生改变，则这种排序是稳定的，否则称为不稳定的。 排序方式：修改存储值记录，链表排序(改变链表指针)，地址排序 插入排序: --直接插入排序：从前至后进行比较插入 --折半插入排序：折半查找插入位置 --2-路插入排序：折半的改变方式，需要额外n的空间 --表插入排序：采用数组下标实现链表的方式 --希尔排序/缩小增量排序：分治？分成子序列进行排序，增量因子除了1之外没有其它公因子，最后一个增量必须为1； 交换排序/快速排序 --起泡排序/沉底：两两比较，每轮最大到最后； --快速排序：递归方式，选取支点(枢轴)，比其小的放之前，大的放其后，然后再对枢轴分出的两个序列进行排序，递归完成； 选择排序 --简单选择排序； --树形选择排序/锦标赛排序：空间大.....； --堆排序：改进的树排序； 归并排序 --将两个或者两个以上的有序表合并成一个有序表的过程，相对于堆排序，归并排序为稳定的排序方式； 计数排序：比较大小计数进行排序的方式； 基数排序 --借助多个关键字思想对单逻辑关键字进行排序的方法； --主关键字/次关键字，对应不同的方法：MSD(most significant Digit first)/LSD(least significant Digit first)--最高位优先/最低位优先； --链式基数分配：分配+收集的方式，按照不同关键字或最高位/最低位优先的方式进行分配，而后进行排序收集； 排序方式的时空比较 依次为： 平均时间 最坏情况 辅助存储 简单排序: O(n^2) O(n^2) O(1) 快速排序: O(nlogn) O(n^2) O(logn) 堆排序:  O(nlogn) O(nlogn) O(1) 归并排序: O(nlogn) O(nlogn) O(n) 基数排序: O(d(n+rd)) O(d(n+rd)) O(rd) 二、查找 查找表：由同一类型的数据元素(或记录)构成的集合。只有查询、读取操作的查找表叫做静态查找表，若还带有删除和修改操作则称为动态查找表。动态查找表可以是在查找过程中动态生成的。 关键字：可以用来设别一组的记录的某一数据项的值；可以唯一标识的叫主关键字，识别多个元素的叫次关键字。 静态查找表 无序表查找 --顺序查找 有序表查找 --折半查找：利用二分法计算索引； --斐波那契查找：采用斐波那契计算索引 --插值查找/线性计算索引判断 静态树表的查找 -- 有序树查找 索引顺序表查找 --简单讲：构造关键字和地址的索引表，利用索引表限制索引范围进行查找的过程。 动态查找表 --二叉排序树/平衡二叉树；决策树？ --B-B+树：多路树，文件系统？； //B树，在B树中所有的数据记录或记录的键，都是按照键的增序存储在叶子中；//索引表构成的树；B树可以用作索引； --键树：结点带有关键字的符号，而非主次关键字； 哈希表 哈希表(散列)：基于哈希函数构造的表; 哈希函数：期望不时通过比较，而是直接通过关键的得到存储地址而构造的函数；基于哈希函数得到的存储地址称为 哈希地址或散列地址。 哈希函数的构造方法： 1、直接定位法 --使用线性函数或是关键字自身； 2、数字分析法 --从具体数据中找到可以区分的相应位进行映射； 3、平方取中法 --取关键字平方后中间几位； 4、折叠法 --将关键字分割成相同的位数求和； 5、除留余数法 --关键字对某数取模，或者平方取中/折叠后取模； 6、随机数法 --以关键字为入参的随机函数； 处理冲突的方法 1、开放定址法 --在得到的哈希地址冲突时，求下一地址，直到找到下一不冲突的地址； Hi = (H(key)+di) mod m i=1,2,...,k(k<=m-1)； //--di = 1，2，3...称线性探测再散列 //--di = 1^2,-1^2,2^2,-2^2... 二次探测再散列 //--di = 伪随机数，随机探测再散列 2、再哈希法 --发生冲突时，采用另外hash函数,增加额外时间； 3、链地址法 --哈希地址相同的元素放入同一链表中； 4、建立一个公共溢出区法 --设立溢出表，当关键字和哈希基本表中的关键字冲突时，不管哈希地址是什么，都放入溢出表；