数据结构之查找和排序

文章目录1.查找1.1 线性表查找1.2 查找树1.2.1 二叉查找/搜索/排序树 BST1.2.2 平衡二叉树1.2.3 红黑树1.2.4 B树(平衡树)1.2.5 B树1.2.6 B*树1.3 哈希表查找1.3.1 哈希表的结构和特点1.3.2 哈希表是如何添加数据的1.3.3 哈希表是如何查询数据的1.3.4 hashCode和equals的作用1.3.5 各种类型数据的哈希码如何获取1.查找1.1 线性表查找1顺序查找publicclassSearchDemo1{publicstaticvoidmain(String[]args){// 给定分数数组int[]scoreArr{89,45,78,45,100,98,86,100,65};// 给定要查找的分数intscore100;// 完成查找intindex-1;for(inti0;iscoreArr.length;i){if(scoreArr[i]score){indexi;break;}}// 输出结果if(index-1){System.out.println(该分数不存在);}else{System.out.println(score的索引是index);}}}2折半查找顺序结构、按照关键字有序①非递归publicclassSearchDemo2{publicstaticvoidmain(String[]args){// 给定数组int[]arr{1,2,3,4,5,6,7,8,9,10};//给定要查找的值intkey9;// 进行折半二分查找intindexbinarySearch(arr,key);// 输出结果if(index-1){System.out.println(该分数不存在);}else{System.out.println(key的索引是index);}}// 不使用递归publicstaticintbinarySearch(int[]array,intkey){// 指定low和highintlow0;inthigharray.length-1;// 折半查找while(lowhigh){// 求midintmid(lowhigh)/2;// 判断是否等于if(keyarray[mid]){returnmid;}elseif(keyarray[mid]){highmid-1;}else{lowmid1;}}return-1;}}②递归publicclassSearchDemo3{publicstaticvoidmain(String[]args){// 给定数组int[]arr{1,2,3,4,5,6,7,8,9,10};//给定要查找的值intkey10;// 进行折半二分查找intindexbinarySearch(arr,key);// 输出结果if(index-1){System.out.println(该分数不存在);}else{System.out.println(key的索引是index);}}// 使用递归publicstaticintbinarySearch(int[]array,intkey){//指定low和highintlow0;inthigharray.length-1;returnbinarySearch(array,key,low,high);}publicstaticintbinarySearch(int[]array,intkey,intlow,inthigh){// 递归结束的条件if(lowhigh){return-1;}intmid(lowhigh)/2;if(keyarray[mid]){returnmid;}elseif(keyarray[mid]){returnbinarySearch(array,key,low,mid-1);}else{returnbinarySearch(array,key,mid1,high);}}}1.2 查找树1.2.1 二叉查找/搜索/排序树 BST1或者是一棵空树2或者是具有下列性质的二叉树①若它的左子树不为空则左子树上所有结点的值均小于它的根结点的值②若它的右子树上所有结点的值均大于它的根结点的值③它的左、右子树也分别为二叉排序树注意对二叉查找树进行中序遍历得到有序集合1.2.2 平衡二叉树自平衡二叉查找树又被称为AVL树(有别于AVL算法)1它是一棵空树2或它的左右两个子树的高度差(平衡因子)的绝对值不超过1并且左右两个子树都是一棵平衡二叉树同时平衡二叉树必定是二叉搜索树反之则不一定①平衡因子结点的平衡因子是结点的左子树的高度减去右子树的高度②平衡二叉树每个结点的平衡因子都为1、-1、0的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树。3二叉树的目的是为了减少二叉查找树层次提高查找速度平衡二叉树的常用实现方法有AVL、红黑树、替罪羊树、Treap、伸展树等。1.2.3 红黑树R-B Tree,全称是Red-Black Tree,又称为“红黑树”它是一种平衡二叉树。红黑树的每个结点上都有存储位表示结点的颜色可以是红或黑。红黑树的特性1每个结点或者是黑色或者是红色。2根结点是黑色3每个叶子结点是黑色(注意:这里叶子结点是指为空的叶子结点)4如果一个结点是红色则它的子节点必须是黑色的。5从一个结点到该结点的子孙结点的所有路径上包含相同数目的黑结点。红黑树的应用比较广泛主要用它来存储有序的数据它的时间复杂度是O(logN),效率非常高。例如Java集合中的TreeSet和TreeMap1.2.4 B树(平衡树)1.2.5 B树1所有的数据都在最下面一层2在B-树(即B树)基础上为叶子结点增加链表指针所有关键字都在叶子结点中出现非叶子结点作为叶子结点的索引B树总是到叶子结点才命中。1.2.6 B*树1.3 哈希表查找1.3.1 哈希表的结构和特点1hash table(哈希表) 也叫散列表2特点快3结构有多种最流行、最容易理解的是顺序表(主结构)链表4主结构顺序表5每个顺序表的结点再单独引出一个链表1.3.2 哈希表是如何添加数据的1计算哈希码(调用hashCode(),结果是一个int值整数的哈希码取自身即可)2计算在哈希表中的存储位置根据hashcode计算出hash值hashcode是一个整数我们需要将它转化成[0, 数组长度-1]的范围。我们要求转化后的hash值尽量均匀地分布在[0,数组长度-1]这个区间减少“hash冲突”① 一种极端简单和低下的算法是hash值 hashcode/hashcode;也就是说hash值总是1。意味着键值对对象都会存储到数组索引1位置这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”HashMap也退化成了一个“链表”。②一种简单和常用的算法是(相除取余算法)hash值 hashcode%数组长度这种算法可以让hash值均匀的分布在[0,数组长度-1]的区间。 早期的HashTable就是采用这种算法。但是这种算法由于使用了“除法”效率低下。JDK后来改进了算法。首先约定数组长度必须为2的整数幂这样采用位运算即可实现取余的效果hash值 hashcode(数组长度-1)。3存入哈希表情况一一次添加成功情况二多次添加成功(出现了冲突[哈希表的存储位置相同]调用equals()和对应链表的元素进行比较,比较到最后结果都是false创建新节点存储数据并加入链表末尾)情况三不添加出现了冲突调用equals()和对应链表的元素进行比较经过一次或者多次比较后结果都是true表明重复不添加结论一哈希表添加数据快(3步即可不考虑冲突)结论二唯一结论三无序1.3.3 哈希表是如何查询数据的和添加数据的过程是相同的结论一哈希表查询数据快结论二哈希表删除数据快结论三哈希表更新数据快(如果更新后影响到哈希码值就比较麻烦了要删除再添加了)1.3.4 hashCode和equals的作用1hashCode()用于计算哈希码是一个整数根据哈希码可以计算出数据在哈希表中的存储位置。2equals()添加时出现了冲突需要通过equals进行比较判断是否相同查询也需要使用equals进行比较判断是否相等1.3.5 各种类型数据的哈希码如何获取1Integer// int就是取自身publicstaticinthashCode(intvalue){returnvalue;}2DoublepublicstaticinthashCode(doublevalue){longbitsdoubleToLongBits(value);return(int)(bits^(bits32));}3StringpublicinthashCode(){inthhash;if(h0value.length0){charval[]value;for(inti0;ivalue.length;i){h31*hval[i];}hashh;}returnh;}