复杂度 相关概念
时间复杂度与时间效率：O(1) < O(log2N) < O(n) < O(N * log2N) < O(N2) < O(N3) < 2N < 3N < N! 一般来说，前四个效率比较高，中间两个差强人意，后三个比较差（只要N比较大，这个算法就动不了了）。 常数阶int sum = 0,n = 100; //执行一次 sum = (1+n)*n/2; //执行一次 System.out.println (sum); //执行一次上面算法的运行的次数的函数为 f(n)=3，根据推导大 O 阶的规则 1，我们需要将常数 3 改为 1，则这个算法的时间复杂度为 O(1)。如果 sum=(1+n)*n/2 这条语句再执行 10 遍，因为这与问题大小 n 的值并没有关系，所以这个算法的时间复杂度仍旧是 O(1)，我们可以称之为常数阶。 线性阶线性阶主要要分析循环结构的运行情况，如下所示： 上面算法循环体中的代码执行了n次，因此时间复杂度为O(n)。 对数阶接着看如下代码： int number = 1;while (number < n) { number = number * 2; //时间复杂度为O(1)的算法 ...}可以看出上面的代码，随着 number 每次乘以 2 后，都会越来越接近 n，当 number 不小于 n 时就会退出循环。假设循环的次数为 X，则由 2^x=n 得出 x=log₂n，因此得出这个算法的时间复杂度为 O(logn)。 平方阶下面的代码是循环嵌套： 内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，现在经过外层循环n次，那么这段算法的时间复杂度则为O(n²)。 算法思想 分治(Divide and Conquer)分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。顾名思义，分而治之。一般分为以下三个过程：
比较经典的应用就是归并排序 (Merge Sort) 以及快速排序 (Quick Sort) 等。我们来从归并排序理解分治思想，归并排序就是将待排序数组不断二分为规模更小的子问题处理，再将处理好的子问题合并起来。 贪心(Greedy)贪心算法是动态规划算法的一个子集，可以更高效解决一部分更特殊的问题。实际上，用贪心算法解决问题的思路，并不总能给出最优解。因为它在每一步的决策中，选择目前最优策略，不考虑全局是不是最优。 贪心算法+双指针求解
回溯(Backtracking)使用回溯法进行求解，回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。究其本质，其实就是枚举。
动态规划(Dynamic Programming)虽然动态规划的最终版本 (降维再去维) 大都不是递归，但解题的过程还是离开不递归的。新手可能会觉得动态规划思想接受起来比较难，确实，动态规划求解问题的过程不太符合人类常规的思维方式，我们需要切换成机器思维。使用动态规划思想解题，首先要明确动态规划的三要素。动态规划三要素：
查找算法顺序查找就是一个一个依次查找。 二分查找二分查找又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。如果待查值小于候选区中间值，则只需比较中间值左边的元素，减半查找范围。依次类推依次减半。
 JAVA代码如下： /** * 执行递归二分查找，返回第一次出现该值的位置 * * @param array 已排序的数组 * @param start 开始位置，如：0 * @param end 结束位置，如：array.length-1 * @param findValue 需要找的值 * @return 值在数组中的位置，从0开始。找不到返回-1 */public static int searchRecursive(int[] array, int start, int end, int findValue) { // 如果数组为空，直接返回-1，即查找失败 if (array == null) { return -1; } if (start <= end) { // 中间位置 int middle = (start + end) / 1; // 中值 int middleValue = array[middle]; if (findValue == middleValue) { // 等于中值直接返回 return middle; } else if (findValue < middleValue) { // 小于中值时在中值前面找 return searchRecursive(array, start, middle - 1, findValue); } else { // 大于中值在中值后面找 return searchRecursive(array, middle + 1, end, findValue); } } else { // 返回-1，即查找失败 return -1; }}/** * 循环二分查找，返回第一次出现该值的位置 * * @param array 已排序的数组 * @param findValue 需要找的值 * @return 值在数组中的位置，从0开始。找不到返回-1 */public static int searchLoop(int[] array, int findValue) { // 如果数组为空，直接返回-1，即查找失败 if (array == null) { return -1; } // 起始位置 int start = 0; // 结束位置 int end = array.length - 1; while (start <= end) { // 中间位置 int middle = (start + end) / 2; // 中值 int middleValue = array[middle]; if (findValue == middleValue) { // 等于中值直接返回 return middle; } else if (findValue < middleValue) { // 小于中值时在中值前面找 end = middle - 1; } else { // 大于中值在中值后面找 start = middle + 1; } } // 返回-1，即查找失败 return -1;}插值查找插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。将折半查找中的求mid索引的公式，low表示左边索引left，high表示右边索引right，key就是前面我们讲的findVal。  注意事项
斐波那契查找黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。斐波那契数列{1, 1,2, 3, 5, 8, 13,21, 34, 55 }发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618。 斐波那契查找原理与前两种相似，仅仅改变了中间结点(mid)的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1(F代表斐波那契数列)，如下图所示：  JAVA代码如下： /** * 因为后面我们mid=low+F(k-1)-1，需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列 * 非递归方法得到一个斐波那契数列 * * @return */private static int[] getFibonacci() { int[] fibonacci = new int[20]; fibonacci[0] = 1; fibonacci[1] = 1; for (int i = 2; i < fibonacci.length; i++) { fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]; } return fibonacci;}/** * 编写斐波那契查找算法 * 使用非递归的方式编写算法 * * @param arr 数组 * @param findValue 我们需要查找的关键码(值) * @return 返回对应的下标，如果没有-1 */public static int fibonacciSearch(int[] arr, int findValue) { int low = 0; int high = arr.length - 1; int k = 0;// 表示斐波那契分割数值的下标 int mid = 0;// 存放mid值 int[] fibonacci = getFibonacci();// 获取到斐波那契数列 // 获取到斐波那契分割数值的下标 while (high > fibonacci[k] - 1) { k++; } // 因为 fibonacci[k] 值可能大于 arr 的 长度，因此我们需要使用Arrays类，构造一个新的数组 int[] temp = Arrays.copyOf(arr, fibonacci[k]); // 实际上需求使用arr数组最后的数填充 temp for (int i = high + 1; i < temp.length; i++) { temp[i] = arr[high]; } // 使用while来循环处理，找到我们的数 findValue while (low <= high) { mid = low + fibonacci[k] - 1; if (findValue < temp[mid]) { high = mid - 1; k--; } else if (findValue > temp[mid]) { low = mid + 1; k++; } else { return Math.min(mid, high); } } return -1;}搜素算法深度优先搜索(DFS)深度优先搜索（Depth-First Search / DFS）是一种优先遍历子节点而不是回溯的算法。  DFS解决的是连通性的问题。即给定两个点，一个是起始点，一个是终点，判断是不是有一条路径能从起点连接到终点。起点和终点，也可以指的是某种起始状态和最终的状态。问题的要求并不在乎路径是长还是短，只在乎有还是没有。 代码案例 广度优先搜索(BFS)广度优先搜索（Breadth-First Search / BFS）是优先遍历邻居节点而不是子节点的图遍历算法。  BFS一般用来解决最短路径的问题。和深度优先搜索不同，广度优先的搜索是从起始点出发，一层一层地进行，每层当中的点距离起始点的步数都是相同的，当找到了目的地之后就可以立即结束。广度优先的搜索可以同时从起始点和终点开始进行，称之为双端 BFS。这种算法往往可以大大地提高搜索的效率。 代码案例 /** * Breadth-First Search(BFS) * <p> * 从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。 * <p> * 数据结构：队列 * 父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可 * */public class BreadthFirstSearch { /** * 树节点 * * @param <V> */ @Data @NoArgsConstructor @AllArgsConstructor public static class TreeNode<V> { private V value; private List<TreeNode<V>> childList; } /** * 模型： * .......A * ...../ \ * ....B C * .../ \ / \ * ..D E F G * ./ \ / \ * H I J K */ public static void main(String[] args) { TreeNode<String> treeNodeA = new TreeNode<>('A', new ArrayList<>()); TreeNode<String> treeNodeB = new TreeNode<>('B', new ArrayList<>()); TreeNode<String> treeNodeC = new TreeNode<>('C', new ArrayList<>()); TreeNode<String> treeNodeD = new TreeNode<>('D', new ArrayList<>()); TreeNode<String> treeNodeE = new TreeNode<>('E', new ArrayList<>()); TreeNode<String> treeNodeF = new TreeNode<>('F', new ArrayList<>()); TreeNode<String> treeNodeG = new TreeNode<>('G', new ArrayList<>()); TreeNode<String> treeNodeH = new TreeNode<>('H', new ArrayList<>()); TreeNode<String> treeNodeI = new TreeNode<>('I', new ArrayList<>()); TreeNode<String> treeNodeJ = new TreeNode<>('J', new ArrayList<>()); TreeNode<String> treeNodeK = new TreeNode<>('K', new ArrayList<>()); // A->B,C treeNodeA.getChildList().add(treeNodeB); treeNodeA.getChildList().add(treeNodeC); // B->D,E treeNodeB.getChildList().add(treeNodeD); treeNodeB.getChildList().add(treeNodeE); // C->F,G treeNodeC.getChildList().add(treeNodeF); treeNodeC.getChildList().add(treeNodeG); // D->H,I treeNodeD.getChildList().add(treeNodeH); treeNodeD.getChildList().add(treeNodeI); // G->J,K treeNodeG.getChildList().add(treeNodeJ); treeNodeG.getChildList().add(treeNodeK); System.out.println('递归方式'); bfsRecursive(Arrays.asList(treeNodeA), 0); System.out.println(); System.out.println('非递归方式'); bfsNotRecursive(treeNodeA); } /** * 递归遍历 * * @param children * @param depth * @param <V> */ public static <V> void bfsRecursive(List<TreeNode<V>> children, int depth) { List<TreeNode<V>> thisChildren, allChildren = new ArrayList<>(); for (TreeNode<V> child : children) { // 打印节点值以及深度 System.out.print('-->[' + child.getValue().toString() + ',' + depth + ']'); thisChildren = child.getChildList(); if (thisChildren != null && thisChildren.size() > 0) { allChildren.addAll(thisChildren); } } if (allChildren.size() > 0) { bfsRecursive(allChildren, depth + 1); } } /** * 非递归遍历 * * @param tree * @param <V> */ public static <V> void bfsNotRecursive(TreeNode<V> tree) { if (tree != null) { // 跟上面一样，使用 Map 也只是为了保存树的深度，没这个需要可以不用 Map Queue<Map<TreeNode<V>, Integer>> queue = new ArrayDeque<>(); Map<TreeNode<V>, Integer> root = new HashMap<>(); root.put(tree, 0); queue.offer(root); while (!queue.isEmpty()) { Map<TreeNode<V>, Integer> itemMap = queue.poll(); TreeNode<V> node = itemMap.keySet().iterator().next(); int depth = itemMap.get(node); //打印节点值以及深度 System.out.print('-->[' + node.getValue().toString() + ',' + depth + ']'); if (node.getChildList() != null && !node.getChildList().isEmpty()) { for (TreeNode<V> child : node.getChildList()) { Map<TreeNode<V>, Integer> map = new HashMap<>(); map.put(child, depth + 1); queue.offer(map); } } } } }}迪杰斯特拉算法(Dijkstra)迪杰斯特拉(Dijkstra)算法 是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是'起点s到该顶点的路径'。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。 操作步骤
迪杰斯特拉算法图解  以上图G4为例，来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)：  代码案例 排序算法十种常见排序算法可以分为两大类：
 冒泡排序（Bubble Sort）循环遍历多次每次从前往后把大元素往后调，每次确定一个最大(最小)元素，多次后达到排序序列。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。  算法步骤
代码实现 /** * 冒泡排序 * 描述：每轮连续比较相邻的两个数，前数大于后数，则进行替换。每轮完成后，本轮最大值已被移至最后 * * @param arr 待排序数组 */public static int[] bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { // 每次比较2个相邻的数,前一个小于后一个 if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return arr;}以下是冒泡排序算法复杂度:
冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n)。平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1)。 Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。 选择排序（Selection Sort）选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 算法描述 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
代码实现 以下是选择排序复杂度:
选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。 插入排序（Insertion Sort）插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序由于操作不尽相同，可分为 直接插入排序、折半插入排序(又称二分插入排序)、链表插入排序、希尔排序 。 算法描述 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
代码实现 /** * 直接插入排序 * 1. 从第一个元素开始，该元素可以认为已经被排序 * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 * 5. 将新元素插入到该位置后 * 6. 重复步骤2~5 * * @param arr 待排序数组 */ public static int[] insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { // 取出下一个元素，在已经排序的元素序列中从后向前扫描 int temp = arr[i]; for (int j = i; j >= 0; j--) { if (j > 0 && arr[j - 1] > temp) { // 如果该元素（已排序）大于取出的元素temp，将该元素移到下一位置 arr[j] = arr[j - 1]; } else { // 将新元素插入到该位置后 arr[j] = temp; break; } } } return arr; } /** * 折半插入排序 * 往前找合适的插入位置时采用二分查找的方式，即折半插入 * 交换次数较多的实现 * * @param arr 待排序数组 */ public static int[] insertionBinarySort(int[] arr) { for (int i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { int tmp = arr[i]; // 记录搜索范围的左边界,右边界 int low = 0, high = i - 1; while (low <= high) { // 记录中间位置Index int mid = (low + high) / 2; // 比较中间位置数据和i处数据大小，以缩小搜索范围 if (arr[mid] < tmp) { // 左边指针则一只中间位置+1 low = mid + 1; } else { // 右边指针则一只中间位置-1 high = mid - 1; } } // 将low~i处数据整体向后移动1位 for (int j = i; j > low; j--) { arr[j] = arr[j - 1]; } arr[low] = tmp; } } return arr; }插入排序复杂度：
Tips：由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 希尔排序（Shell Sort）1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 算法描述 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
代码实现 以下是希尔排序复杂度:
Tips：希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。 归并排序（Merging Sort）简介 基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 场景使用 应用场景：内存少的时候使用，可以进行并行计算的时候使用。 步骤：
算法描述 a.递归法（假设序列共有n个元素） ①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素； ②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素； ③. 重复步骤②，直到所有元素排序完毕。 b.迭代法 ①. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 ②. 设定两个指针，最初位置分别为两个已经排序序列的起始位置 ③. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 ④. 重复步骤③直到某一指针到达序列尾 ⑤. 将另一序列剩下的所有元素直接复制到合并序列尾 代码实现 /** * 归并排序（递归） * ①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素； * ②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素； * ③. 重复步骤②，直到所有元素排序完毕。 * * @param arr 待排序数组 */ public static int[] mergeSort(int[] arr) { return mergeSort(arr, 0, arr.length - 1); } private static int[] mergeSort(int[] arr, int low, int high) { int center = (high + low) / 2; if (low < high) { // 递归，直到low==high，也就是数组已不能再分了， mergeSort(arr, low, center); mergeSort(arr, center + 1, high); // 当数组不能再分，开始归并排序 mergeSort(arr, low, center, high); } return arr; } private static void mergeSort(int[] a, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; // 把较小的数先移到新数组中 while (i <= mid && j <= high) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } // 把左边剩余的数移入数组 while (i <= mid) { temp[k++] = a[i++]; } // 把右边边剩余的数移入数组 while (j <= high) { temp[k++] = a[j++]; } // 把新数组中的数覆盖nums数组 for (int x = 0; x < temp.length; x++) { a[x + low] = temp[x]; } }以下是归并排序算法复杂度:
从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn，, 又每步都是一个普通的合并子数组的过程， 时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。 Tips：和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。 快速排序（Quick Sort）快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 算法描述 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
代码实现 以下是快速排序算法复杂度:
快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高。 Tips: 同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定。 基数排序（Radix Sort）基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。 算法描述
代码实现 /** * 基数排序（LSD 从低位开始） * 基数排序适用于： * (1)数据范围较小，建议在小于1000 * (2)每个数值都要大于等于0 * <p> * ①. 取得数组中的最大数，并取得位数； * ②. arr为原始数组，从最低位开始取每个位组成radix数组； * ③. 对radix进行计数排序（利用计数排序适用于小范围数的特点）； * * @param arr 待排序数组 */public static int[] radixSort(int[] arr) { // 取得数组中的最大数，并取得位数 int max = 0; for (int item : arr) { if (max < item) { max = item; } } int maxDigit = 1; while (max / 10 > 0) { maxDigit++; max = max / 10; } // 申请一个桶空间 int[][] buckets = new int[10][arr.length]; int base = 10; // 从低位到高位，对每一位遍历，将所有元素分配到桶中 for (int i = 0; i < maxDigit; i++) { // 存储各个桶中存储元素的数量 int[] bktLen = new int[10]; // 分配：将所有元素分配到桶中 for (int value : arr) { int whichBucket = (value % base) / (base / 10); buckets[whichBucket][bktLen[whichBucket]] = value; bktLen[whichBucket]++; } // 收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞 int k = 0; for (int b = 0; b < buckets.length; b++) { for (int p = 0; p < bktLen[b]; p++) { arr[k++] = buckets[b][p]; } } base *= 10; } return arr;}以下是基数排序算法复杂度，其中k为最大数的位数：
其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r))。基数排序更适合用于对时间, 字符串等这些整体权值未知的数据进行排序。 Tips: 基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。 堆排序（Heap Sort）对于堆排序，首先是建立在堆的基础上，堆是一棵完全二叉树，还要先认识下大根堆和小根堆，完全二叉树中所有节点均大于(或小于)它的孩子节点，所以这里就分为两种情况：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。 算法描述
动图演示 代码实现
Tips: 由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列. 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序. 计数排序（Counting Sort）计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 算法描述
动图演示 代码实现 /** * 计数排序算法 * * @param arr 待排序数组 */ public static int[] countingSort(int[] arr) { // 得到数列的最大值与最小值，并算出差值d int max = arr[0]; int min = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } if (arr[i] < min) { min = arr[i]; } } int d = max - min; // 创建统计数组并计算统计对应元素个数 int[] countArray = new int[d + 1]; for (int value : arr) { countArray[value - min]++; } // 统计数组变形，后面的元素等于前面的元素之和 int sum = 0; for (int i = 0; i < countArray.length; i++) { sum += countArray[i]; countArray[i] = sum; } // 倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组 int[] sortedArray = new int[arr.length]; for (int i = arr.length - 1; i >= 0; i--) { sortedArray[countArray[arr[i] - min] - 1] = arr[i]; countArray[arr[i] - min]--; } return sortedArray; }算法分析 计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。 桶排序（Bucket Sort）桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。 算法描述
代码实现 算法分析 桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。 |
|
|
