说明

闵老师的文章链接： 日撸 Java 三百行（总述）_minfanphd的博客-CSDN博客
自己也把手敲的代码放在了github上维护：https://github.com/fulisha-ok/sampledata

day50 小结

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

• 顺序查找，比较简单，从数据第一个元素开始逐个比对。再排序中引入了“哨兵”的概念，哨兵可以避免进行不必要的判断。
• 折半查找相比顺序查找快了一点，它是基于分治思想的查找算法。折半查找可以对比二叉排序树，但使用折半查找是要求给出的数据必须是有序的。我觉得可以结合排序算法来使用这个折半查找算法
• 哈希算法比前面两种查找都快，因为是通过函数映射的，当需要查找一个元素时，只需要通过哈希函数计算出它的索引位置，然后在该位置上查找即可，但是关键就是映射函数如何设计和如何处理冲突。哈希表的时间复杂度取决于哈希函数的效率和哈希表的装填因子（我上面写的时间复杂度是再比较理想的情况下：哈希函数的效率高、装填因子低时），如果哈希函数效率低，装填因子高就另说了。

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

• 在实现排序算法的过程种，要注意数组存储的起始索引值是从0还是1开始
• 不同类型的排序实现方式是不同的，交换类和选择类排序在每一趟排序后都会确定一个数据的最终位置

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

• 直接插入排序
  每一趟排序，把待排序数据插入到已排好序的数据中，在这个过程中就需要比较数据（待排序数据和已排好序数据进行比较）找到合适的插入位置，并移动数据。虽然直接插入排序在的时间复杂度比较高，但数据量小的时候，它排序算法也挺高的，而且他不需要额外的存储空间，算法也比较稳定。

• 希尔排序
  希尔排序是插入排序的改进，当数据基本有序时用插入排序是较优的，希尔排序每一趟排序则是按一个步长分组进行插入排序(这样移动数据的次数减少了)，每一趟排序后数据都逐渐有序，当最后步长为1时，则和插入排序一样，但是这时的数据基本有序。但希尔排序对步长的选择很关键，这会影响他时间复杂度。

• 冒泡排序
  冒泡排序，就是把最大（最小）的数据往“上”冒，冒得过程则是和相邻元素两两比较，根据排序规则进行交换数据。在待排序数据较大的情况下，冒泡排序应该不是首选，他的平均时间复杂度比较高。

• 快速排序
  快速排序也需要比较数据，但不是和冒泡排序一样相邻元素两两比较，而是和一个基准值比较，并且是从数据两边交替比较，根据排序规则进行交换数据。在确定一个数据位置就会有左右之分，左右又可以采用通样的方法（递归）。相比于其他排序算法，快速排序是一种高效的排序算法，在大规模数据时，快速排序是一个不错的选择。

• 选择排序
  在未排序数据中找到最大(最小)元素，将数据依次放到已排序数据后（前）。这个过程中要去比较数据找到数据。选择排序的时间复杂度与数据的大小和数据分布无关，所以选择排序的性能不怎么样。所以数据量大的时候不是首选

• 堆排序
  堆排序借助大(小)顶堆的特点，大（小）顶堆又和完全二叉树很相似，所以堆排序和树有关，重点是要建堆和调整堆。

• 归并排序
  归并排序（基于分治思想）将待排序数据进行分组，如二路归并，将两个有序序列归并为一个有序序列。

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

我设计的Hash函数采用的是直接寻址法，而解决冲突的办法是拉链法。在设计Hash函数时，我设计的思路参考了图中的领接表，我认为他的数据结构和这个拉链法很相似，由数组加链表结合。如下是自己写的代码并通过测试：

package datastructure.search;

/**
 * @author： fulisha
 * @date： 2023/5/12 13:51
 * @description：
 */
public class Hash {
    //链表的结构
    class HashNode {
        int column;
        HashNode next;
        public HashNode(int paraColumn) {
            column = paraColumn;
            next = null;
        }
    }

    int length;
    HashNode[] data;

    public Hash(int[] paraArray,int paraLenght) {
        length = paraLenght;
        data = new HashNode[paraLenght];
        HashNode tempNode,tempPreviousNode;
        int tempPosition;

        //采用直接地址法构造hash函数 并用拉链法解决冲突
        for (int i = 0; i < paraLenght; i++) {
            data[i] = new HashNode(i);
            tempPreviousNode = data[i];
            for (int j = 0; j < paraArray.length; j++) {
                tempPosition = paraArray[j] % paraLenght;
                //，我对取模值相同的在外层一个for一次搞定
                if (tempPosition == i) {
                    tempNode = new HashNode(paraArray[j]);
                    tempPreviousNode.next = tempNode;
                    tempPreviousNode = tempNode;
                }
            }
        }

        //打印输出链表法的值
        HashNode hashNode;
        for (int i = 0; i < paraLenght; i++) {
            hashNode = data[i];
            String hashString = " ";
            while (hashNode != null) {
                hashString = hashString + " " + hashNode.column ;
                hashNode = hashNode.next;
            }
            System.out.println(hashString);
        }
    }

    public static void main(String args[]) {
        int[] tempUnsortedKeys = { 16, 33, 38, 69, 57, 95, 86 };
        Hash hash = new Hash(tempUnsortedKeys, 8);
    }

}