Java

1、排序

1.1 数组排序(java.util.Arrays

1.1.1 基本数据类型排序

  • 对整个数组排序

    1. public static void sort(int[] a);
  • 对部分数组 [fromIndex, toIndex) 排序

    1. public static void sort(int[] a, int fromIndex, int toIndex);

    七种基本类型 int、long、short、char、byte、float、double(除了 boolean),都支持上述格式的排序 API。

    1.1.2 对象排序

  • 实现了 java.lang.Comparable 接口的对象。

    1. // 对整个数组排序
    2. public static void sort(Object[] a);
    3. // 对部分数组 [fromIndex, toIndex) 排序
    4. public static void sort(Object[] a, int fromIndex, int toIndex);
  • 通过 java.util.Comparator 排序: ```java // 对整个数组排序 public static void sort(T[] a, Comparator<? super T> c); // 对部分数组 [fromIndex, toIndex) 排序 public static void sort(T[] a, int fromIndex, int toIndex,

    1. Comparator<? super T> c);

public interface Comparator { // result < 0:o1 排在 o2 前面 // result == 0:o1 和 o2 的值一样 // result > 0:o1 排在 o2 后面 int compare(T o1, T o2); }

  1. 案例:
  2. ```java
  3. public class Solution {
  4. public static void main(String[] args) {
  5. Person[] persons = new Person[2];
  6. persons[0] = new Person(2);
  7. persons[1] = new Person(1);
  8. Arrays.sort(persons, new Comparator<Person>() {
  9. @Override
  10. public int compare(Person o1, Person o2) {
  11. return o1.id - o2.id;
  12. }
  13. });
  14. // 输出:
  15. // Solution.Person(id=1)
  16. // Solution.Person(id=2)
  17. Arrays.stream(persons).forEach(System.out::println);
  18. }
  19. @AllArgsConstructor
  20. @ToString
  21. public static class Person {
  22. private int id;
  23. }
  24. }

或者使用 lambda 表达式替换 Comparator 匿名类。

  1. Arrays.sort(persons, (o1, o2) -> {
  2. return o1.id - o2.id;
  3. });

1.2 列表排序(java.util.Collections

排序

  1. public static <T extends Comparable<? super T>> void sort(List<T> list);
  2. public static <T> void sort(List<T> list, Comparator<? super T> c);
  3. public interface Comparator<T> {
  4. // result < 0:o1 排在 o2 前面
  5. // result == 0:o1 和 o2 的值一样
  6. // result > 0:o1 排在 o2 后面
  7. int compare(T o1, T o2);
  8. }

反转列表元素

  1. public static void reverse(List<?> list);

1.3 二维数组排序(java.util.Arrays

提示:Java 数组也是一种对象

  1. // api
  2. public static <T> void sort(T[] a, Comparator<? super T> c);
  3. // 案例
  4. Arrays.sort(nums, (int[]a, int[]b) -> a[0] - b[0]);

2、二分查找

数组(java.util.Arrays

  1. public static int binarySearch(int[] a, int key);
  2. public static int binarySearch(int[] a, int fromIndex, int toIndex, int key);
  3. public static int binarySearch(Object[] a, Object key);
  4. public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key);
  5. public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c);
  6. public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c);

列表(java.util.Collections

  1. public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key);
  2. public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c);

3、栈(java.util.Stack

创建

  1. Stack<Integer> stack = new Stack<>();

数据操作

  1. // 往【栈】里面添加一个元素
  2. public E push(E item)
  3. // 往【栈】里面弹出一个元素
  4. public synchronized E pop();

条件判断

  1. public synchronized boolean isEmpty();

4、队列(java.util.Queue

创建(java.util.LinkedList

  1. Queue<Integer> queue = new LinkedList<>();

数据操作

  1. // 往【队列】里面添加一个元素
  2. boolean add(E e);
  3. // 往【队列】里面弹出一个元素
  4. E poll();

条件判断

  1. boolean isEmpty();

5、堆(java.util.PriorityQueue

提示:Java 里面的优先队列

创建

  1. // 创建一个最小堆
  2. PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  3. // 创建一个最大堆
  4. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

数据操作

  1. // 往【堆】里面添加一个元素
  2. public boolean add(E e);
  3. // 从【堆】里面弹出一个元素
  4. public E poll();

其他工具

降序排序(java.util.Comparator

  1. // 反转一个 Comparator 的排序规则
  2. // 比如从【升序】反转为【降序】
  3. default Comparator<T> reversed();
  4. // 反转一个 Comparable 的排序规则
  5. // 比如从【升序】反转为【降序】
  6. public static <T extends Comparable<? super T>> Comparator<T> reverseOrder();

大数(java.math.BigInteger

  1. // 创建一个大数
  2. public static BigInteger valueOf(long val);
  3. // 数据操作
  4. public BigInteger add(BigInteger val);
  5. public BigInteger subtract(BigInteger val);
  6. public BigInteger multiply(BigInteger val);
  7. public BigInteger divide(BigInteger val);

集合(java.util.Collections

  1. // 初始化一个具有 n 个相同元素 o 的 list
  2. public static <T> List<T> nCopies(int n, T o);
  3. // 反转一个 list 的顺序
  4. public static void reverse(List<?> list);