文章目录
- 说明
- day50 小结
- 1.比较分析各种查找算法.
- 2.比较分析各种排序算法
- 3.描述各种排序算法的特点和基本思想
- 4.设计一个自己的 Hash 函数和一个冲突解决机制
说明
闵老师的文章链接： 日撸 Java 三百行（总述）_minfanphd的博客-CSDN博客
自己也把手敲的代码放在了github上维护：https://github.com/fulisha-ok/sampledata
day50 小结
1.比较分析各种查找算法.
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 |
|---|---|---|---|
| 顺序查找 | O(n) | O(n) | O(1) |
| 折半查找 | O(log2n) | O(log2n) | O(log2n) |
| 哈希表法 | O(1) | O(1) | O(1) |
- 顺序查找，比较简单，从数据第一个元素开始逐个比对。再排序中引入了“哨兵”的概念，哨兵可以避免进行不必要的判断。
- 折半查找相比顺序查找快了一点，它是基于分治思想的查找算法。折半查找可以对比二叉排序树，但使用折半查找是要求给出的数据必须是有序的。我觉得可以结合排序算法来使用这个折半查找算法
- 哈希算法比前面两种查找都快，因为是通过函数映射的，当需要查找一个元素时，只需要通过哈希函数计算出它的索引位置，然后在该位置上查找即可，但是关键就是映射函数如何设计和如何处理冲突。哈希表的时间复杂度取决于哈希函数的效率和哈希表的装填因子（我上面写的时间复杂度是再比较理想的情况下：哈希函数的效率高、装填因子低时），如果哈希函数效率低，装填因子高就另说了。
2.比较分析各种排序算法
| 类型 | 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|---|
| 插入排序 | 直接插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(nlog2n) | O(n2) | O(n1.3) | O(1) | 不稳定 | |
| 交换排序 | 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(nlog2n) | 不稳定 | |
| 选择排序 | 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | |
| 归并排序 | 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
- 在实现排序算法的过程种，要注意数组存储的起始索引值是从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);
}
}
