Java 查找算法

* 二分查找又称折半查找，它是一种效率较高的查找方法。 【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。 * @author wzj public class BinarySearch { public static void main(String[] args) { int[] src = new int[] {1, 3, 5, 7, 8, 9}; System.out.println(binarySearch(src, 3)); System.out.println(binarySearch(src,3,0,src.length-1)); * * 二分查找算法 * * * @param srcArray * 有序数组 * * @param des * 查找元素 * * @return des的数组下标，没找到返回-1 public static int binarySearch(int[] srcArray, int des){ int low = 0; int high = srcArray.length-1; while(low = high) { int middle = (low + high)/2; if(des == srcArray[middle]) { return middle; }else if(des srcArray[middle]) { high = middle - 1; }else { low = middle + 1; return -1; /** *二分查找特定整数在整型数组中的位置(递归) *@paramdataset *@paramdata *@parambeginIndex *@paramendIndex *@returnindex public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){ int midIndex = (beginIndex+endIndex)/2; if(data dataset[beginIndex]||data dataset[endIndex]||beginIndex endIndex){ return -1; if(data dataset[midIndex]){ return binarySearch(dataset,data,beginIndex,midIndex-1); }else if(data dataset[midIndex]){ return binarySearch(dataset,data,midIndex+1,endIndex); }else { return midIndex; }

但是插入因为会涉及当前节点后的所有值得移动，一次，其时间复杂度为O(n) + O(log n)

只能从头节点遍历， 查找的复杂度是O（n）
插入或者是删除，因为只需要移动指针，时间复杂度为O（1） + O（n）

插入的复杂度本身并不高，只是简单的节点添加。但是因为寻找插入位置的查找操作的复杂度跟树的高度相关为logn，极差的情况下可能接近于线性查找。

平衡二叉树是尽量减少数高的二叉树，其算法中增加了左旋和右旋的操作。插入复杂度会高一些，但是会得到不错的查找性能。

学习自这里
这个就要说一下上面说的跟磁盘I/O相关的，因此为了减少磁盘I/O。可以利用磁盘的预读特性，一次提取大概相当于一页大小的节点到内存中。
先要说一下B-Tree.
一个平衡的m-way查找数，其要满足如下的条件：

子数节点要完全大于、小于、或者在其之间。 也就是不能越过父节点的两个值 叶子节点中的值的个数 =m/2 非叶子节点中的值的个数=子节点个数-1
如下图：

可以看出，三个子节点的有两个值，三个子节点中的数据分别对应了小于、之间、大于这个范围

B+Tree
与上面的差别是：

父节点存储的都是到子节点的指针 会有两个入口，一个是根节点，另外一个是从最小叶子节点开始的指针

查找跟二叉树比较像，因为插入的时候已经是相当于二分算法了，所以只需要，递归找到就可以了。

Hash表

为了解决一些不容易排序，或者查找的对象。 比如图像，视频等等。
在Java的HashMap中有使用。
是一个链表的数组
- 对key进行进行散列函数，求Hash值，找到其对应的链表。
- 剩下的解决hash冲突的问题
- 解决hash冲突，可以在命中链表之后顺序比较
- 这里顺便再说一下一致性hash. 预置很多节点，选择最近的节点存入，可以解决增加节点数据转移的问题。

常用排序算法的实现（Java版） 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序等。
java二分查找算法实现 package arithmetic; * @author JasonLee * @description java的二分查找(折半查找),前提是数组中的数据是有序的 * 思想:搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素， * 则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空， * 则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半