一、算法

作者: wqjcarnation | 来源:发表于2022-01-05 16:18 被阅读0次

算法（一）-算法思想
字符串匹配算法总结
关于GC（二）关于回收算法
iOS证书相关概念梳理
LruCache原理和源码分析（一）
记录数据结构与算法的学习之路 -----005.BF算法与RK算
JVM读书笔记-垃圾回收算法-06
面试官：限流算法有哪些？
匈牙利算法
Algorithm进阶计划 -- LRU 与 LFU 算法

目标

递归算法
查找算法
算法分析
十大排序算法

递归算法

什么是递归
递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。
通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。

递归的三大要素
第一要素：明确你这个函数想要干什么。先不管函数里面的代码什么，而是要先明白，你这个函数的功能是什么，要完成什么样的一件事。
第二要素：寻找递归结束条件。我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。
第三要素：找出函数的等价关系式。我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。

递归的案例

下面我们还看几个案例：
1、案例1(计算1+2+...+100)
分析过程：1+2+...100=100+(1...99)=100+99+(1..98)=100+99+98+(1..97)=100+99+98+...+1

    //案例1（计算1+2+...+100）
    public class CalcTest {
        public static int f(int n) {
            if (n == 1) {
                return 1;
            }
            return n + f(n - 1);
        }
    
        public static void main(String[] args) {
            int sum = f(100);
            System.out.println(sum);
        }
    }

2、案例2（实现字符串逆序）：
分析：
abcdefg=bcdefg+a=cdefg+b+a=defg+c+b+a

        public class Test01 {
        public static String reverse(String str) {
            System.out.println("---------->"+str);
            if (str.length() == 1) {
                return str;
            }
            //substring(int beginIndex)
            //substring(int beginIndex, int endIndex)
            return reverse(str.substring(1)) + str.substring(0, 1);
        }
    
        public static void main(String[] args) {
            String str = reverse("abcdefg");
            System.out.println(str);
        }
    }

3、案例3（返回斐波那契数列中的第n个值）：
斐波那契数列（Fibonacci sequence），又称[黄金分割]数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：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，n ∈ N）

    public class FeiTest {
        public static int f(int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 1;
            }
            return f(n - 1) + f(n - 2);
        }
    
        public static void main(String[] args) {
            int num = f(6);
            System.out.println(num);
        }
    }

递归的优化方法

在斐波那契数列这个案例中，很多数据会被重复计算，影响效率。比如f(3) 被重复计算两次。
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)

如果你使用递归的时候不进行优化，会有非常多的子问题被重复计算的。因此，使用递归的时候，必要须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来。

  public class Test3 {
public static void main(String[] args) {
    int[] arr = new int[40];
    long start = System.currentTimeMillis();
    int num = f(40,arr);
    System.out.println(num);
    long end = System.currentTimeMillis();
    System.out.println("程序耗时:"+(end-start));
}

public static int f(int n, int[] arr){
    if(n==1){
        return 1;
    }
    if(n==2){
        return 1;
    }
    if(arr[n-1]>0){
        return arr[n-1];
    }       
    arr[n-1] = f(n-1, arr) + f(n-2,arr);
    return arr[n-1];
}
    }

实际应用案例：

练习：Leetcode真题：第70题：爬楼梯。来源：https://leetcode-cn.com/problems/climbing-stairs
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶

示例 2：
输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶

2 阶 + 1 阶

 class Solution {
  public int climbStairs(int n) {
int[] arr = new int[n];
return c(n, arr);
   }

 public int c(int n, int[] arr) {
if (n == 1) {
    return 1;
}
if (n == 2) {
    return 2;   //注意这里返回的是2
}
if (arr[n-1] > 0) {
    return arr[n-1];
}
arr[n-1] = c(n - 1, arr) + c(n - 2, arr);
return arr[n-1];
}
   }

查找算法

1、顺序查找
基本思想：
顺序查找，就是从第一个元素开始，按索引顺序遍历待查找序列，直到找出给定目标或者查找失败。
特点：

对待查序列（表）无要求 -- 待查找序列可以是有序，也可以是无序；
从第一个元素开始；
需要逐一遍历整个待查序列（除非已经找到）；
若查找到最后一个元素还没找到，则查找失败；
缺点：
效率低 -- 需要遍历整个待查序列

性能分析：
● 需要时间：
平均查找时间 = 列表长度/2
最坏查找时间 = 列表长度
● 需要空间：
1个待查序列+1个目标元素

示例：
看一组示例，从一组数据[3,6,7,2,12,9,0,11]中查找12，

   public class Test {
public static int seqSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        int p = array[i];
        if (p == target) {
            System.out.println("sucess to find out "+target+" from array, index="+i);
            return i;
        }
    }
    System.out.println("fail to find out the target");
    return -1;
}

public static void main(String[] args) {
    int[] data = { 3, 6, 7, 2, 12, 9, 0, 11 };
    System.out.println(seqSearch(data, 12));
}
     }

2、二分查找
基本思想：
二分查找一个顺序数组，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
特点：

对待查序列（表）有要求 -- 待查找序列必须是有序；
从中间元素开始；
利用中间位置记录将表分成前、后两个子表（除非已经找到）；
如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表；

缺点：
必须是有序元素

性能分析：
● 需要时间：
查找时间 = log2列表长度

● 需要空间：
1个待查序列+1个目标元素

示例：

题目：

从一组数据[10,11,12,16,18,23,29,33,48,54,57,68,77,84,98]中查找23的位置：

思路：

初始状态：变量P指向列表中间元素，索引为mid

image

比较数组mid元素为33，大于被比较元素23，因此继续使用33之前部分的所有元素进行与23比较操作

image

继续重复上一步，查找到结果

image

示例代码：

   public class Test {
       public static int seqSearch(int[] array, int target) {
         int lo = 0;
        int hi = array.length - 1;
        while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if(target==array[mid]){//正好相等
            return mid;
        }else if (target < array[mid]) {
            hi = mid - 1;
        } else if (target > array[mid]) {//查找值大于中间址
            lo = mid + 1;
        } 
    }
    return -1;
}

public static void main(String[] args) {
    int[] data = { 10, 11, 12, 16, 18, 23, 29, 33, 48, 54, 57, 68, 77, 84, 98 };
    System.out.println(seqSearch(data, 23));
}
 }

思考题：
找左侧边界和右侧边界
leetcode34题：
在排序数组中查找元素第一个和最后一个位置

算法分析

大O表示法：
大O表示法是一种特殊的表示法，指出了算法的速度有多快。
就是将代码的所有步骤转换为数据规模N的规模的公式项，然后排除不会对问题的整体复杂度产生影响的因素，忽略系数和常数
比如执行效数是是3n+4 即为n，忽略3，4
1、时间复杂度
数据增大n倍时，耗时增长多少倍
下面按从快到慢的顺序列出了你经常会遇到的6种大O运行时间。
● O(1)，也叫常数时间，这样的算法包括数组的插入或删除，非常好的算法。
● O(log n)，也叫对数时间，这样的算法包括在有序数组里查找元素，比如二分查找，性能趋近于 O(1)。
● O(n)，也叫线性时间，这样的算法包括在无序数组中查找元素，比如简单查找。
● O(n * log n)，这样的算法包括后面将介绍的快速排序——一种速度较快的排序算法。
● O(n2)，这样的算法包括后面将介绍的选择排序——一种速度较慢的排序算法。
● O(n!)，这样的算法包括后面将介绍的旅行商问题的解决方案——一种非常慢的算法。

image.png

2、空间复杂度

空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

空间复杂度 O(n)

十大排序算法

比较类排序-7种

时间复杂度记忆-冒泡、选择、直接排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O（n2）O（n2）（一遍找元素O(n)O(n)，一遍找位置O(n)O(n)）
快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)O(nlogn)（一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn)）

1、冒泡

public static void main(String[] args) {
    int[] arr = { 9, 8, 5, 4, 2, 0 };
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}

private static void bubbleSort(int[] arr) {
    // n个数，则要进行n-1趟比较
    for (int i = 1; i < arr.length; i++) {
        // n个数，则要进行n-i趟比较
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

}

2、快排

/* 快速排序算法的排序流程如下：
● 1．先从数列中取出一个数作为基准数。
● 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
● 3．再对左右区间重复第二步，直到各区间只有一个数。*/

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        // 1. 定义基准pivot,
        int pivot = arr[left];
        // 2、 pivot移动到中间，左边都比pivot小， 右边都比pivot大
        int i = left;
        int j = right;
        while (i != j) {
            while (i < j && arr[j] >= pivot) {//从后向前找，找到第一个比基准数小的数的下标
                j--;
            }
            swap(arr, i, j);
            while (i < j && arr[i] <= pivot) {//再从前向后找，找到第一个比基准数大的数的下标
                i++;
            }
            swap(arr, i, j);
        }
        
        // 2. 递归对左右2部分快排
        quickSort(arr, left, j - 1);
        quickSort(arr, j + 1, right);
    }
}

public static void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static void main(String[] args) {
    //{2,3,0,1,4} 5 {6,7,9,10,8}
    ////从后向前找，找到第一个比基准数小的数的下标
    //再从前向后找，找到第一个比基准数大的数的下标
    int[] arr = { 5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8 };
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

3、插入

算法思路
把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

public static void main(String[] args) {
    int[] arr = { 7, 6, 9, 3, 1, 5, 2, 4 };
    InsertSort(arr);
    System.out.println(Arrays.toString(arr));
}

private static void InsertSort(int[] arr) {
    //n个数比较n-1趟
    for(int i=1;i<arr.length;i++){
        //每一趟从i处往前比
        for(int j=i;j>0;j--){
            //如果后面的比前一个小，就交换
            if (arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            } else {
                //否则停止
                break;
            }
        }
    }
    
}

4、希尔

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

public static void main(String[] args) {
    int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
    shellSort(arr);
    System.out.println(Arrays.toString(arr));

}

private static void shellSort(int[] arr) {
    // 增量gap, 并逐步的缩小增量
            for (int gap = arr.length / 2; gap > 0; gap /= 2) {
                // 从第gap个元素，逐个对其所在的组进行直接插入排序
                //虽然分析时分组考虑，但写程序时可以从gap开始顺序向后写
                for (int i = gap; i < arr.length; i++) {
                    for (int j = i; j >= gap; j -= gap) {
                        if (arr[j] < arr[j - gap]) {
                            int temp = arr[j];
                            arr[j] = arr[j - gap];
                            arr[j - gap] = temp;
                        } else {
                            break;
                        }
                    }
                }
            }
    
}

5、选择

算法思路
以由小到大排序为例，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

public static void main(String[] args) {
    int[] arr = { 29, 38, 65, 87, 78, 23, 27, 29 };
    selectionSort(arr);
    System.out.println(Arrays.toString(arr));
}

private static void selectionSort(int[] arr) {
    int minindex,temp;
    //n个数，比较n-1次
    for(int i=0;i<arr.length-1;i++){
        //每次都先假设i是最小值索引
        minindex=i;
        //接下来从i+1处开始比对，一直比到最后,得到当前最小值的索引
        for(int j=i+1;j<arr.length;j++){
            if(arr[j]<arr[minindex]){
                minindex = j; 
            }
        }
        //把最小值放到i处
        temp = arr[i];
        arr[i] = arr[minindex];
        arr[minindex] = temp;
    }
}

6、堆排序

堆的概念
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
（完全二叉树：设二叉树的深度为h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。）
我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中
关键数值：
对于某1个节点i, 它的父节点(i-1)/2
对于某1个节点i, 它的左孩子2i+1
对于某1个节点i, 它的右孩子2i+2
最后一个非叶子结点的下标：(arr.length-1-1)/2 = arr.length/2-1

堆排序的思路
（1）根据初始数组去构造初始堆。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆，再进行交换第一个元素和最后一个元素，再调整大顶堆，重复执行，直到整个数组排序完成。

建堆的过程：
现在我们有一个无序数组：27,46,12,33,49,27,36,40,42,50,51，我们先把它建成完全二叉树，然后从最后一个非叶子结点开始，从右至左，从下至上进行调整，将它调整成大顶堆。

最后一个非叶子结点的下标：(arr.length-1-1)/2 = arr.length/2-1

堆排序的过程：
将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端，调整堆结构(heapify)，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复操作，直到堆里只剩下1个元素。

    public static void main(String[] args) {
        int[] arr = { 27, 46, 12, 33, 49, 27, 36, 40, 42, 50, 51 };
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    private static void heapSort(int[] arr) {
        //根据原数据构建大顶堆
        //最后一个非叶子节点下标为arr.length/2-1
        //从第一个非叶子节点开始，遍历每一个非叶子节点，使它们都成为最大堆
        //这里传递最大的index是为了使方法变通用，防止数组遍历越界
        for(int i=arr.length/2-1;i>=0;i--){
            heapify(arr,i,arr.length-1);
        }
        
        //依次交换堆顶元素和最后一个元素，取得最大值，之后再用余下的数据重复构建大顶堆
        for(int i=arr.length-1;i>0;i--){//从后从前循环
            //始终把i的值放入arr[0],即把i与0处的值进行交换
            swap(arr,0,i);
            heapify(arr,0,i-1);//重新构建大顶堆，同时i的值也减1了
        }
        
        
    }
    /**
     * 
     * @param arr
     * @param i 当前节点的索引
     * @param lastIndex 最大索引
     */
    private static void heapify(int[] arr, int i, int lastIndex) {
        //i节点的左叶子节点下标为i*2+1 右叶子节点为i*2+2
        //比对这三个这点，谁值大，谁就与i交换
        //注意当前节点有可能不是最后一个非叶子节点，所以交换后需要对新的节点做递归
        int max=i;
        //有左叶子节点并且左叶子节点大，max=左叶子节点索引
        if(i*2+1<lastIndex&&arr[i*2+1]>arr[max]){
            max=i*2+1;
        }
        if(i*2+2<lastIndex&&arr[i*2+2]>arr[max]){
            max=i*2+2;
        }
        //左右比i的值大
        if(max!=i){
           swap(arr,max,i);
           //对子节点重复上面操作
           heapify(arr,max,lastIndex);
        }
        
    }
    
    private static void swap(int[] arr, int max, int i) {
        int temp=arr[max];
        arr[max]=arr[i];
        arr[i]=temp;
    }

7、归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。
算法思路
● 把长度为n的输入序列分成两个长度为n/2的子序列；
● 对这两个子序列分别采用归并排序；
● 将两个排序好的子序列合并成一个最终的排序序列。

public static void mergeSort(int arr[], int low, int high) {
    if (low < high) {
        // 分2部分
        int mid = (low + high) / 2;
        // 1. 对左边进行归并排序
        mergeSort(arr,  low, mid);
        // 2. 对右边进行归并排序
        mergeSort(arr,  mid + 1, high);
        // 3. 合并左右两个有序集合
        merge(arr,  low, mid, high);
    }
}

public static void merge(int[] arr,  int low, int mid, int high) {
    // 辅助数组
    int[] temp = new int[arr.length];
    int i = low;        //设置左指针初始位置
    int j = mid + 1;    //设置右指针初始位置
    int k = 0;          //临时数组指针
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 左边有剩余，将左边剩余的填入temp
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    // 右边有剩余，将右边剩余的填入temp
    while (j <= high) {
        temp[k++] = arr[j++];
    }
    // 将临时数组，从头开始拷贝到arr中
    k = 0;
    while (low <= high) {
        arr[low++] = temp[k++];
    }
}

public static void main(String[] args) {
    //int[] arr = { 8, 4, 5, 7, 1, 3, 6, 2 };
    
    int[] arr = { 8, 4, 5};
    
    mergeSort(arr,  0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

非比较类排序-3种

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

1、计数

计数排序是一种非比较排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0_{100]，[10000}19999] 这样的数据。

public static void countSort(int[] arr) {
    // 找到最大值
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    // 创建计数数组
    int[] count = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }
    int k = 0;
    // 往数组中输出
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {     //count[i]控制循环次数
            arr[k++] = i;
            count[i]--;
        }
    }
}

public static void main(String[] args) {
    int[] arr = { 8, 9, 6, 1, 7, 2, 3, 2, 4, 6, 1, 10 };
    countSort(arr);
    System.out.println(Arrays.toString(arr));
}

2、桶排序

桶排序是计数排序的升级版。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序。桶排序利用了函数的映射关系把数据分配到桶里，高效与否的关键就在于这个映射函数的确定。

桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。
但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
桶排序的基本思想是：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
算法思路
1.找出待排序数组中的最大值max、最小值min
2.我们使用动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
比如： max=50 min=0 时分6个桶，主要是从0开始
0-9 10-19 20-29 30-39 40-49 50
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
放入第几个桶=(arr[i] - min) / (arr.length) （其实是取整数部分）
4.每个桶各自排序
5.遍历桶数组，把排序好的元素放进输出数组

   public static void bucketSort(int[] arr){
       int max = Integer.MIN_VALUE;
       int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
          max = Math.max(max, arr[i]);
         min = Math.min(min, arr[i]);
    }

//桶数
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
    bucketArr.add(new ArrayList<Integer>());
}

//将每个元素放入桶
for(int i = 0; i < arr.length; i++){
    int num = (arr[i] - min) / (arr.length);
    bucketArr.get(num).add(arr[i]);
}

//对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
    Collections.sort(bucketArr.get(i));
}

     System.out.println(bucketArr.toString());

     }

3、基数排序

另一种实现方式:
数组：[26, 3, 49, 556, 81, 9, 863, 0]
1、创建桶（下标0~9），并以个位数为下标，从第一个元素开始，依次放入桶中。
0[0]
1[81]
2[]
3[3，863]
4[]
5[]
6[26，556]
7[]
8[]
9[49，9]
遍历桶，将元素依次取出，完成第一次排序：[0, 81, 3, 863, 26, 556, 49, 9]
2、以十位数为下标，将完成第一次排序的数组从第一个元素开始，依次放入桶中。
0[0，3，9]
1[]
2[26]
3[]
4[49]
5[556]
6[863]
7[]
8[81]
9[]
遍历桶，将元素依次取出，完成第二次排序：[0, 3, 9, 26, 49, 556, 863, 81]
3、以百位数为下标，将完成第二次排序的数组从第一个元素开始，依次放入桶中。
0[0，3，9，26，49，81]
1[]
2[]
3[]
4[]
5[556]
6[]
7[]
8[863]
9[]
遍历桶，将元素依次取出，完成第三次排序：[0, 3, 9, 26, 49, 81, 556, 863]
*/

代码实现

public static void main(String[] args) {
    int[] arr = { 26, 3, 49, 556, 81, 9, 863, 0 };
    radixSort(arr);
    System.out.println(Arrays.toString(arr));
}

private static void radixSort(int[] arr) {
    // 第一步：查找最大值，确定排序的次数
    int max = arr[0];
    for (int anArr : arr) {
        if (anArr > max) {
            max = anArr;
        }
    }
    // 863 这个数决定了位数 （三位）
    System.out.println("最大值" + max);
    // 逐位循环 1-> 10->100
    for (int step = 1; max / step > 0; step *= 10) {
        // 个 十 百 个位时除以1 十位时除以10...
        // 创建桶并初始化（桶的下标 0~9）
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++) {
            buckets.add(i, new ArrayList());
        }
        // 将数据存储在buckets中
        for (int value : arr) {
            //获取指定位上的数，并放入指定桶里
            buckets.get((value / step) % 10).add(value);
        }
        //将每一次排序的结果复制到arr数组中
        int k=0;
        for(ArrayList<Integer> list : buckets) {
            for(Integer num : list) {
                arr[k++]=num;
            }
        }

    }

}

算法（一）-算法思想
一、算法思想介绍常用的算法包含但不限于以下几种：分治：分而治之，将问题拆解为形式相同子问题处理，然后合并为...
字符串匹配算法总结
面写过一篇字符串匹配算法，总共涉及BF算法，RK算法，BM算法，还有一种算法是KMP算法。这几种算法思想和代码我都...
关于GC（二）关于回收算法
引用计数算法可达性算法2.1 标记清除算法2.2 复制算法2.3 标记整理算法一、引用计数器算法算法实现简...
iOS证书相关概念梳理
非对称加密 RSA算法原理（一）RSA算法原理（二）摘要算法另一个神奇的算法就是摘要算法。摘要算法是指，可以将...
LruCache原理和源码分析（一）
一、Lru算法 Lru算法：最近最少使用算法；算法的核心关键类是LinkedHashMap。基本算法：将key...
记录数据结构与算法的学习之路 -----005.BF算法与RK算
1.BF算法 1.1 定义 BF算法，即暴风算法，也有人称为朴素算法、暴力算法。BF算法是一种做字符串匹配的算法。...
JVM读书笔记-垃圾回收算法-06
垃圾回收算法一共分为四种标记-清除算法、复制算法、标记-整理算法、分代收集算法标记-清除算法标记清除算法是最开...
面试官：限流算法有哪些？
限流的实现算法有很多，但常见的限流算法有三种：计数器算法、漏桶算法和令牌桶算法。一、计数器算法计数器算法是在一...
匈牙利算法
算法思想算法流程算法步骤算法实现 python 算法应用
Algorithm进阶计划 -- LRU 与 LFU 算法
LRU 与 LFU 算法LRU 算法LFU 算法 1. LRU 算法 LRU 算法是一种缓存淘汰策略，是 Leas...