1.算法

  1. 简书：https://www.jianshu.com/p/1af509b2be08
  2. cnblogs: https://www.cnblogs.com/itsharehome/p/11058010.html

1.1.排序算法

  1. 1、十种常见排序算法分类
  2. 1、按数据是否加载到内存再计算分
  3.         1-1、内部排序(全部加载到内存)
  4.         1-2、外部排序
  5.     2、按数据是否进行比较分
  6.     2-1、比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
  7.     2-2、非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 
  9. 2、算法的时间复杂度
  10. 2-1、时间频度：也称语句频度，一个算法中的语句执行次数，记为T(n)。一个算法花费的时间与算法中语句的执行次数成正比，语句执行次数越多，花费时间就越多，
  11. 2-2、当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常熟，则称为f(n)是T(n)的同数量级函数。记为：T(n)=O(f(n)),O(f(n))为算法的渐进时间复杂度，简称：时间复杂度。
  12. 2-3、常用的时间复杂度有以下七种，算法时间复杂度从小到大为：
  13. O(1)常数型、
  14. O(log2 n)对数型、
  15. O(n)线性型、
  16. O(nlog2n)线性对数型、
  17. O(n^2)平方型、
  18. O(n^3)立方型、
  19. O(n^k)k次方型、
  20. O(2^n)指数型.
  21. 4、空间复杂度(Space Complexity)
  22. 指运行完一个程序所需内存的大小，利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。
  23. 程序执行时所需存储空间包括以下两部分。 
  24.         （1）固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，这部分属于静态空间。 
  25.         （2）可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。
  26. 1、空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
  27. 2、通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1)。
  28. 3、算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。

十种常见排序算法分类示意图
Java-基础算法-简介 - 图1
十种常见排序算法算法复杂度
Java-基础算法-简介 - 图2

1.1.1.冒泡排序

1.2.查找算法

  1. 1、常用的查找算法有：
  2. 1-1、顺序(线性)查找
  3. 1-2、二分查找/折半查找: 数据必须是有序的
  4. 1-3、插值查找
  5. 1-4、斐波那契查找(黄金分割比)
  6. blog:
  7. https://blog.csdn.net/abcdef314159/article/details/85097414
  8. https://blog.csdn.net/smile_from_2015/article/details/72190562

1.2.1.顺序/线性查找

  1. 顺序/线性查找：从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录;如果直到最后一个(或第一个)记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功 。
  3. /**
  4.  * 顺序查找
  5.  * @param a 数组
  6.  * @param key 待查找关键字
  7.  * @return 关键字下标
  8.  */
  9. public static int sequentialSearch(int[] a, int key) {
  10. for (int i = 0; i < a.length; i++) {
  11. if (a[i] == key)
  12. return i;
  13. }
  14. return -1;
  15. }

1.2.2.二分查找

  1. 二分查找思路分析：
  2. 1、确定该数据的中间的下标
  3. mid = (第一个元素+第二个元素)/2
  4. 2、让查找的数findVal与arr[mid]进行比较
  5. findVal > arr[mid],递归向右查找
  6. findVal < arr[mid],递归向左查找
  7. findVal == arr[mid],说明找到了，返回
  8. 3、递归结束条件确定
  9. 找到需要查找的数findVal,结束递归
  10. 递归完整个数组没找到findVal，结束递归: 第一个元素下标> 第二个元素下标
  11. 二分查找求mid索引公式：low-左边索引，high-右边索引
  12. mid = (low+high)/2 = low + (high-low)/2

1.2.2.1.二分查找-递归方式实现
  1. public class Demo{
  2.     public static void main(String[] args) {
  3.         // 二分查找的前提是：给定的数组是有序数组 
  4. int [] arr = {1,3,4,5,6,7,8,9,10,11};
  5. // 递归实现
  6. System.out.println(recursiveFind(arr,0,arr.length-1,9));
  7. }
  8.     private static int recursiveFind(int[] arr,int start,int end,int searchKey){
  9.             if (start <= end) {
  10.                 int middle =  (start+end)/2;
  11.                 if (searchKey == arr[middle]) {
  12.                     return middle;
  13.                 } else if (searchKey < arr[middle]) {
  14.                     return recursiveFind(arr, start, middle - 1, searchKey);
  15.                 } else {
  16.                     return recursiveFind(arr, middle + 1, end, searchKey);
  17.                 }
  18.             } else {
  19.                 return -1;
  20.             }
  21.         }     
  22. }

2.2.2.2.二分查找-非递归方式实现
  1. public class Demo{
  2.     public static void main(String[] args) {
  3.         // 二分查找的前提是：给定的数组是有序数组 
  4. int [] arr = {1,3,4,5,6,7,8,9,10,11};
  5. // 常规方式-非递归方式
  6. System.out.println(find(arr,9));
  7. }
  9.     private static int find(int [] arr,int searchKey){
  10.             int lowerBound = 0;
  11.             int upperBound = arr.length -1;
  12.             int curIn;
  13.             while(lowerBound <= upperBound){
  14.                 curIn = (lowerBound + upperBound) / 2;
  15.                 if(arr[curIn] == searchKey){
  16.                     return curIn;
  17.                 }else{
  18.                     if(arr[curIn] < searchKey){
  19.                         lowerBound = curIn + 1;
  20.                     }else{
  21.                         upperBound = curIn - 1;
  22.                     }
  23.                 }
  24.             }
  25.             return -1;
  26.         }   
  27. }

2.2.3.插值查找

插值查找类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
插值查找mid索引公式：key-指需要查找的数据findVal
mid = low + (high-low)*(key-arr[low])/(arr[high]-arr[low])
代码示例：
        public static int insertSearch(int[] array, int key) {
            return search(array, key, 0, array.length - 1);
        }
        private static int search(int[] array, int key, int left, int right) {
            while (left <= right) {
                if (array[right] == array[left]) {
                    if (array[right] == key)
                        return right;
                    else return -1;
                }
                int middle = left + ((key - array[left]) / (array[right] - array[left])) * (right - left);
                if (array[middle] == key) {
                    return middle;
                }
                if (key < array[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            return -1;
        }

2.2.4.斐波那契查找(黄金分割比)

斐波那契查找(黄金分割比)：也仅仅改变了中间节点(mid)的位置，位于黄金分割点附近，
mid = low + F(k-1)-1; (F为菲波那切数列,low-左边索引)
F(k-1)-1的理解：
F[k] = F[k-1]+F[k-2] ==> F[k]-1 = (F[k-1]-1) + (F[k-2]-1) +1;
由：斐波那契查找的数组长度必须是F[k]-1
===>mid = low + F(k-1)-1;
菲波那切数列：{1,1,2,3,5,8,,13,21,34,55,.....},两个相邻数的比例，无线接近黄金分割值0.618