[数据结构与算法]day50

1.比较分析各种查找算法.

顺序：逐个查找，将最后一个空值点设为哨兵，返回值为这点即为无查找值
折半：对应数学中的二分法，利用数组间的大小关系获得较快的查找速度
哈希表：根据数据值将其放在对应位置，可认为给了根据数据值特征的位置，但位置可能重复，则向后顺延，思想的话比较像以特征形容一个人（如生日），但若遇到下一个位置有同样特征（如一个班级有生日重复的人）则顺延一个标记位置

2.设计一个自己的 Hash 函数和一个冲突解决机制.

int tempPosition = paraKey % length;
? ? ? ? while (data[tempPosition] != null) {
? ? ? ? ? ? if (data[tempPosition].key == paraKey){
? ? ? ? ? ? ? ? return data[tempPosition].content;
? ? ? ? ? ? }//of if
? ? ? ? ? ? System.out.println("Not this one for " + paraKey);
? ? ? ? ? ? tempPosition = tempPosition % length + 1;
? ? ? ? }//of while

3.比较分析各种排序算法.

插入排序计算复杂度较高，由于每个点都逐个调换，其最高复杂度于数组原顺序关系较大。

希尔排序在插入排序的复杂度基础上较低，使得有较大跳跃的情况能够调换较快。但是因为要预估较差情况，其复杂度只能预估于插入排序在同一数量级。

冒泡排序的复杂度被浮泡必定确定一个值所限制，最大复杂度也就是循环n次。

快速排序：在冒泡排序基础上减小计算复杂度

堆排序利用的完全二叉树的深度较低的特点，降低了复杂度。

归并排序在使用中其实没有分这个阶段，仅需要不断两两比较即可

4.描述各种排序算法的特点和基本思想.

插入排序：逐个将不符合顺序的向左调换，直到左边顺序正确，再向右计算下一点。

希尔排序：在插入排序基础上跳跃间隔概念，使得差距较大的数字能较快调动而非逐个比较，再逐步缩小间隔使得位置精确。

冒泡排序：逐个比较，将较大值向右浮，每次for i至少确定一个位置的值。

快速排序：在冒泡排序的基础上加上阈值，将数据分别从两侧筛选小于阈值和大于阈值的数据，若出现分区错误情况则先卡在这个位置，计算另一侧，直到另一侧也被卡住，将两侧数据交换，再继续挪动挡板。需要用到四重循环。

堆排序：将数字根据顺位放在二叉树结构中，调整二叉树使得父节点大于其所有子节点，完成调整成为一个父节点最大的最大堆后，将这个父节点放到最后一个位置。在接下来的筛选中删去最后一个位置，筛选出次大值，重复前序操作，放在现在的最后位置，筛选完所有点后，现在的二叉树为根据顺位排序的有序结构

归并排序：将数组拆开各点放在各个位置，再两两比较成序，最后分为两组序数，逐个比较大小放进最后的序列中