本章主要是各种算法，主要分为有序查找和无序查找。

1、有序查找

main调用

public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int[] arr3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int[] arr4 = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99}; int result2 = sequentialSearch(arr2, 2); System.out.println("sequentialSearch的index为：" + result2); int result = sequentialSearch2(arr, 10); System.out.println("sequentialSearch2的index为：" + result); int result3 = binarySearch(arr3, 5); System.out.println("binarySearch的index为：" + result3); int result4 = interpolationSearch(arr3, 6); System.out.println("interpolationSearch的index为：" + result4); int result5 = fbiSearch(arr4, 1); System.out.println("fbiSearch的index为：" + result5); }

顺序表查找算法

/** * arr有序 * 顺序表查找算法 * 时间复杂度O（n） * * @param arr * @param key * @return */ public static int sequentialSearch(int[] arr, int key) { for (int i = 0; i < arr.length; i++) { if (arr[i] == key) { return i; } } return -1; }

顺序表查找算法-优化（哨兵模式）

/** * arr有序 * 顺序表查找算法-优化（哨兵模式） * O（n） * * @param arr * @param key * @return */ private static int sequentialSearch2(int[] arr, int key) { int i = arr.length - 1; if (arr[0] == key) { return 0; } arr[0] = key;//设置哨兵，while比较到0的时候说明没有找到，返回-1。 while (arr[i] != key) { i--; } return i == 0 ? -1 : i; }

折半查找算法（二分查找算法）

/** * arr有序 * 折半查找算法（二分查找算法） * O（logn） logn简写=long2n，x=log2n ，2的x次方等于n * n>2时，时间复杂度小于n的平方 * * @param arr * @param key * @return */ private static int binarySearch(int[] arr, int key) { int low, high, mid; low = 0; high = arr.length - 1; while (low <= high) { mid = (low + high) / 2; if (key < arr[mid]) { high = mid - 1; } else if (key > arr[mid]) { low = mid + 1; } else { return mid; } } return -1; }

插值查找法（二分查找算法的优化版本）

/** * arr有序 * 插值查找法（二分查找算法的优化版本） * O（logn） logn简写=long2n，x=log2n ，2的x次方等于n * n>2时，时间复杂度小于n的平方 * * @param arr * @param key * @return */ private static int interpolationSearch(int[] arr, int key) { int low, high, mid; low = 0; high = arr.length - 1; while (low <= high) { // mid = (low + high) / 2; mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]); if (key < arr[mid]) { high = mid - 1; } else if (key > arr[mid]) { low = mid + 1; } else { return mid; } } return -1; }

斐波那契数列查找法

/** * arr有序 * 斐波那契数列查找法 * 时间复杂度O(logn)，只做加减运算 * * @param arr * @param key * @return */ private static int fbiSearch(int[] arr, int key) { int low, high, mid, i, k; low = 0; int len = arr.length - 1; high = len; k = 0; int[] fbiArr = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55};//提前要创建一个斐波那契数列，可以动态创建，长度参照arr的长度 while (len > fbiArr[k] - 1) { k++; } arr = addArray(arr, arr.length + (fbiArr[k] - 1 - arr.length)); //要左右比较，所以需要数组扩容2个 for (i = len; i < fbiArr[k] - 1; i++) { arr[i] = arr[len]; } while (low <= high) { mid = low + fbiArr[k - 1] - 1; if (key < arr[mid]) { high = mid - 1; k = k - 1; } else if (key > arr[mid]) { low = mid + 1; k = k - 2; } else { if (mid <= len) { return mid; } else { return len; } } } return -1; } //数组扩容 public static int[] addArray(int[] arr1, int len) { int[] arr2 = new int[len]; //新数组长度 for (int i = 0; i < arr1.length; i++) { arr2[i] = arr1[i]; } return arr2; }

2、无序查找

二叉树查找操作

/TODO /待补充

散列表查找

/TODO /待补充