复杂度
相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数
时间复杂度与时间效率：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)，我们可以称之为常数阶。
线性阶
线性阶主要要分析循环结构的运行情况，如下所示：
for (int i = 0; i < n; i++) {
//时间复杂度为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)。
平方阶
下面的代码是循环嵌套：
for (int i = 0; i < n; i++) {
for(int j = 0; j < n; i++) {
//复杂度为O(1)的算法
...
}
}内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，现在经过外层循环n次，那么这段算法的时间复杂度则为O(n²)。
算法思想
分治(Divide and Conquer)
分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。顾名思义，分而治之。一般分为以下三个过程：
- 分解：将原问题分解成一系列子问题
- 解决：递归求解各个子问题，若子问题足够小，则直接求解
- 合并：将子问题的结果合并成原问题
比较经典的应用就是归并排序 (Merge Sort) 以及快速排序 (Quick Sort) 等。我们来从归并排序理解分治思想，归并排序就是将待排序数组不断二分为规模更小的子问题处理，再将处理好的子问题合并起来。
贪心(Greedy)
贪心算法是动态规划算法的一个子集，可以更高效解决一部分更特殊的问题。实际上，用贪心算法解决问题的思路，并不总能给出最优解。因为它在每一步的决策中，选择目前最优策略，不考虑全局是不是最优。
贪心算法+双指针求解
- 给一个孩子的饼干应当尽量小并且能满足孩子，大的留来满足胃口大的孩子
- 因为胃口小的孩子最容易得到满足，所以优先满足胃口小的孩子需求
- 按照从小到大的顺序使用饼干尝试是否可满足某个孩子
- 当饼干 j >= 胃口 i 时，饼干满足胃口，更新满足的孩子数并移动指针 i++ j++ res++
- 当饼干 j < 胃口 i 时，饼干不能满足胃口，需要换大的 j++
回溯(Backtracking)
使用回溯法进行求解，回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。究其本质，其实就是枚举。
- 如果没有更多的数字需要被输入，说明当前的组合已经产生
- 如果还有数字需要被输入：遍历下一个数字所对应的所有映射的字母将当前的字母添加到组合最后，也就是 str + tmp[r]
动态规划(Dynamic Programming)
虽然动态规划的最终版本 (降维再去维) 大都不是递归，但解题的过程还是离开不递归的。新手可能会觉得动态规划思想接受起来比较难，确实，动态规划求解问题的过程不太符合人类常规的思维方式，我们需要切换成机器思维。使用动态规划思想解题，首先要明确动态规划的三要素。动态规划三要素：
- 重叠子问题：切换机器思维，自底向上思考
- 最优子结构：子问题的最优解能够推出原问题的优解
- 状态转移方程：dp[n] = dp[n-1] + dp[n-2]
查找算法
顺序查找
就是一个一个依次查找。
二分查找
二分查找又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。如果待查值小于候选区中间值，则只需比较中间值左边的元素，减半查找范围。依次类推依次减半。
- 二分查找的前提：列表有序
- 二分查找的优点：查找速度快
- 二分查找的时间复杂度为：O(logn)
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。
注意事项
- 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快
- 关键字分布不均匀的情况下，该方法不一定比折半查找要好
/**
* 插值查找
*
* @param arr 已排序的数组
* @param left 开始位置，如：0
* @param right 结束位置，如：array.length-1
* @param findValue
* @return
*/
public static int insertValueSearch(int[] arr, int left, int right, int findValue) {
//注意：findVal < arr[0] 和 findVal > arr[arr.length - 1] 必须需要, 否则我们得到的 mid 可能越界
if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {
return -1;
}
// 求出mid, 自适应
int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
int midValue = arr[mid];
if (findValue > midValue) {
// 向右递归
return insertValueSearch(arr, mid + 1, right, findValue);
} else if (findValue < midValue) {
// 向左递归
return insertValueSearch(arr, left, mid - 1, findValue);
} else {
return mid;
}
}斐波那契查找
黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是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解决的是连通性的问题。即给定两个点，一个是起始点，一个是终点，判断是不是有一条路径能从起点连接到终点。起点和终点，也可以指的是某种起始状态和最终的状态。问题的要求并不在乎路径是长还是短，只在乎有还是没有。
代码案例
/**
* Depth-First Search(DFS)
*
* 从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。
* 数据结构：栈
* 父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可
*
*/
public class DepthFirstSearch {
/**
* 树节点
*
* @param <V>
*/
@Data
@NoArgsConstructor
@AllArgsConstructor
public static class TreeNode<V> {
private V value;
private List<TreeNode<V>> childList;
// 二叉树节点支持如下
public TreeNode<V> getLeft() {
if (childList == null || childList.isEmpty()) {
return null;
}
return childList.get(0);
}
public TreeNode<V> getRight() {
if (childList == null || childList.isEmpty()) {
return null;
}
return childList.get(1);
}
}
/**
* 模型：
* .......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("非递归方式");
dfsNotRecursive(treeNodeA);
System.out.println();
System.out.println("前续遍历");
dfsPreOrderTraversal(treeNodeA, 0);
System.out.println();
System.out.println("后续遍历");
dfsPostOrderTraversal(treeNodeA, 0);
System.out.println();
System.out.println("中续遍历");
dfsInOrderTraversal(treeNodeA, 0);
}
/**
* 非递归方式
*
* @param tree
* @param <V>
*/
public static <V> void dfsNotRecursive(TreeNode<V> tree) {
if (tree != null) {
// 次数之所以用 Map 只是为了保存节点的深度，如果没有这个需求可以改为 Stack<TreeNode<V>>
Stack<Map<TreeNode<V>, Integer>> stack = new Stack<>();
Map<TreeNode<V>, Integer> root = new HashMap<>();
root.put(tree, 0);
stack.push(root);
while (!stack.isEmpty()) {
Map<TreeNode<V>, Integer> item = stack.pop();
TreeNode<V> node = item.keySet().iterator().next();
int depth = item.get(node);
// 打印节点值以及深度
System.out.print("-->[" + node.getValue().toString() + "," + depth + "]");
if (node.getChildList() != null && !node.getChildList().isEmpty()) {
for (TreeNode<V> treeNode : node.getChildList()) {
Map<TreeNode<V>, Integer> map = new HashMap<>();
map.put(treeNode, depth + 1);
stack.push(map);
}
}
}
}
}
/**
* 递归前序遍历方式
* <p>
* 前序遍历(Pre-Order Traversal) ：指先访问根，然后访问子树的遍历方式，二叉树则为：根->左->右
*
* @param tree
* @param depth
* @param <V>
*/
public static <V> void dfsPreOrderTraversal(TreeNode<V> tree, int depth) {
if (tree != null) {
// 打印节点值以及深度
System.out.print("-->[" + tree.getValue().toString() + "," + depth + "]");
if (tree.getChildList() != null && !tree.getChildList().isEmpty()) {
for (TreeNode<V> item : tree.getChildList()) {
dfsPreOrderTraversal(item, depth + 1);
}
}
}
}
/**
* 递归后序遍历方式
* 后序遍历(Post-Order Traversal)：指先访问子树，然后访问根的遍历方式，二叉树则为：左->右->根
*
* @param tree
* @param depth
* @param <V>
*/
public static <V> void dfsPostOrderTraversal(TreeNode<V> tree, int depth) {
if (tree != null) {
if (tree.getChildList() != null && !tree.getChildList().isEmpty()) {
for (TreeNode<V> item : tree.getChildList()) {
dfsPostOrderTraversal(item, depth + 1);
}
}
// 打印节点值以及深度
System.out.print("-->[" + tree.getValue().toString() + "," + depth + "]");
}
}
/**
* 递归中序遍历方式
* 中序遍历(In-Order Traversal)：指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式，二叉树则为：左->根->右
*
* @param tree
* @param depth
* @param <V>
*/
public static <V> void dfsInOrderTraversal(TreeNode<V> tree, int depth) {
if (tree.getLeft() != null) {
dfsInOrderTraversal(tree.getLeft(), depth + 1);
}
// 打印节点值以及深度
System.out.print("-->[" + tree.getValue().toString() + "," + depth + "]");
if (tree.getRight() != null) {
dfsInOrderTraversal(tree.getRight(), depth + 1);
}
}
}广度优先搜索(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中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。
操作步骤
- 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]
- U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k
- 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离
- 重复步骤(2)和(3)，直到遍历完所有顶点
迪杰斯特拉算法图解
以上图G4为例，来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)：
代码案例
public class Dijkstra {
// 代表正无穷
public static final int M = 10000;
public static String[] names = new String[]{"A", "B", "C", "D", "E", "F", "G",};
public static void main(String[] args) {
// 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
// A -> A 距离为0, 常量M 为正无穷
int[][] weight1 = {
{0, 12, M, M, M, 16, 14},
{12, 0, 10, M, M, 7, M},
{M, 10, 0, 3, 5, 6, M},
{M, M, 3, 0, 4, M, M},
{M, M, 5, 4, 0, 2, 8},
{16, 7, 6, M, 2, 0, 9},
{14, M, M, M, 8, 9, 0}
};
int start = 0;
int[] shortPath = dijkstra(weight1, start);
System.out.println("===============");
for (int i = 0; i < shortPath.length; i++) {
System.out.println("从" + names[start] + "出发到" + names[i] + "的最短距离为：" + shortPath[i]);
}
}
/**
* Dijkstra算法
*
* @param weight 图的权重矩阵
* @param start 起点编号start（从0编号，顶点存在数组中）
* @return 返回一个int[] 数组，表示从start到它的最短路径长度
*/
public static int[] dijkstra(int[][] weight, int start) {
// 顶点个数
int n = weight.length;
// 标记当前该顶点的最短路径是否已经求出,1表示已求出
int[] visited = new int[n];
// 保存start到其他各点的最短路径
int[] shortPath = new int[n];
// 保存start到其他各点最短路径的字符串表示
String[] path = new String[n];
for (int i = 0; i < n; i++) {
path[i] = names[start] + "-->" + names[i];
}
// 初始化，第一个顶点已经求出
shortPath[start] = 0;
visited[start] = 1;
// 要加入n-1个顶点
for (int count = 1; count < n; count++) {
// 选出一个距离初始顶点start最近的未标记顶点
int k = -1;
int dMin = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (visited[i] == 0 && weight[start][i] < dMin) {
dMin = weight[start][i];
k = i;
}
}
// 将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
shortPath[k] = dMin;
visited[k] = 1;
// 以k为中间点，修正从start到未访问各点的距离
for (int i = 0; i < n; i++) {
// 如果 '起始点到当前点距离' + '当前点到某点距离' < '起始点到某点距离', 则更新
if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) {
weight[start][i] = weight[start][k] + weight[k][i];
path[i] = path[k] + "-->" + names[i];
}
}
}
for (int i = 0; i < n; i++) {
System.out.println("从" + names[start] + "出发到" + names[i] + "的最短路径为：" + path[i]);
}
return shortPath;
}
}排序算法
十种常见排序算法可以分为两大类：
- 非线性时间比较类排序
- 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
- 线性时间非比较类排序
- 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
冒泡排序（Bubble Sort）
循环遍历多次每次从前往后把大元素往后调，每次确定一个最大(最小)元素，多次后达到排序序列。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 重复步骤1~3，直到排序完成
代码实现
/**
* 冒泡排序
* 描述：每轮连续比较相邻的两个数，前数大于后数，则进行替换。每轮完成后，本轮最大值已被移至最后
*
* @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;
}以下是冒泡排序算法复杂度:
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
O(n²) | O(n) | O(n²) | O(1) |
冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n)。平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1)。
Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。
选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
- 初始状态：无序区为R[1..n]，有序区为空
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
- n-1趟结束，数组有序化了
代码实现
/**
* 选择排序
* 描述：每轮选择出最小值，然后依次放置最前面
*
* @param arr 待排序数组
*/
public static int[] selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 选最小的记录
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
// 内层循环结束后，即找到本轮循环的最小的数以后，再进行交换：交换a[i]和a[min]
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
return arr;
}以下是选择排序复杂度:
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
O(n²) | O(n²) | O(n²) | O(1) |
选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。
插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序由于操作不尽相同，可分为 直接插入排序、折半插入排序(又称二分插入排序)、链表插入排序、希尔排序 。
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
代码实现
/**
* 直接插入排序
* 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;
}插入排序复杂度：
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
O(n²) | O(n) | O(n²) | O(1) |
Tips：由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
希尔排序（Shell Sort）
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1
- 按增量序列个数k，对序列进行k 趟排序
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
代码实现
/**
* 希尔排序
* 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
* 2. 按增量序列个数k，对序列进行k 趟排序；
* 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
* 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
*
* @param arr 待排序数组
*/
public static int[] shellSort(int[] arr) {
int gap = arr.length / 2;
// 不断缩小gap，直到1为止
for (; gap > 0; gap /= 2) {
// 使用当前gap进行组内插入排序
for (int j = 0; (j + gap) < arr.length; j++) {
for (int k = 0; (k + gap) < arr.length; k += gap) {
if (arr[k] > arr[k + gap]) {
int temp = arr[k + gap];
arr[k + gap] = arr[k];
arr[k] = temp;
}
}
}
}
return arr;
}以下是希尔排序复杂度:
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(1) |
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];
}
}以下是归并排序算法复杂度:
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(n) |
从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn，, 又每步都是一个普通的合并子数组的过程， 时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。
Tips：和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
快速排序（Quick Sort）
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
代码实现
/**
* 快速排序（递归）
* ①. 从数列中挑出一个元素，称为"基准"（pivot）。
* ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* ③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
*
* @param arr 待排序数组
*/
public static int[] quickSort(int[] arr) {
return quickSort(arr, 0, arr.length - 1);
}
private static int[] quickSort(int[] arr, int low, int high) {
if (arr.length <= 0 || low >= high) {
return arr;
}
int left = low;
int right = high;
// 挖坑1：保存基准的值
int temp = arr[left];
while (left < right) {
// 坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
while (left < right && arr[right] >= temp) {
right--;
}
arr[left] = arr[right];
// 坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
while (left < right && arr[left] <= temp) {
left++;
}
arr[right] = arr[left];
}
// 基准值填补到坑3中，准备分治递归快排
arr[left] = temp;
quickSort(arr, low, left - 1);
quickSort(arr, left + 1, high);
return arr;
}
/**
* 快速排序（非递归）
* ①. 从数列中挑出一个元素，称为"基准"（pivot）。
* ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* ③. 把分区之后两个区间的边界（low和high）压入栈保存，并循环①、②步骤
*
* @param arr 待排序数组
*/
public static int[] quickSortByStack(int[] arr) {
Stack<Integer> stack = new Stack<>();
// 初始状态的左右指针入栈
stack.push(0);
stack.push(arr.length - 1);
while (!stack.isEmpty()) {
// 出栈进行划分
int high = stack.pop();
int low = stack.pop();
int pivotIdx = partition(arr, low, high);
// 保存中间变量
if (pivotIdx > low) {
stack.push(low);
stack.push(pivotIdx - 1);
}
if (pivotIdx < high && pivotIdx >= 0) {
stack.push(pivotIdx + 1);
stack.push(high);
}
}
return arr;
}
private static int partition(int[] arr, int low, int high) {
if (arr.length <= 0) return -1;
if (low >= high) return -1;
int l = low;
int r = high;
// 挖坑1：保存基准的值
int pivot = arr[l];
while (l < r) {
// 坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
while (l < r && arr[r] >= pivot) {
r--;
}
arr[l] = arr[r];
// 坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
while (l < r && arr[l] <= pivot) {
l++;
}
arr[r] = arr[l];
}
// 基准值填补到坑3中，准备分治递归快排
arr[l] = pivot;
return l;
}以下是快速排序算法复杂度:
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
O(nlog₂n) | O(nlog₂n) | O(n²) | O(1)（原地分区递归版） |
快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高。
Tips: 同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定。
基数排序（Radix Sort）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
算法描述
- 取得数组中的最大数，并取得位数
- arr为原始数组，从最低位开始取每个位组成radix数组
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）
代码实现
/**
* 基数排序（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为最大数的位数：
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
O(d*(n+r)) | O(d*(n+r)) | O(d*(n+r)) | O(n+r) |
其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r))。基数排序更适合用于对时间, 字符串等这些整体权值未知的数据进行排序。
Tips: 基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。
堆排序（Heap Sort）
对于堆排序，首先是建立在堆的基础上，堆是一棵完全二叉树，还要先认识下大根堆和小根堆，完全二叉树中所有节点均大于(或小于)它的孩子节点，所以这里就分为两种情况：
- 如果所有节点「大于」孩子节点值，那么这个堆叫做「大根堆」，堆的最大值在根节点
- 如果所有节点「小于」孩子节点值，那么这个堆叫做「小根堆」，堆的最小值在根节点
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。
算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
动图演示
代码实现
/**
* 堆排序算法
*
* @param arr 待排序数组
*/
public static int[] heapSort(int[] arr) {
// 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
// 将最大的节点放在堆尾，然后从根节点重新调整
for (int j = arr.length - 1; j > 0; j--) {
// 交换
int temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
// 完成将以i对应的非叶子结点的树调整成大顶堆
adjustHeap(arr, 0, j);
}
return arr;
}
/**
* 功能： 完成将以i对应的非叶子结点的树调整成大顶堆
*
* @param arr 待排序数组
* @param i 表示非叶子结点在数组中索引
* @param length 表示对多少个元素继续调整， length 是在逐渐的减少
*/
private static void adjustHeap(int[] arr, int i, int length) {
// 先取出当前元素的值，保存在临时变量
int temp = arr[i];
//开始调整。说明：1. k = i * 2 + 1 k 是 i结点的左子结点
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
// 说明左子结点的值小于右子结点的值
if (k + 1 < length && arr[k] < arr[k + 1]) {
// k 指向右子结点
k++;
}
// 如果子结点大于父结点
if (arr[k] > temp) {
// 把较大的值赋给当前结点
arr[i] = arr[k];
// i 指向 k,继续循环比较
i = k;
} else {
break;
}
}
//当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)。将temp值放到调整后的位置
arr[i] = temp;
}平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
O(n \log_{2}n) | O(n \log_{2}n) | O(n \log_{2}n) | O(1) |
Tips: 由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列. 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序.
计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法描述
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
动图演示
代码实现
/**
* 计数排序算法
*
* @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)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
算法描述
- 设置一个定量的数组当作空桶
- 遍历输入数据，并且把数据一个一个放到对应的桶里去
- 对每个不是空的桶进行排序
- 从不是空的桶里把排好序的数据拼接起来
代码实现
/**
* 桶排序算法
*
* @param arr 待排序数组
*/
public static int[] bucketSort(int[] arr) {
// 计算最大值与最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int value : arr) {
max = Math.max(max, value);
min = Math.min(min, value);
}
// 计算桶的数量
int bucketNum = (max - min) / arr.length + 1;
List<List<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
// 将每个元素放入桶
for (int value : arr) {
int num = (value - min) / (arr.length);
bucketArr.get(num).add(value);
}
// 对每个桶进行排序
for (List<Integer> integers : bucketArr) {
Collections.sort(integers);
}
// 将桶中的元素赋值到原序列
int index = 0;
for (List<Integer> integers : bucketArr) {
for (Integer integer : integers) {
arr[index++] = integer;
}
}
return arr;
}算法分析
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。