一、引课Gitee 项目访问地址：Data Structure And Algorithm
几个经典的算法面试题 1
子串匹配问题：KMP算法汉诺塔问题：分治算法
几个经典的算法面试题 2
八皇后问题：回溯算法马踏棋盘（骑士周游问题）：DFS + 贪心算法优化
内容介绍和授课模式
一般来说程序会使用内存计算框架（如 Spark）和缓存技术（如 Redis）来优化程序
数据结构与算法的关系
数据结构是一门研究组织数据方式的学科
编程中实际遇到的几个问题
线性结构与非线性结构
常见线性结构：一维数组、栈、队列、链表
常见非线性结构：二维数组、多维数组、广义表、树、图
稀疏数组的应用场景
稀疏数组（Sparse Array）的处理方法：
记录数组一共有几行几列，有多少个有效的值把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小存储的规模
稀疏数组转换的思路分析
稀疏数组的代码实现
public int[][] arrayToSparse(int[][] array) {
int rows = array.length;
int cols = array[0].length;
// 获得原数组中的有效数据个数
int dataCount = 0;
for (int[] rowData : array) {
for (int colData : rowData) {
if (colData != 0) {
dataCount++;
}
}
}
// 创建稀疏数组，由于稀疏数组第一行存储原数组行、列、有效数个数信息，故稀疏数组行数 +1
int[][] sparseArray = new int[++dataCount][3];
int sparseCurrentRow = 0;
// 稀疏数组第一行存储原数组行、列、有效数个数信息
sparseArray[sparseCurrentRow][0] = rows;
sparseArray[sparseCurrentRow][1] = cols;
sparseArray[sparseCurrentRow][2] = --dataCount;
// 遍历原数组，将有效数据的坐标信息及值存入稀疏数组中
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int data = array[i][j];
if (data != 0) {
++sparseCurrentRow;
sparseArray[sparseCurrentRow][0] = i;
sparseArray[sparseCurrentRow][1] = j;
sparseArray[sparseCurrentRow][2] = data;
}
}
}
return sparseArray;
}
public int[][] sparseToArray(int[][] sparse) {
if (sparse.length == 0) {
return null;
}
// 从稀疏数组的第一行中获取原数组的大小
int rows = sparse[0][0];
int cols = sparse[0][1];
int[][] array = new int[rows][cols];
// 从稀疏数组的第一行开始遍历，其结构为 row col val
for (int i = 1; i < sparse.length; i++) {
// 给需要恢复的二维数组赋值
array[sparse[i][0]][sparse[i][1]] = sparse[i][2];
}
return array;
}
三、队列
队列的应用场景和介绍
数组模拟队列的思路分析
创建一个类，具有三个属性 rear（尾指针）、front（头指针）、MaxSize 以及添加数据和取出数据的方法
数组模拟队列的代码实现 1
数组模拟队列的代码实现 2
数组模拟循环队列思路分析图
变量的含义做出以下调整：
front：指向队列的第一个元素，初始值为 0
rear：指向队尾元素的下一个元素，初始值为 0
队列满的条件：(rear + 1) % maxSize == front
队列中有效数据的个数 (rear - front + maxSize) % maxSize
数组模拟环形队列实现
package com.bear.queue;
public class CircleArrayQueue {
private final int maxSize;
private final int[] array;
private int front;
private int rear;
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.array = new int[maxSize];
}
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
public boolean isEmpty() {
return front == rear;
}
public void add(int data) {
if (isFull()) {
System.out.println("队列已满，无法添加数据");
return;
}
array[rear] = data;
rear = (rear + 1) % maxSize;
}
public int get() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法取出数据");
}
int temp = array[front];
front = (front + 1) % maxSize;
return temp;
}
public void list() {
if (isEmpty()) {
System.out.println("队列为空，无数据");
return;
}
for (int i = front; i < front + dataSize(); i++) {
int index = i % maxSize;
System.out.printf("array[%d] = %dn", index, array[index]);
}
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无数据");
}
return array[front];
}
public int dataSize() {
return (rear - front + maxSize) % maxSize;
}
}
单链表介绍和内存布局
单链表的创建和遍历分析实现
单链表按顺序插入节点
public void addByOrder(Node head, Node node) {
// 只有头节点，直接添加并返回
if (head.next == null) {
head.next = node;
return;
}
Node current = head;
// 判断新加入的节点是否要添加到第一个位置，若是则直接添加到第一个位置并返回
if (current.next.data > node.data) {
node.next = current.next;
current.next = node;
return;
}
current = current.next;
// 从第一个节点开始遍历整个链表，如果当前节点不指向空且数据比新加入节点的数据小，则当前节点后移，循环寻找新节点的插入位置
while (current.next != null && current.next.data < node.data) {
current = current.next;
}
// 将新节点指向当前节点的下一个节点
node.next = current.next;
// 将当前节点指向新节点
current.next = node;
}
单链表节点的修改
单链表节点的删除和小结
public void delete(Node head, Node node) {
Node current = head;
// 找到需要删除的节点的前一个节点
while (current.next != null && !node.data.equals(current.next.data)) {
current = current.next;
}
// 让当前节点指向当前节点的下下个节点
current.next = current.next.next;
}
单链表新浪面试题
单链表腾讯面试题
单链表的反转：思路 - 定义一个新的链表头节点 reverseHead，遍历原链表的同时以此将每个节点插入到 reverseHead 与 新链表上一个插入节点之间，最后让原链表的 head.next = reverseHead
public void reverse(Node head) {
// 无节点或只有一个节点，无需反转
if (head.next == null || head.next.next == null) {
return;
}
Node reverseHead = new Node(null);
Node cur = head.next;
Node curNext;
while (cur != null) {
// 记录当前节点的下一个节点
curNext = cur.next;
// 将当前节点指向 reverseHead 的下一个节点即所有插入的新节点都在 reverseHead 与上一次插入的节点之间
cur.next = reverseHead.next;
// 将 reverseHead 指向当前节点
reverseHead.next = cur;
// 将记录的节点 curNext 赋值给 cur，继续遍历原链表
cur = curNext;
}
head.next = reverseHead.next;
}
单链表百度面试题
逆序打印链表：
先将原单链表反转，再遍历，破坏了原链表的结构（不推荐）遍历原链表的每个节点并将其放入栈中，后遍历栈
合并两个有序链表，使得合并后的链表依旧有序：定义一个头节点，当两个链表都不为空时获取两个链表的一个节点，比较其值后连接到头节点尾部，指针后移，当某个链表遍历完之后直接将指针指向剩下链表的那个节点
双向链表的增删改查分析图解
单向链表与双向链表的比较：
单向链表不能自我删除，需要借助辅助节点，而双向链表可以自我删除
双向链表的增删改查代码实现
删除关键点，遍历到需要删除的节点 temp
// 将当前节点的上一节点指向当前节点的下一节点
temp.prev.next = temp.next;
// 判断当前节点是否是最后一个节点
if(temp.next != null){
// 将当前节点的下一个节点指向当前节点的上一个节点
temp.next.prev = temp.prev;
}
双向链表功能测试和小结
环形链表介绍和约瑟夫问题
约瑟夫问题分析图解和实现 1
约瑟夫问题分析图解和实现 2
博客链接：Java环形链表解決约瑟夫（Joseph）问题
栈的应用场景和介绍
栈的应用场景：
子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，回到程序调用处处理递归调用：和子程序的调用类似，但除了存储下一个指令的地址外，还将参数、区域变量等数据存入堆栈中表达式的转换与求值（中缀表达式转后缀表达式）二叉树的遍历图的深度优先（DFS）
栈的思路分析和代码实现
使用数组实现栈数据结构
package com.bear.stack; public class Stack{ private Integer elementCount = 0; private final Object[] elementData; private Integer size = -1; public Stack(Integer elementCount) { this.elementCount = elementCount; this.elementData = new Object[elementCount]; } public void push(T element) { if (size >= elementCount) { System.out.println("栈满，不能添加数据"); return; } elementData[++size] = element; } public Object pop() { if (size < 0) { System.out.println("空栈，不能取出数据"); return null; } return elementData[size--]; } public Object peek() { if (size < 0) { System.out.println("空栈，不能取出数据"); return null; } return elementData[size]; } public Integer size() { return this.size + 1; } public void print() { int index = size; while (index >= 0) { System.out.print(pop() + "t"); --index; } } }
栈的功能测试和小结
栈实现综合计算器思路分析
使用栈完成对运算表达式计算的思路分析：
定义两个栈 numStack（存放操作数）和 operatorStack（存放操作符）
使用一个 index 索引来遍历需要进行计算的运算表达式：如果是一个数字（注意需向前查看一位，以确定该数字是否是多位数），则直接压入 numStack，如果是操作符，则分以下两种情况进行：
2.1 如果当前的符号栈为空，则直接将操作符入栈
2.2 如果当前符号栈不为空，则比较栈顶的运算符与当前运算符的优先级，若当前操作符优先级大于栈顶的操作符优先级，则当前操作符压入符号栈；否则将栈顶的运算符弹出的同时从数栈中弹出两个数进行运算获得的运算结果 res 将其压入数栈中；再次比较当前操作符与符号栈，重复情况讨论
表达式扫描完毕，从数栈和符号栈中弹出运算符和操作数并进行运算，且将运算结果 res 压入数栈
当且仅当符号栈为空且数栈只存在一个数时，该数就是最终的计算结果
栈实现综合计算器代码实现 1
栈实现综合计算器代码实现 2
前缀 中缀 后缀表达式规则
前缀表达式（波兰表达式）：前缀表达式的运算符位于与其相关的操作数之前。前缀表达式的计算机求值步骤：从右至左扫描求值计算表达式（前缀表达式），遇到数字时将其压入栈顶，遇到操作符时依次弹出栈顶的两位操作数并用运算符进行计算得到结果 res，再将 res 压入栈顶；重复上述步骤直至到达计算表达式左端，最后得出的数即为运算结果后缀表达式（逆波兰表达式）：后缀表达式的运算符位于与其相关的操作数之后。计算机求值步骤与前缀相似，不同的是扫描表达式的顺序是从左到右。
逆波兰计算器分析和实现 1
计算后缀表达式代码实现：
public int calSuffixExp(String suffixExp) {
String[] suffix = suffixExp.split(" ");
Stack numStack = new Stack<>();
// 从左至右遍历后缀表达式
for (String str : suffix) {
// 遇到数字则将其压入栈中
if (str.matches("\d+")) {
numStack.push(Integer.valueOf(str));
} else {
// 遇到操作符则从栈顶依次弹出两个操作数计算得到结果 res，并将 res 再次压入栈顶
numStack.push(calculate(numStack.pop(), numStack.pop(), str));
}
}
return numStack.pop();
}
逆波兰计算器分析和实现 2
中缀转后缀表达式思路分析
中缀表达式转后缀表达的思路分析：
从左到右开始扫描中缀表达式：
遇到数字，直接输出
遇到运算符：
2.1 若为左括号 “(” 或栈为空则 直接入栈
2.2 若为右括号 “)” 将符号栈中的元素依次出栈并输出, 直到左括号 “(“ 出栈， “(“ 只出栈不输出
2.3 若为其他符号, 将符号栈中的元素依次出栈并输出, 直到遇到比当前符号优先级更低的符号，并将当前符号入栈扫描完后, 将符号栈栈中剩余符号依次输出
中缀转后缀表达式代码实现 1
中缀转后缀表达式代码实现 2
public String infixToSuffix(String infixExp) {
if (infixExp == null || infixExp.length() == 0) {
return null;
}
Stack operatorStack = new Stack<>();
List infixList = infixExpIntoList(infixExp);
StringBuilder res = new StringBuilder();
// 从左至右遍历中缀表达式
for (String str : infixList) {
// 如果是数字则直接输出
if (str.matches("\d+")) {
res.append(str).append(" ");
} else if ("(".equals(str) || operatorStack.size() == 0) {
// 左括号或栈为空则直接入栈
operatorStack.push(str);
} else if (")".equals(str)) {
// 右括号需要将符号栈中的 "(" 括号之前的操作符全部输出，"(" 只出栈不输出
String op;
while (!"(".equals((op = operatorStack.pop()))) {
res.append(op).append(" ");
}
} else {
// 栈顶操作符优先级大于等于当前操作符，则弹出栈顶元素，结束后将当前操作符压入栈中
while (operatorStack.size() > 0 && getPriority(operatorStack.peek()) - getPriority(str) >= 0) {
res.append(operatorStack.pop()).append(" ");
}
operatorStack.push(str);
}
}
// 将符号栈中剩余的操作符输出
while (operatorStack.size() > 0) {
res.append(operatorStack.pop()).append(" ");
}
return res.toString();
}
完整版逆波兰计算器和小结
递归应用场景和调用机制
递归能解决的问题和规则
递归解决的问题举例：
各种数学问题：如八皇后问题、汉诺塔问题、阶乘问题、迷宫问题、球和篮子的问题各种算法：快排、归并排序、二分查找、分治算法用栈解决的问题用递归解决代码较为简介
使用递归需要注意的问题：
递归调用一次方法时就会开辟一个独立的栈空间，各个栈空间中局部变量相互独立互不影响如果递归方法中的参数是引用类型则递归调用的所有方法共享该变量3递归过程必须趋向退出递归的条件逼近当一个方法执行完毕或遇到 return 就会返回到方法调用处，谁调用就将返回值返回给谁
迷宫回溯问题分析和实现 1
迷宫回溯问题分析和实现 2
迷宫问题探路递归算法：
public boolean findWay(int[][] map, int row, int col) {
// Recursive exit, reaching the end, game is over
if (map[MazeGame.ROWS - 2][MazeGame.COLS - 2] == State.ACCESSIBLE.ordinal()) {
return true;
} else {
// Did not find the recursive exit, continue to recursively find the exit
// Current location was never passed by, you should judge whether it could go.
if (map[row][col] == State.COULD_GO.ordinal()) {
// First, we assumed to be able to go through, make the value is 2
map[row][col] = State.ACCESSIBLE.ordinal();
// To the right of the current position is a path
if (findWay(map, row, col + 1)) {
return true;
} else if (findWay(map, row + 1, col)) {
// Below the current position is a pathway
return true;
} else if (findWay(map, row, col - 1)) {
// To the left of the current position is a path
return true;
} else if (findWay(map, row - 1, col)) {
// Above the current position is a pathway
return true;
} else {
// There is no accessible way of the current location, change its value to 3.
map[row][col] = State.DON_NOT_GO_AGAIN.ordinal();
return false;
}
} else {
// map[row][col] == 1 || 2 || 3
return false;
}
}
}
汉诺塔问题盘子移动关键算法：
public int tower(int num, char begin, char middle, char target) {
cnt++;
// 如果只有一个盘，直接从 begin 移动到 target
if (num == 1) {
System.out.println(begin + " -> " + target);
} else {
// 先将剩下的 num - 1 个盘子从 begin 移动到 middle，中间过程借助 target 柱
tower(num - 1, begin, target, middle);
// 将 begin 上的最后一个盘移动到 target
System.out.println(begin + " -> " + target);
// 再将 middle 柱上剩下的 num -1 个盘从 middle 移动到 target，中间过程借助 begin 柱
tower(num - 1, middle, begin, target);
}
return cnt;
}
八皇后问题分析和实现 1
八皇后问题分析和实现 2
八皇后问题分析和实现 3
package com.bear.recursion;
public class EightQueens {
private static final int QUEENS = 8;
private final int[] array = new int[QUEENS];
private int solution;
public int getSolution() {
return solution;
}
public void place(int queenNum) {
if (queenNum == QUEENS) {
print();
++solution;
return;
}
// 依次放置皇后，同时判断布局是否冲突
for (int i = 0; i < QUEENS; i++) {
// 先将当前皇后放到该行的第 1 列，并判断是否冲突
array[queenNum] = i;
if (isConflict(queenNum)) {
// 不冲突接着放置皇后
place(queenNum + 1);
}
// 冲突则当前皇后后移一个位置
}
}
private boolean isConflict(int queenNum) {
for (int i = 0; i < queenNum; i++) {
// 判断两个皇后是否在同一列
// 注：无需判断是否在同一行，因为 i 自增依次表示第 i + 1 行
if (array[i] == array[queenNum]) {
return false;
}
// 判断是否在同一斜线上
if (Math.abs(queenNum - i) == Math.abs(array[queenNum] - array[i])) {
return false;
}
}
return true;
}
private void print() {
for (int location : array) {
System.out.print(location + " ");
}
System.out.println();
}
}
排序算法介绍和分类
排序的分类：
内部排序：将所需要处理的所有数据都加载到内存中进行排序外部排序：数据量过大，无法全部加载到内存中进行排序，需要借助外部存储进行排序
常见排序算法
算法的时间复杂度：事后统计法和事前估算法
时间频度介绍和特点
时间频度：一个算法耗费的时间与算法中语句的执行次数成正比例。一个算法中语句执行次数称为语句频度或时间频度，记为 T(n)分析时可以忽略常数项、忽略低次项、忽略系数
时间复杂度计算机和举例说明
时间复杂度：一般情况下，算法的基本操作语句的重复执行次数是问题规模 n 的某个函数用 T(n) 表示。若有辅助函数 f(n) 使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于 0 的常数，则称 f(n) 是 T(n) 的同数量级函数。记作 T(n) = O(f(n))，称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度
常见时间复杂度由小到大依次为：O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(nk) < O(2n)
| 时间复杂度 | 符号 | |
|---|---|---|
| 1 | 常数阶 | O(1) |
| 2 | 对数阶 | O(log2n) |
| 3 | 线性阶 | O(n) |
| 4 | 线性对数阶 | O(nlog2n) |
| 5 | 平方阶 | O(n2) |
| 6 | 立方阶 | O(n3) |
| 7 | k 次方阶 | O(nk) |
| 8 | 指数阶 | O(2n) |
| 9 | 阶乘阶 | O(n!) |
各时间复杂度举例说明：
对数阶（O(n) = log2n）
int i = 1; while(i < n){ i = i * 2; }线性阶：单层 for 循环
线性对数阶：将时间复杂度为对数的代码执行 n 遍
for(int m = 1; m < n; m++){ int i = 1; while(i < n){ i = i * 2; } }
平均和最坏时间复杂度介绍
常见算法的平均时间复杂度和最坏时间复杂度介绍
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 稳定度 | 空间复杂度 | 使用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) | n 较小 |
| 交换排序 | O(n2) | O(n2) | 不稳定 | O(1) | n 较小 |
| 选择排序 | O(n2) | O(n2) | 不稳定 | O(1) | n 较小 |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已有序 |
| 基数排序 | O(logRB) | O(logRB) | 稳定 | O(n) | B(0-9) R(个十百) |
| 希尔排序 | O(nlogn) | O(ns) 1 < s < 2 | 不稳定 | O(1) | s 是所选分组 |
| 快速排序 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n 较大 |
| 归并排序 | O(nlogn) | Onlogn) | 稳定 | O(1) | n 较大 |
| 堆排序 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n 较大 |
冒泡排序算法思路图解
冒泡排序算法代码实现
public void bubbleSort(int[] array) {
int times = array.length - 1;
// 外层循坏共执行 len - 1 次
for (int i = 0; i < times; i++) {
boolean flag = true;
for (int j = 0; j < times - 1 - i; j++) {
// 如果前一个数比后一个数大则交换
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = false;
}
}
// 如果在某趟排序过程中未发生元素交换则说明数组已有序，可提前结束排序
if (flag) {
break;
}
}
}
冒泡排序算法优化和总结
优化：如果在某趟排序过程中未发生元素交换则说明数组已有序，可提前结束排序
选择排序算法思路图解
选择排序算法代码实现
public void selectSort(int[] array) {
int len = array.length;
// 外层循环共执行 len - 1 次
for (int i = 0; i < len - 1; i++) {
// 假设本轮选择排序中最大的数的下标为 i
int maxIndex = i;
for (int j = i + 1; j < len; j++) {
// 从后序的数组元素中查找看是否有比当前 array[maxIndex] 更大的数，有则将其下标赋值给 maxIndex
if (array[j] > array[maxIndex]) {
maxIndex = j;
}
}
if (maxIndex != i) {
int temp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = temp;
}
}
}
- 选择排序算法速度测试
插入排序算法思路图解
基本思想：把 n 各待排序的数据看作是一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含 n - 1 各元素，排序过程中每次从无序表中取出第一个元素，把它与有序表中的元素依次比较，插入到合适的位置使得有序表依然有序
插入排序算法代码实现
public void insertionSort(int[] array) {
int len = array.length;
// 从第二个元素开始依次为每个元素寻找插入位置
for (int rightIndex = 1; rightIndex < len; rightIndex++) {
int waitInsertValue = array[rightIndex];
int leftIndex = rightIndex - 1;
// 从待插入数据的前一个元素向前查找，当左索引大于等于 0 且元素值大于待插入数据时继续向左查找，过程中元素逐次后移
while (leftIndex >= 0 && array[leftIndex] > waitInsertValue) {
// 将大于待插入数据的元素依次后移
array[leftIndex + 1] = array[leftIndex];
--leftIndex;
}
// 查找结束将 waitInsertValue 插入到空位上
array[leftIndex + 1] = waitInsertValue;
}
}
插入排序算法速度测试
希尔排序算法思路图解
插入排序算法存在的问题：当需要插入的数据较小且位于数组较后时，元素后移的次数明显增多，效率低
希尔排序交换式算法实现
public void hillSort(int[] array) {
int len = array.length;
// 依次将数组按 gap 间隔进行分组
for (int gap = len / 2; gap > 0; gap /= 2) {
// 一组一组地进行遍历
for (int i = gap; i < len; i++) {
// 遍历各组元素，并进行简单插入排序
for (int j = i - gap; j >= 0; j -= gap) {
if (array[j] > array[j + gap]) {
int temp = array[j];
array[j] = array[j + gap];
array[j + gap] = temp;
}
}
}
}
}
希尔排序移位式算法实现
public void hillSort(int[] array) {
int len = array.length;
// 按 gap 间隔对数组进行分组
for (int gap = len / 2; gap > 0; gap /= 2) {
// 依次遍历每一组元素
for (int i = gap; i < len; i++) {
int waitInsertValue = array[i];
int curIndex = i;
// 若当前数据比前一个数据小，继续向前寻找插入位置
if (array[curIndex] < array[curIndex - gap]) {
// 当未找到当前组的最左端元素且当前元素依旧比等待插入的元素值大时，继续寻找插入位置并将元素后移
while (curIndex - gap >= 0 && array[curIndex - gap] > waitInsertValue) {
array[curIndex] = array[curIndex - gap];
curIndex -= gap;
}
// while 循环结束为当前等待插入的数据找到了插入位置
array[curIndex] = waitInsertValue;
}
}
}
}
快速排序算法思路图解
快速排序是对冒泡排序的一种改进。其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行
快速排序算法代码实现
public void quickSort(int[] array, int begin, int end) {
if (begin > end) {
return;
}
// 每次快排选取最左边的数作为基准数
int baseNum = array[begin];
int leftIndex = begin;
int rightIndex = end;
// 在 [begin,end] 区间范围内寻找比基准数小和比基准数大的数进行交换直至左索引与右索引相遇
while (leftIndex != rightIndex) {
// 在右半区间寻找比基准数小的数
while (array[rightIndex] >= baseNum && rightIndex > leftIndex) {
rightIndex--;
}
// 在左半区间寻找比基准数大的数
while (array[leftIndex] <= baseNum && leftIndex < rightIndex) {
leftIndex++;
}
// 如果左半区间找到的比基准数大的数比右半区间找到的比基准数小的数还大，则他俩交换其值
if (array[leftIndex] > array[rightIndex]) {
int temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
}
// 将本轮基准数移动到 [begin,end] 区间的中间位置
array[begin] = array[leftIndex];
array[leftIndex] = baseNum;
// 对左半部分数据继续进行快排
quickSort(array, begin, leftIndex - 1);
// 对右半本分数据继续进行快排
quickSort(array, rightIndex + 1, end);
}
快速排序算法速度测试
归并排序算法思路图解
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的
归并排序算法代码实现
public void mergeSort(int[] array, int begin, int end, int[] temp) {
if (begin < end) {
int mid = (begin + end) / 2;
// 向左递归分解左部分
mergeSort(array, begin, mid, temp);
// 向右递归分解右部分
mergeSort(array, mid + 1, end, temp);
// 合并
merge(array, begin, end, temp);
}
}
private void merge(int[] array, int begin, int end, int[] temp) {
// i 为左部分有序表的左索引
int i = begin;
// mid 为本次分解后的中间下标
int mid = (begin + end) / 2;
// j 为右部分有序表的左索引
int j = mid + 1;
// t 为临时数组 temp 的左索引
int t = 0;
// 按升序合并左、右两部分有序表直至一方合并完成，借助临时数组
while (i <= mid && j <= end) {
// 拷贝左部分有序表元素到临时数组
if (array[i] <= array[j]) {
temp[t] = array[i];
t++;
i++;
} else {
// 拷贝右部分有序表元素到临时数组
temp[t] = array[j];
t++;
j++;
}
}
// 将左部分有序表剩余元素拷贝到临时数组
while (i <= mid) {
temp[t] = array[i];
t++;
i++;
}
// 将右部分有序表剩余元素拷贝到临时数组
while (j <= end) {
temp[t] = array[j];
t++;
j++;
}
// 最后将左、右部分有序表合并结果拷贝到原数组中
t = 0;
for (; begin <= end; begin++, t++) {
array[begin] = temp[t];
}
}
归并排序算法速度测试
基数排序算法思路图解
基数排序是对桶排序的扩展。其基本思想是将所有待比较的数值统一为同样长度的数位，数位较短的前面补 0。然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位的排序完成以后，数列就已然有序
基数排序算法代码实现 1
基数排序算法代码实现 2
public void radixSort(int[] array) {
// 获取数组中数字的最大位数
int maxDigits = getMaxDigits(array);
int len = array.length;
// 定义十个桶，编号依次为 0 ~ 9，每个桶依次记录末尾数字与桶编号相同的元素值
int[][] bucket = new int[10][len];
// 定义一维数组存放每个桶放置的元素个数
int[] digitsInBucket = new int[len];
// 循环 maxDigits 轮，依次将数字归到对应的桶中
for (int k = 0; k < maxDigits; k++) {
for (int num : array) {
int lastNumber = (num / (int) Math.pow(10, k)) % 10;
// 将 num 放到对应的桶编号中
bucket[lastNumber][digitsInBucket[lastNumber]] = num;
digitsInBucket[lastNumber]++;
}
// 遍历十个桶，将其中存放的数据重新赋值给 array
int arrayIndex = 0;
for (int i = 0; i < 10; i++) {
// 判断桶中是否有数据，有则遍历取出
if (digitsInBucket[i] != 0) {
for (int j = 0; j < digitsInBucket[i]; j++) {
array[arrayIndex] = bucket[i][j];
arrayIndex++;
}
// 元素取出后对应桶编号中存放的数据个数置 0
digitsInBucket[i] = 0;
}
}
}
}
private int getMaxDigits(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int maxNum = 0;
for (int num : array) {
if (num > maxNum) {
maxNum = num;
}
}
return (maxNum + "").length();
}
基数排序算法注意事项
基数排序是效率较高的的稳定性排序法排序算法的稳定性是指，在需要进行排序操作的数据中，如果存在值相等的元素，在排序前后，相等元素之间的相对位置不发生变化桶排序示意图
4. 计数排序示意图
5. 堆排序示意图
排序算法时间复杂度比较
