DS冲刺整理做题定理（四）查找与排序

????????最后一期更新，考试之前应该不会再出该专题了，之后有时间会出一些有关链表的代码题，其他章节只挑选重点的总结~

---

一.查找

1.顺序查找

????????又被称为线性查找，对顺序表和链表都使用~基本思想是从某一端开始，逐个检查关键字是否满足给定的条件~

2.折半查找

????????适用于有序的顺序表：首先将给定值key与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置，若不等，则所需查找的元素只能在中间元素以外的前半不分或者后半部分，然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止?

3.分块查找

????????分块查找又称为索引顺序查找，将查找表分为若干个小的子块，块内元素可以无序，但块之间是有序的~即将查找的过程分为两步：第一步是在索引表猴子那个确定待查记录所在的块，第二步则是在快内顺序查找~

4.二叉排序树（BST）

? ? ? ? 又被称为二叉查找树，若左子树非空，则左子树上所有的结点的值均小于根节点的值，而右子树则均大于，这样在查找节点时可以达到类似分块查找的效果~

5.平衡二叉树

? ? ? ? AVL树，为了防止树的高度增长过快而降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左右子树高度差的绝对值不超过1，将这样的二叉排序树称为平衡二叉树，简称平衡树~

6.散列表

• 散列函数：将查找表中的关键字映射成该关键字对应位置地址的函数
• 散列冲突：将2个或更多的关键字映射再同一地址
• 哈希函数的种类：直接定址、除留取余、数字分析、平方取中
• 处理冲突的方法：开放定址、拉链法（链接到同一个位置上的链表）
• 要会计算平均查找长度ASL~

二.排序

1.插入排序

• 直接插入：将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
• 折半插入：先折半查找出元素待插入的位置，再统一地一定待插入位置之后的所有元素
• 希尔排序：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

2.交换排序

• 冒泡排序：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
• 快速排序：快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

3.选择排序

• 简单选择：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
• 堆排序：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

4.归并排序

????????将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

5.基数排序

????????它是通过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

6.外部排序

• 多路归并排序：多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k（不是重点~）

7.对比~