经典算法解析Part1

　　经典算法有很多，这里罗列一些比较常用的算法：
　　1.排序算法：冒泡排序（Bubble Sort）选择排序（Selection Sort）插入排序（Insertion Sort）希尔排序（Shell Sort）归并排序（Merge Sort）快速排序（Quick Sort）堆排序（Heap Sort）计数排序（Counting Sort）桶排序（Bucket Sort）基数排序（Radix Sort）
　　2.查找算法：线性查找（Linear Search）二分查找（Binary Search）哈希查找（Hash Search）平衡树查找（AVL Tree、B-Tree）
　　3.图算法：深度优先搜索算法（Depth First Search）广度优先搜索算法（Breadth First Search）最短路径算法Dijkstra 算法Bellman-Ford 算法Floyd-Warshall 算法最小生成树算法Prim 算法Kruskal 算法
　　4.字符串匹配算法：暴力匹配算法（Brute Force）KMP 算法BM 算法
　　以上算法只是部分经典算法，并不是全部，但它们在各自领域都拥有着广泛的应用。
　　在很早之前我的排序算法专项中，已经解析了10大排序算法。本篇我们为你讲解经典查找算法。线性查找
　　线性查找是一种简单的查找算法，适用于无序数组或链表等数据结构。它遍历待查找的数据结构，逐个检查每个元素是否匹配目标值，直到找到目标值或者遍历完整个数据结构。
　　下面是使用Java实现线性查找的示例代码：public class LinearSearch {      public static int linearSearch(int[] arr, int target) {         for (int i = 0; i < arr.length; i++) {             if (arr[i] == target) {                 return i;             }         }         return -1;     }      public static void main(String[] args) {         int[] arr = {10, 20, 30, 40, 50};         int target = 30;         int result = linearSearch(arr, target);         if (result == -1) {             System.out.println(＂Element is not present in array＂);         } else {             System.out.println(＂Element is present at index ＂ + result);         }     } }
　　这段代码定义了一个名为LinearSearch的类，其中包含一个静态方法linearSearch和一个main方法。linearSearch方法接收一个整型数组和一个目标值，返回目标值在数组中的索引位置。如果目标值不在数组中，则返回-1。
　　在main方法中，我们创建了一个整型数组arr和一个目标值target，并将它们传递给linearSearch方法进行查找。最后，根据返回值，打印出相应的结果。
　　线性查找的时间复杂度是O(n)，其中n是数组或链表元素的数量。对于大型数据结构，使用线性查找可能会非常耗时，因此需要使用其他更高效的算法。二分查找
　　二分查找是一种高效的查找算法，它要求被查找的数组元素必须是有序的。具体实现过程如下：首先确定查找范围的起始点和终止点。将数组从中间划分成两部分，判断目标值与中间值的大小关系。如果目标值等于中间值，则查找成功。如果目标值小于中间值，则在数组前半部分进行查找，并将查找范围终止点移动到中间位置的前一个位置。如果目标值大于中间值，则在数组后半部分进行查找，并将查找范围起始点移动到中间位置的后一个位置。重复上述步骤，直到查找到目标值或者查找范围缩小为0。
　　下面是Java实现代码：public static int binarySearch(int[] arr, int target) {     int lo = 0;     int hi = arr.length - 1;          while (lo <= hi) {         int mid = lo + (hi - lo) / 2;         if (arr[mid] == target) {             return mid;         } else if (arr[mid] < target) {             lo = mid + 1;         } else {             hi = mid - 1;         }     }          return -1; // target not found }
　　在这个实现中，变量lo表示查找范围的起始点，变量hi表示查找范围的终止点。如果目标值在此范围内，则将此范围缩小为[mid + 1, hi]或[lo, mid - 1]。
　　这个算法的时间复杂度是O(log n)，因为每次比较都将查找范围缩小一半。哈希查找
　　哈希查找（Hash table lookup or Hash search）又称散列查找，是根据键值(Key value)而直接进行访问的一种数据查找技术。哈希函数将关键字映射到存储位置来访问记录，加快了查找速度。哈希表由关键码值(Key value)映射成表中一个位置的记录(Redirect Addressable Memory)。支持常数级平均查找时间，哈希表在数据库搜索、缓存等领域有着广泛的应用。
　　基本思想：通过把关键码值映射到表中一个位置来查找记录，以加快查找的速度。哈希函数和冲突处理方法是哈希技术的关键。
　　实现步骤：
　　1.设计哈希函数，并初始化一个数组大小为m的散列表。注意哈希函数需要满足如下特性：一致性：若a=b，则hash(a)=hash(b)高效性：计算简单，且易于解析均匀分布性：各个元素被哈希分到各个槽的概率应该相等
　　2.插入元素根据哈希函数值，得到散列表中哈希桶的地址向该哈希桶中插入元素
　　3.查找元素根据哈希函数值，得到散列表中哈希桶的地址在该哈希桶中遍历查找指定的元素
　　Java实现：public class HashSearch {     private int size;     private List[] hashtable;      public HashSearch() {         this.size = 1000; // 散列表大小为1000         this.hashtable = new ArrayList[this.size];          for (int i = 0; i < this.size; i++) {             this.hashtable[i] = new ArrayList<>();         }     }      // 哈希函数，使用除留余数法     private int hash(int key) {         return key % this.size;     }      // 插入元素     public void insert(int key) {         int hashKey = hash(key);         List list = this.hashtable[hashKey];         list.add(key);     }      // 查找元素     public boolean search(int key) {         int hashKey = hash(key);         List list = this.hashtable[hashKey];          // 判断元素是否在哈希桶中         return list.contains(key);     } }
　　哈希查找算法的时间复杂度通常为O(1)，因为它使用散列函数直接定位元素所存储的位置。但在一些极端情况下，哈希函数可能会产生哈希碰撞，这将导致查找、插入和删除操作的性能降低到O(n)。因此，在选择哈希函数时需要谨慎，并估计哈希表大小来减少哈希冲突的可能性。平衡树查找
　　平衡树是一种基于二叉树的查找算法，主要目的是为了解决普通二叉搜索树在极端情况下会退化成链表的问题。常见的平衡树有红黑树、AVL树、Treap、伸展树等。
　　这里以红黑树为例来讲解并使用Java实现平衡树查找算法。
　　红黑树简介
　　红黑树(Red-Black Tree)是一种自平衡的二叉查找树，每个节点上的额外信息包括节点颜色和子树大小等。通过遵循如下规则保持二叉查找树的整体高度始终为 O(log n) 每个节点要么是红色，要么是黑色 根节点是黑色 叶子节点是黑色 如果一个节点是红色，则它的左右子节点必须都是黑色 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
　　插入和删除一个节点的时间复杂度均为 O(log n)，查询的时间复杂度也是 O(log n)
　　Java实现红黑树代码如下：public class RedBlackTree> {     private static final boolean RED   = true;     private static final boolean BLACK = false;      private Node root;      private static class Node {         T key;         Node left, right;         int size;         boolean color;         Node(T key, int size, boolean color) {             this.key = key;             this.size = size;             this.color = color;         }     }      private void flipColor(Node x) {         x.color = !x.color;         x.left.color = !x.left.color;         x.right.color = !x.right.color;     }      private Node rotateLeft(Node h) {         Node x = h.right;         h.right = x.left;         x.left = h;         x.color = h.color;         h.color = RED;         x.size = h.size;         h.size = 1 + size(h.left) + size(h.right);         return x;     }      private Node rotateRight(Node h) {         Node x = h.left;         h.left = x.right;         x.right = h;         x.color = h.color;         h.color = RED;         x.size = h.size;         h.size = 1 + size(h.left) + size(h.right);         return x;     }      private boolean isRed(Node x) {         if (x == null) return false;         return x.color == RED;     }      private int size(Node x) {         if (x == null) return 0;         return x.size;     }      public boolean contains(T key) {         return contains(root, key);     }      private boolean contains(Node x, T key) {         while (x != null) {             int cmp = key.compareTo(x.key);             if      (cmp < 0) x = x.left;             else if (cmp > 0) x = x.right;             else              return true;         }         return false;     }      public void put(T key) {         root = put(root, key);         root.color = BLACK;     }      private Node put(Node h, T key) {         if (h == null) return new Node<>(key, 1, RED);          int cmp = key.compareTo(h.key);         if      (cmp < 0) h.left  = put(h.left,  key);         else if (cmp > 0) h.right = put(h.right, key);         else              ;  // The Key already exist in the tree.          if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);         if (isRed(h.left)  && isRed(h.left.left))  h = rotateRight(h);         if (isRed(h.left)  && isRed(h.right))     flipColor(h);          h.size = size(h.left) + size(h.right) + 1;          return h;     } }