递归(Recursion)

简单的说递归就是自己调用自己，每次调用时传入不同的变量

小案例引出(调用机制理解)

打印数字

public static void test(int n) {
    if (n > 2) {
        test (n - 1);
    }
    System.out.println ("n=" + n);
}

数据结构08_递归.png

阶乘问题

public static int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    else {
        return factorial(n - 1) * n;
    }
}

递归能解决的问题

  1. 各种数学问题如：8皇后，汉诺塔，阶乘，迷宫，球和篮子
  2. 各种算法中也会使用递归比如快排，归并排序，二分查找，分治算法
  3. 将使用栈解决的问题->递归代码比较简洁

递归需要遵守的重要规则

  1. 执行一个方法时，就创建一个新的受保护的独立空间，栈空间
  2. 方法的局部变量时独立的，不会相互影响
  3. 递归必须向退出递归的条件逼近，否则就是无限递归，死递归
  4. 当一个方法执行完毕，或者遇到return就会返回，遵循谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

迷宫问题

描述：把一个小球放在迷宫中的一个位置，使小球达到目标位置。

规定

  1. 用二维数组模拟地图
  2. 为1即位墙壁
  3. 为2即为小球走过的路
  4. 为3则为死路
  5. 为0是未走过的路程
  6. 小球从11开始找到达65即为找到
  7. 定制策略，先走下->右->上->左

代码实现

public static void main(String[] args) {
    // 创建一个二维数组模拟迷宫
    int[][] map = new int[8][7];
    // 使用1表示墙
    // 上下置为1
    for (int i = 0; i < 7; i++) {
        map[0][i] = 1;
        map[7][i] = 1;
    }
    // 左右
    for (int i = 0; i < 8; i++) {
        map[i][0] = 1;
        map[i][6] = 1;
    }
    map[3][1] = 1;
    map[3][2] = 1;
    map[3][3] = 1;
    map[5][4] = 1;
    map[4][5] = 1;
    for (int[] item : map) {
        for (int i : item) {
            System.out.print ( i + "\t" );
        }
        System.out.println ();
    }
    // 使用递归给小球找路
    setWay (map, 1, 1);
    System.out.println ("----------分割线----------");
    for (int[] item : map) {
        for (int i : item) {
            System.out.print ( i + "\t" );
        }
        System.out.println ();
    }
}

递归代码

public static boolean setWay(int [][] map, int i, int j) {
     if (map[1][5] == 2) { //通路找到了
         return true;
     } else {
	 // 没走过
         if (map[i][j] == 0) {
             map[i][j] = 2;
             if (setWay (map, i + 1, j)) { // 向下走
                 return true;
             } else if (setWay (map, i, j + 1)) {
                 return true;
             } else if (setWay (map, i - 1, j)) {
                 return true;
             } else if (setWay (map, i, j - 1)) {
                 return true;
             } else {
                 map[i][j] = 3;
                 return false;
             }
         } else { // 不=0可能是1 2 3 
             return false;
         }
     }
}

思考

  1. 迷宫问题的路径跟程序员设置的找路策略有关，即找路的上下左右有关
  2. 求出最短路径？

我的理解

我一直是把递归理解为，每一个方法都是完成一件事情的一个人，下一件事情怎么做交给下一个人做就好了。
比如setWay方法就是判断下一个格子能不能走的一个方法，每一个方法都只需要判断自己管的下一个格子能不能走，剩下的向左向右走就交给下一个setWay方法解决就好了。

八皇后问题

问题描述

在8*8的棋盘上放8个皇后，他们不能在一条直线上（横向或者纵向）也不能再一条斜线上

思路分析

  1. 第一个皇后放在第一行第一列
  2. 第二个皇后放在第二行第一列，然后判断是不是ok，不ok继续放在第二，三列依次放完所有的列，找到一个合适的
  3. 继续放第三个皇后，还是第一列，第二列，直到第8个皇后也放在了一个不冲突的位置，算是找到了一个正确的解
  4. 当得到一个正确的解的时候开始回溯，将第一个皇后放在第一列的所有正确解全部得到
  5. 然后回头继续第一个皇后放在第二列，后面继续循环执行1234步骤

使用一个一维数组既可以表示，a[8]={1,2,3,4,5,6,7,8}下标表示第几个皇后，值代表放在第几列

代码实现

规则定义
用max来规定最大的行数
用一个一维数组保存一次解 下标表示行数，值表示列数
用一个List存储所有的解

int max = 8;
// 定义一个数组，保存结果
int[] array = new int[max];
List<int[]> list = new ArrayList<>();

辅助方法：判断放置第n个皇后，是否符合规则

小算法：判断两个点是否在一条斜线上 是判断 行值差的绝对值是否等于列值差的绝对值
也就是Math.abs ( n - i ) == Math.abs ( array[n] - array[i] )

private boolean judge(int n) {
    for (int i = 0; i < n; i++) {
        if (array[i] == array[n] || Math.abs ( n - i ) == Math.abs ( array[n] - array[i] )) {
            return false;
        }
    }
    return true;
}

放置方法：递归的方法
分析：

  1. 首先明确当前方法的意义，放置第n行皇后，会遍历第n行的所有结果列
  2. 递归结束的条件是n的值是max也就是n==8 其实是第九行 如果要放置第九行就代表前八行放好了也就没必要继续放置了
  3. 继续看放置每行的皇后，会由第一列开始，判断当前皇后的位置是否冲突
  4. 不冲突就放下一个皇后，下一个皇后怎么放，之前我们方法的意义不就是放置第n个皇后吗，只需要check(n + 1) 就是放置下一个皇后了
  5. 冲突的话就什么都不用做，让循环继续进行，检查当前行的下一列是否冲突就好了
private void check(int n) {
    if (n == max) { // n=8 皇后已经放好了
        list.add (array);
        return;
    }
    // 依次放入皇后
    for (int i = 0; i < max; i++) {
        // 先把当前皇后 n放到改行的第一列
        array[n] = i;
        // 判断当前放置n皇后时候是否冲突
        if (judge ( n )) { // 不冲突
            // 放第n+1个皇后
            check ( n + 1 );
        }
    }
}

测试和结果

public static void main(String[] args) {

    Queue8 queue8 = new Queue8 ();
    queue8.check (0);
    System.out.println (queue8.list.size ());
}

最后list的大小是92，内容就没必要看了，应该是正确的
这种方法应该是8皇后的暴力破解方案，教程有讲到以后会使用贪心算法来优化

排序算法

介绍

排序也叫排序算法(Sort Algorithm)，排序是将一组数据，依照指定的顺序进行排列的过程。

分类

  1. 内部排序：在内存中的排序
  2. 外部排序：借助外存的排序

常见排序算法分类

  • 插入排序
    • 直接插入
    • 希尔排序
  • 选择排序
    • 简单选择
    • 堆排序
  • 交换排序
    • 冒泡排序
    • 快速排序
  • 归并排序
  • 基数排序

算法的时间复杂度

度量一个程序(算法)执行的时间的两种方法

事前估算，通过分析某个算法的时间复杂度来判断那个算法更优秀

时间频度

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，那个算法中的语句执行次数多，他花费的时间就多。
一个算法中的语句执行的次数称之为语句频度或者时间频度。记为T(n)。

特点

  1. 常数可以忽略
  2. 低阶项可以忽略
  3. 系数可以忽略

时间复杂度

一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若由某个辅助函数f(n)，使得当n趋近于无穷大的时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

T(n)不同时间复杂度有可能相同

时间复杂度的计算方式
用常数1代替运行时间中的所有加法常数
修改后的运行次数函数中，只保留最高阶项
去除最高阶项的系数

常见的时间复杂度

  1. 常数阶O(1)
  2. 对数阶O($log_2 n$).
  3. 线性阶O(n)
  4. 线性对数阶O(n$log_2 n$)
  5. 平方阶O(n^2)
  6. 立方阶O(n^3)
  7. k次方阶O(n^k)
  8. 指数阶O(2^n)

常见的算法时间复杂度由小到大一次为1-8
我们要尽量避免是用指数阶的算法

常见的时间复杂度计算

常数阶O(1)

无论代码由多少行，只要没有循环递归等复杂的结构，这个代码的时间复杂度就是O(1)

对数阶O($log_2 n$)

在while或者for循环中，每次叠加的步长都乘以i*2，条件是小于n，i距离n就越来越近了。假设循环x次后，i就大于n了此时循环就推出了，也就是说2的x次方等于n，那么x=$log_2 n$也就是说循环了$log_2 n$次后代码结束了，因此代码的时间复杂度就是O($log_2 n$)

线性阶O(n)

单纯的for循环就是线性阶

线性对数阶O(n$log_2 n$)

将时间复杂度位O($log_2 n$)的循环，循n次就是线行对数阶

平方阶O(n^2)

立方阶O(n^3)

k方阶(n^k)

双重循环 三重 k次循环

算法的平均时间复杂度和最坏时间复杂度

**平均时间复杂度：**平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
**最坏情况：**最坏情况是指最坏时候的时间复杂度。一般讨论的时间复杂度就是最坏时间复杂度。

空间复杂度

类似于时间复杂度，一个算法的空间复杂度，定义为该算法所耗费的存储空间，它也是问题规模n的函数。

空间复杂度是对一个算法在运行过程中临时占用的存储空间的大小的量度，有的算法需要占用临时的工作单元数于解决问题的规模n有关，它随着n的增大而增大，当n较大时占用较多的存储空间。

在做算法分析的时候，主要讨论的还是时间复杂度。从用户使用体验上来看，更看重程序的执行速度。其实就是用空间来换取时间。

基础排序(冒泡选择插入)

冒泡排序

冒泡排序(Bubble Sorting)的基本思想是：通过对待排序序列从前向后(从下标较小的元素开始)，依次比较相邻元素的值若发现逆序则与之交换，使值较大的元素逐渐从前移向后部。
很简单的排序过程看代码就完事了

小问题
如果在一次内循环中一次交换都没有发生的话，就说明改数组依然是有序的，故而可以结束掉外循环
这个操作借助了临时变量flag来实现

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {1, 56, 12, 45, 33, -5, -1, 6};
        // 为了理解，我们把冒泡排序的演变过程
        // 第一堂排序就是把最大的数拍到最后
        int temp = 0; // 临时变量
        boolean flag = false; // 标识变量，表示是否进行过变换
        for (int j = 1; j < arr.length; j++) {
            for (int i = 0; i < arr.length - j; i++) {
                // 如果前面的数比后面的大就交换
                if (arr[i] > arr[i + 1]) {
                    if (!flag)
                        flag = true;
                    temp = arr[i];
                    arr[i] = arr[i +1];
                    arr[i + 1] = temp;
                }
            }
            if (!flag) // 一大堂排序中一次交换都没有
                break;
            else
                flag = false;
        }
        String string = Arrays.toString ( arr );
        System.out.println (string);
    }
}

选择排序

思想

第一次从数组0-length中找到最小的值和0位置的值进行交换，第二次从1-length中找最小的和1位置的数交换依次类推。
思想很简单
每次循环找到最小的值，和前面的值进行交换就ok了
看代码就完事了

public class SelectSort {
    public static void main(String[] args) {
        int arr[] = {1, 56, 12, 45, 33, -5, -1, 6};
        // 外层循环，代表需要交换几次，每次把当前元素和后面的最小的交换位置
        for (int i = 0; i < arr.length; i++) {
            // 两个辅助变量用于找到后面的最小的值的位置
            int minIndex = i;
            int min = arr[i];
            // 循环找到后面的最小的值的位置
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 将当前值的位置和最小的字的位置交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
        System.out.println (Arrays.toString ( arr ) );
    }
}

插入排序

For Me

首先是自己根据《数据结构与算法分析 JAVA语言描述》这本书理解的插入排序，也是因为比较简单就先列出自己的理解的书上的思路和自己实现的代码。
思路

首先插入排序的主要思想我认为是，保证先前部分有序。

首先拿出数组中的第二个元素，把本元素前面的元素看为一个有序的数组。将本元素插入到前面的有序数组中去，并使其有序。

以此再将第3第4第n个元素进行上述操作即可使得，数组有序。

实现代码

具体步骤：

  1. 外层for循环是来选择第i个数来插入0-i这个有序数组的
  2. 内循环是是来找到0-i这个有序数组中适合i插入的位置
  3. 每次进入if中就表示i这个数在j这个数前面还需要继续往下找
  4. 将arr[j] = arr[j - 1]是为了将比i大的全部往后挪一格，为i腾位置
  5. o是用来记录if执行过几次，也就是记录到第几个数之后就是i的位置
  6. 最后将o在的位置和数赋值成之前temp存储的i的值就可以了
public class InsertSort {
    public static void main(String[] args) {
        // 待排序数组
        int[] arr = {12, 5, -3, 24, 25, 33, -1};
        // 主体逻辑
        int j;
        for (int i = 1; i < arr.length; i++) {
            // 内循环实现插入
            int temp = arr[i];
            int o = i;
            for (j = i; j > 0; j--) {
                if (temp < arr[j - 1]) {
                    arr[j] = arr[j - 1];
                    o--;
                }
            }
            arr[o] = temp;
        }
        // 输出
        System.out.println(Arrays.toString(arr));
    }
}

优化
看了书上的例子后，发现书上的逻辑更胜一筹

这里书上的逻辑，直接摒弃了o这个变量，将判断条件提升到了内循环中，从而控制了循环的次数，这样这时的j变量不仅完成了j的作用还顺便完成了我定义的o的作用。太精彩了。

public class InsertSort {
    public static void main(String[] args) {
        // 待排序数组
        int[] arr = {12, 5, -3, 24, 25, 33, -1};
        // 主体逻辑
        int j;
        for (int i = 1; i < arr.length; i++) {
            // 内循环实现插入
            int temp = arr[i];
            for (j = i; j > 0 && temp < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
        // 输出
        System.out.println(Arrays.toString(arr));
    }
}

For Course

教程中的思路是大体一致这里贴出代码

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int insertVal = arr[i];
        int insertIndex = i - 1;
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex -= 1;
        }
        arr[insertIndex + 1] = insertVal;
    }
}

这里教程中是使用的wile循环代替的for的内循环，应该是更容易理解一些，大体思路并无差异

高级排序(Shell,基数,快速,归并)

Shell(希尔)排序

简单插排的局限性

在简单插排中，很明显可以看出对于基本有序的数组进行插排效率是比较高的，但是对于较小的数在数组的后面就会移动非常多次数据，效率比较低。

Shell排序介绍和思想

介绍
首先Shell排序是由希尔这个人提出的，也属于一种插入排序，是简单插入排序的改进后的增强的算法，也称为缩小增量排序

思想
把数组按照增量进行分组，对分组进行排序后缩小增量，继续进行直接插入排序，直到增量缩小为1就是对整个数组进行直接插入排序但是这个时候的数组是基本有序的数组，所以效率会很高。

实现

实现方法有两种，基于交换和基于插入。
基于交换便于理解，而基于插入则是真正的希尔排序。
其实希尔排序可以看成是这两种基础排序加上分组的设定。

基于交换实现
很简单其实就是在交换的基础排序算法(冒泡排序)之上又加入了分组的思想设定
但是这样并不能给本来的冒泡排序带来优化，因为冒泡在对基本有序的数组进行排序或者任何情况下的数组排序都是一样的效果

public static void shellSort(int[] arr) {
    int temp = 0;
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            // 遍历各组中所有的元素(共有5组每组又两个元素)
            for (int j = i - gap; j >= 0 ; j -= gap) {
                // 当前元素大于加上步长后的那个元素
                if (arr[j] > arr[j + gap]) {
                    temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
    }
}

基于插入实现
就是在直接插入的算法基础上加上了分组的设定，又利用了插入排序对基本有序的数组排序效率高的特点，所以结合成了希尔排序。
我认为希尔排序只是一种思想，也就是分组的思想。

public static void shellSort2(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        int j;
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            for (j = i; j - gap >= 0 && temp < arr[j - gap]; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

QuickSort(快速排序)

咳！学到快速排序，就不得不翻出建站的时候写的一篇文章
快速排序的实现和分析
现在回头再看自己的这个逻辑表达能力哟，很让人揪心。

这里就只贴出源码

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    private static void quickSort(int[] arr, int low, int height) {
        // 一旦不符合这个条件就说明,需要分治的区域已经小于1个就相当于有序了
        if (low < height) {
            int mid = division(arr, low, height);
            // 对分治后的左区域进行快速排序
            quickSort(arr, low, mid - 1);
            // 右区域
            quickSort(arr, mid + 1, height);
        }
    }

    // 快速排序的核心，分治的过程
    private static int division(int[] arr, int left, int right) {
        // 选取中间数
        int mid = arr[left];
        // 接下来的工作就是把比中间数小的全部放在左面，大的放在右面
        // 定义一个变量来表示空间是在左边还是右边
        boolean flag = true; // true表示在空间在左边
        // 当left==right的时候就是分治结束的时候
        while (left != right) {
            // 注意观察空间的位置，开始的时候是在左边因为我们的中间值拿出去了，所以空的位置就是中间值的位置arr[0]
            if (flag) {
                // 空间在左边
                // 从右边找值
                if (arr[right] < mid) {
                    // 小于中间值需要放在左边
                    arr[left] = arr[right];
                    // 空间的位置变为右边
                    flag = false;
                    // 左边的指针后移
                    left++;
                } else {
                    // 大于中间值就是该在右边
                    // 只需要移动右指针即可
                    right--;
                }
            } else {
                // 空间在右边
                // 从左边找值
                if (arr[left] > mid) {
                    // 比中间值大，需要放在右边
                    arr[right] = arr[left];
                    // 空间标在左边
                    flag = true;
                    // 右边的指针累加
                    right--;
                } else {
                    // 比中间值小
                    // 左边指针累加
                    left++;
                }
            }
        }
        arr[left] = mid;
        return left;
    }

MergeSort(归并排序)

和快排一样也是基于分治和递归的思想，不过实现排序的方式又实用了归并所以叫归并排序。

整体思想

分治就是分而治之的意思，将大问题化小，小问题化了。
将数组分为左右两个数组，这是个递归的过程，直到分成每个数组只有一个元素。
然后将数组借用临时的数组，进行有序的装配(归并)

数据结构(09)_分治归并过程

注*图示为引用教程
这里图示的分就是分治的过程
而治就是归并的过程

代码实现

arr ： 待排序数组
left : 左边界
right ：右边界
mid ： 中间点

还是那个理解递归的思路，先搞明白要递归的方法是干什么的。

  1. mergeSort方法是用来分治一个数组的
  2. left < right 表示两个位置间不止一个元素的时候
  3. int mid = left + ((right - left) >> 1);使用了位运算求出了left和right的中点
  4. mergeSort(arr, left, mid);对左边的区间进行分治
  5. mergeSort(arr, mid + 1, right);;对右边的区间进行分治
  6. merge(arr, left, mid, right);将两个区间进行归并
public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + ((right - left) >> 1);
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

最关键的就是merge这个方法的编写，也就是实现两个数组的归并,分为5部

  1. 分别定义三个指针，指向左区间的开头(i)，右区间的开头(j)，temp的开头(n)，这里temp的长度应该为right - left + 1
  2. 如果比较left和right的值，较小的装入temp，只要有一个区间没有了值就结束装载

这里是用temp[n++] = arr[i] < arr[j] ? arr[i++] : arr[j++];来判断大小和装入temp的.使用了++的小技巧

  1. 然后看是left还是right中的值没有装完，接着装入temp中即可
  2. 将temp中的值复制到arr也就是原来的两个区间中去

注意这里for循环开始是k但是区间的第一个值应该是k+left

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int n = 0;
    while (i <= mid && j <= right) {
        temp[n++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) {
        temp[n++] = arr[i++];
    }
    while (j <= right) {
        temp[n++] = arr[j++];
    }
    for (int k = 0; k < temp.length; k++) {
        arr[left + k] = temp[k];
    }
}

小结

看了算法书上的归并排序，没有细看只是大体的瞄了几眼，好像分了从顶向下和自地向上的实现方式。以后再研究吧！

基数排序

基数排序(radix sort)属于"分配式排序"(distribution sort)，又称"桶子法"(bucket sort)或bin sort。

思想

创建10个桶，然后分别计算待排序数组的个位数，安照个位数将其放在对应的桶中。再按照桶的顺序将其取出放回原数组。这样就实现了个位的有序。
继续计算十位数，将其按照十位数大小放在桶中，再取出放回原数组。
继续计算百位和千位，直到计算到该数组内最大数的最高位，再取出即有序。

实现代码

先计算出待排数组最大数的位数

// 数组中最大的数的位数
int max = arr[0]; // 假设第一个数是最大的

for (int i = 1; i < arr.length; i++) {
    if (i > max) {
        max = arr[i];
    }
}
// 的到最大数是几位数
int maxLength = (max + "").length();

定义桶
定义一个bucketElementCounts用来代表桶中有多少个数据

int[][] bucket = new int[10][arr.length];
int[] bucketElementCounts = new int[10];

核心的逻辑代码
将数据放入桶中和取出数据放回数组

for (int z = 0, n = 1; z < maxLength; z++, n *= 10) {
    // 将数据放入桶中
    for (int i = 0; i < arr.length; i++) {
        int digitOfElement = arr[i] / n % 10;
        // 放在对应的桶中
        bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = arr[i];
    }
    // 取数据
    int index = 0;
    // 遍历每一个桶，将桶中的数据放到原数组
    for (int i = 0; i < bucketElementCounts.length; i++) {
        if (bucketElementCounts[i] != 0) {
            // 循环该桶
            for (int j = 0; j < bucketElementCounts[i]; j++) {
                // 取出元素放入到arr
                arr[index++] = bucket[i][j];
            }
        }
        bucketElementCounts[i] = 0;
    }
}

分析

基数排序的速度非常快甚至在面对大量数据的时候比快速排序归并排序sell排序都要快
但是缺点也很明显，首先目前代码不能对负数进行排序，可以再创建9个桶来实现对负数的支持
但是那样就会有19个桶本来10个桶占用的空间已经非常大了，19个桶占用的空间就更恐怖
也就是基数排序虽然时间复杂度很低但是空间复杂度非常高

常用排序算法比较

这里只是基础的分析

排序算法平均时间复杂度空间复杂度稳定性
冒泡排序O(n^2)O(1)稳定
插入排序O(n^2)O(1)稳定
选择排序O(n^2)O(1)不稳定
快速排序O(n*log_2n)O(n*log_2n)不稳定
希尔排序O(n*log_2n)O(1)不稳定
堆排序O(n*log_2n)O(1)不稳定
归并排序O(n*log_2n)O(n)稳定
基数排序O(n+k)O(n+k)稳定

查找算法

常见的查找算法介绍

  1. 顺序查找
  2. 二分查找/折半查找
  3. 插值查找
  4. 斐波那契查找

顺序查找

其实就是暴力查询，也是最简单的方式，直接贴上代码

public static int orderSearch(int[] arr, int findValue) {
    int curVal = -1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == findValue) {
            curVal = i;
            break;
        }
    }
    return curVal;
}

二分查找/折半查找

思想

首先待查找数组要求为必须是有序数组。

  1. 找到数组的中间索引的值
  2. 判断待查找值和中间值的大小
  3. 得出待查找值在中间值的左边还是右边
  4. 对左边或者右边进行二分查找，直到发现中间值于期望值相等
  5. 注意递归的结束条件，也就是找不到的情况

代码实现

// 二分查找
public static int binarySearch(int[] arr, int left, int right, int findValue) {
    if (left > right) {
        return -1;
    }
    int mid = (left + right) >> 1;
    int midValue = arr[mid];
    if (midValue > findValue) {
        return binarySearch(arr, left, mid - 1, findValue);
    } else if (midValue < findValue) {
        return binarySearch(arr, mid + 1, right, findValue);
    } else {
        return mid;
    }
}

这个版本也比较简单，应该直接能看懂。

课后练习

加强之前的二分查找基础版使其返回一个ArrayList内存放所有的查找值索引，未找到返回空集合

代码实现

public static List<Integer> binarySearch(int[] arr, int left, int right, int findValue) {
    if (left > right) {
        return new ArrayList<>();
    }
    int mid = (left + right) >> 1;
    int midValue = arr[mid];
    if (midValue > findValue) {
        return binarySearch(arr, left, mid - 1, findValue);
    } else if (midValue < findValue) {
        return binarySearch(arr, mid + 1, right, findValue);
    } else {
        List<Integer> list = new ArrayList<>();
        // 向左边扫描
        int temp = mid - 1;
        while (true) {
            if (temp < 0 || arr[temp] != findValue) {
                break;
            }
            list.add(temp);
            temp--;
        }
        list.add(mid);
        // 扫描右边
        temp = mid + 1;
        while (true) {
            if (temp > arr.length - 1 || arr[temp] != findValue) {
                break;
            }
            list.add(temp);
            temp++;
        }
        return list;
    }
}

插值查找

插值插值其实就是在二分查找的基础上使用算法优化了mid的值
使算法变得在待查找数组分布较为均匀时效率更高

求mid的思想

其他的写法和二分查找全部相同，区别仅在mid的求法不同
int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
其实这个公式并不需要用什么斜率之类的过分数学化的术语去理解
首先(findValue - arr[left]) / (arr[right] - arr[left])这个比值就是算法的关键
用待查找值和数组首元素的差与数组尾元素和首元素的差作比值
为什么说分布平均效率高，因为如果是完全的平均分布的化这个比值代表的其实就是待查找值的位置
前面用(right - left)也就是用数组的长度乘这个比值结果当然是期望的位置，如果是完全平均分布的化这个就是带查找值的位置，分布的越平均律，期望值位置就越准确
算法前面还加上了left这个也很好理解因为我们进行二分查找是一个递归过程，不可能一直查找左边所以这个left的值有可能不是0所以就必须加上它来保证元素位置的正确性，其实这个简单的操作在归并排序的求中值也有用到。

代码

public static int insertValueSearch(int[] arr, int left, int right, int findValue) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
    int midValue = arr[mid];
    if (midValue > findValue) {
        return binarySearch(arr, left, mid - 1, findValue);
    } else if (midValue < findValue) {
        return binarySearch(arr, mid + 1, right, findValue);
    } else {
        return mid;
    }
}

Q.E.D.

深至缄默，如云漂泊