Java版的数据结构和算法（二） java

PS：本文系转载文章，阅读原文可读性会更好，文章末尾有原文链接
ps：本篇文章写斐波那契查找算法和数组、链表、树的存储方式
1、斐波那契查找算法
斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……；在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2），这里有一个黄金分割点的概念：指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比，取其前三位数字的近似值是0.618；斐波那契数列中，两个相邻数的比例是无限接近与黄金分割值0.618。
“把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比，取其前三位数字的近似值是0.618” 这句话是什么意思呢？我来拿斐波那契数列里面的3个数（13、21 和 34）来举个例子，假设有一条绳子34米并把这条绳子命名为A，把A分成两段，一段是13米并命名为A1，另一段是21米并命名为A2；这个时候计算A1的长度除以A2的长度，约等于0.619；计算A2的长度除以A的长度，约等于0.617；这个时候A1/A2 是不是差不多等于A2/A，这回该理解蓝色的那一句话的意思了吧。
斐波那契查找算法与二分查找算法很类似，只是在于 mid 的计算不一样；
（1）在二分查找算法中，mid = (0 + array.length) / 2。
（2）在斐波那契查找算法中，我们要搞明白几个变量，那就是mid、low、high、F(k-1)-1，其中 mid=low+F(k-1)-1，low 表示什么呢？它表示一开始一个数列区间中最左边的下标，比如数组 arr={1,2,3,4,6}，那么 low 一开始就是数组元素1的下标，也就是0；high 表示一开始一个数列区间中最右边的下标，比如数组 arr={1,2,3,4,5,6}，那么 low 一开始就是数组元素6的下标，也就是5；mid 表示[low,high]之间的一个值；由斐波那契数列计算公式 F(k) = F(k-1) + F(k-2) 得到 F(k)-1 = (F(k-1) - 1) + (F(k-2) - 1) + 1，这时候把 F(k)-1 看做一根线总长名叫A，把 F(k-1) - 1 看做是 A 的一部分并命名为 A1，把 1 看做是 A 的一部分并命名为 A2，也就是表示1个数，那便是 mid，把 F(k-2) - 1 看做是 A 的一部分并命名为 A3，所以 mid 即表示[low,high]之间的一个值，也表示 F(k-1)-1 中的一个数。
我画个图来表示
图片
图1
好，我们举个例子，注意斐波那契数查找算法适合在有序的数列进行查找，这里有斐波那契数组 f={1,1,2,3,5,8,......}，待查找的数组 arr={1,2,3,4,5,6}，假设我们从 arr 数组中查找元素6的下标；
算法思路分析一把：
（1）拿到斐波那契数组 f 。
（2）判断数组 arr 的长度是不是斐波那契数组 f 中的一个元素，显然不是，arr 的长度在斐波那契数组 f 中是大于5而小于8，那么我们就把数组 arr 复制到一个长度为8的数组 temp 中，复制完成后 temp={1,2,3,4,5,6,0,0}，我们把 temp 中为0的元素赋值数组 arr 的最大值6，赋值完成后 temp={1,2,3,4,5,6,6,6} 。
（3）判断 low 是否大于 high，如果大于就返回 -1，表示没有找到；low=0，high=arr.length=6，显然不是，程序往下走。
（4）计算 mid ，mid = low + f[k - 1] - 1，数组 temp 的长度是8，8在数组 f 的下标是5，所以k = 5，mid=0 + f[4] - 1=4 。
（5）判断查找值是否小于 temp[mid]，如果成立，那么 high=mid-1，k--，这里为什么是 k--，我们再把 f[k - 1] - 1 这段（看图1理解）分成 f[(k -1) -1] -1 、mid 和 f[(k -2) -1] -1，所以新的 k 就等于 k-1，也就是 k--；判断查找值是否大于 temp[mid]，如果成立，那么 low = mid + 1，k=k-2，这里为什么是 k=k-2，f[k -2] -1 分成 f[k -3] -1 、mid和 f[k -4] -1 这3部分，也就是 f[(k -2)-1] -1 、mid 和 f[(k -2)-2] -1，所以新的 k 就等于 k-2；判断查找值是否等于 temp[mid]，如果成立，那么再如果 mid <= high，就返回 mid ，如果 mid > high ，就返回 high 。
（6）判断查找值是否大于 temp[4]，显然成立，重新计算 k 和 low，k = 4 - 2 = 2，low = mid + 1 = 4 + 1 = 5 。
（7）重新计算 mid，mid = low + f[k - 1] - 1 = 5 + 1 - 1 = 5 。
（8）判断查找值是否等于 temp[5]，显然成立，又如果 mid <= high，所以返回 mid 。
代码实现一把：
public class Test {
private static int maxSize = 100;
private static int[] fib() {

int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i <= maxSize - 1; i++) { f[i] = f[i - 1] + f[i - 2]; } return f;

}
public static int fibSearch(int[] arr, int findVal) {

return fibSearch(arr, 0, arr.length - 1, findVal);

}
public static int fibSearch(int[] arr, int low, int high, int findVal) {

if (arr == null || arr.length <= 0) return -1; int k = 0; // 表示斐波那契数列的下标 int[] f = fib(); // 获取斐波那契数组 int mid = 0; // 获取斐波那契分割数值，比如在这个demo中， // 判断数组 arr 的长度是不是斐波那契数组 f 中的一个元素，显然不是， // arr 的长度在斐波那契数组 f 中是大于5而小于8， // 那么我们就把数组 arr 复制到一个长度为8的数组 temp 中 // 8 在斐波那契数组 f 中的下标是5，所以k=5 while (high > f[k] - 1) { k++; } // 如果 f[k] > arr.length ，那么就将 arr 所有元素赋值给数组 temp // 比如在这个demo中，temp={1,2,3,4,5,6,0,0} int[] temp = Arrays.copyOf(arr, f[k]); // 把扩容多出来的数赋予原来arr的最后一个数据 // 比如在这个demo中，将temp[6] = arr[5],temp[7] = arr[5] for (int i = high + 1; i < temp.length; i++) { temp[i] = arr[high]; }while (low <= high) { mid = low + f[k - 1] - 1; if (findVal < temp[mid]) { high = mid - 1; k--; } else if (findVal > temp[mid]) { low = mid + 1; k -= 2; } else { if (mid <= high) { return mid; } else { return high; } } } return -1;

}
public static void main(String[] args) {