> 需要实现排序器,以及通过静态方法调用。
```java
package util;
import java.util.Arrays;
public class Sort {
public static void main(String[] args) {
String[] a = {
"1", "2", "3", "a", "a1", "b2", "a0", "_"
};
//Sort.heapSort(a);
//Sort.quickSort3way(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
/**
* 根据数组的两个下标交换数组中的元素
*
* @param <T>
* @param array
* @param i
* @param j
*/
private static <T extends Comparable> void swap(T[] array, int i, int j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
/**
* 判断a是否小于b
*
* @param <T>
* @param a
* @param b
* @return
*/
private static <T extends Comparable> boolean less(T a, T b) {
return a.compareTo(b) < 0;
}
/**
* 判断a是否等于b
*
* @param <T>
* @param a
* @param b
* @return
*/
private static <T extends Comparable> boolean eq(T a, T b) {
return a.compareTo(b) == 0;
}
/**
* 判断数组是否排序
*
* @param <T>
* @param array
* @return
*/
public static <T extends Comparable> boolean isSorted(T[] array) {
for (int i = 1; i < array.length; i++) {
if (less(array[i], array[i - 1])) {
return false;
}
}
return true;
}
/**
* 打印数组
*
* @param <T>
* @param array
*/
public static <T extends Comparable> void print(T[] array) {
for (T t : array) {
System.out.print(t + " ");
}
System.out.println();
}
}
```
- 1 设计接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 栈接口Stack
- 1.4 队列接口Queue
- 1.5 Union-Find算法接口UF
- 2 实现接口
- 2.1 结点类Node
- 2.2 数组迭代器ArrayIterator
- 2.3 链表迭代器ListIterator
- 2.4 背包(Bag)的实现
- 2.4.1 能动态调整数组大小的Bag
- 2.4.2 链式Bag的实现
- 2.5 栈(Stack)的实现
- 2.5.1 能动态调整数组大小的Stack
- 2.5.2 链式Stack的实现
- 2.6 队列(Queue)的实现
- 2.6.1 能动态调整数组大小的Queue
- 2.6.2 链式Queue的实现
- 2.7 Union-Find算法的实现
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 测试
- 2.8.1 测试Stack
- 2.8.2 测试Union-Find
- 3 排序算法
- 3.1 定义排序工具的类结构
- 3.2 选择排序
- 3.3 插入排序
- 3.4 希尔排序
- 3.5 归并排序
- 3.5.1 归并排序的合并方法
- 3.5.2 自顶向下的归并排序
- 3.5.3 自底向上的归并排序
- 3.6 快速排序
- 3.6.1 常规快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改进方法-小数据量转成插入排序
- 3.6.4 快速排序的改进方法-三向切分
- 3.7 堆排序
- 3.8 最终的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 优先队列(MaxPriorityQueue)
- 4.3 二叉查找树(BST)
- 4.4 红黑二叉查找树(RedBlackBST)
- 4.5 B-树(BTree)
- 5 图
- 5.1 无向图(Graph)
- 5.2 有向图(Digraph)
- 6 贪心
- Dijkstra算法-单元最短路径
- 7 动态规划
- 7.1 最长公共子序列问题
- 7.2 0-1背包问题
- 7.3 加工顺序问题
- 8 搜索法
- 8.1 图的着色问题
- 8.2 深度优先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集树
- 8.3.3 排列树
- 8.3.4 满m叉树(组合树)
- 8.4 广度优先搜索
- 8.5 分支限界法
- 9 随机化算法
- 9.1 数值随机化算法
- 9.2 蒙特卡罗算法
- 9.3 拉斯维加斯算法
- 9.4 舍伍德算法
- 10 数论算法
- 10.1 Stein求最大公约数
- 10.2 矩阵求斐波那切数列
- LeetCode刷题笔记