万里任禅游

简体中文

English

简体中文

English

外观

算法

约 4642 字大约 15 分钟

2025-06-20

数据结构

基础数据结构

背包
/**
 * 背包
 */
public class Bag<Item> implements Iterable<Item> {

    private Node first;

    private int N; // 维护背包中元素的数量

    private class Node {
        Item item;
        Node next;
    }

    /**
     * 添加元素到背包头部
     * @param item 要添加的元素
     */
    public void add(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++; // 元素数量加一
    }

    /**
     * 删除背包头部的元素
     * @return 被删除的元素
     * @throws NoSuchElementException 如果背包为空
     */
    public Item remove() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException("Bag is empty");
        }
        Item item = first.item; // 获取头部元素
        first = first.next;    // 移动头指针到下一个节点
        N--; // 元素数量减一
        return item;           // 返回被删除的元素
    }

    /**
     * 检查背包是否为空
     * @return 如果背包为空则返回 true，否则返回 false
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * 获取背包中元素的数量
     * @return 元素的数量
     */
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        @Override
        public boolean hasNext() {
            return current != null;
        }
        @Override
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

}

应用数据结构

自定义计时器
/**
 * 自定义计时器
 */
public class StopWatch {

    private final long start;

    public StopWatch() {
        start = System.currentTimeMillis();
    }

    public String getStart() {
        String startStr  = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date(start));
        return startStr;
    }

    public double elapsedTime () {
        long now = System.currentTimeMillis();
        return (now - start) / 1000.0;
    }

}

算法

查找

二分法查找
/**
 * 二分法查找
 * 时间复杂度：O(log2n)
 */
public class BinarySearch {

    private int[] a;

    public BinarySearch(int[] keys) {
        a = new int[keys.length];
        for (int i = 0; i < keys.length; i++) {
            a[i] = keys[i]; // 保护性复制
        }
        Arrays.sort(a);
    }

    public boolean contains(int key) {
        return rank(key) != -1;
    }

    /**
     * 二分法
     * @param key
     * @return
     */
    private int rank(int key) {
        int lo = 0; // 小索引
        int hi = a.length - 1; // 大索引
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2; // 中间索引
            if (key < a[mid]) {
                hi = mid - 1;
            } else if (key > a[mid]) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


}
二分查找
  • 时间复杂度：O(log2n) 二分查找

排序

选择排序
/**
 * 选择排序：第i个元素和剩余元素比较选出最小的
 * 时间复杂度：上下界 n^2，N^2/2次比较，N次交换，幂函数增长
 * 空间复杂度：原地排序算法
 */
public class Selection {

    /**
     * 排序
     * @param a
     */
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i+1; j < N; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }
            }
            exch(a, i, min);
        }
    }

    /**
     * 判断大小
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 交换元素
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组
     * @param a
     */
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

    /**
     * 测试数组是否有顺序
     * @param a
     * @return
     */
    private static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String filePath = System.getProperty("user.dir") + "/src/txt/" + "Example.txt";
        String[] a = In.readStrings(filePath);
        sort(a);
        StdOut.println("是否排序：" + isSorted(a));
        show(a);
    }

}
选择排序
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定 选择排序