以前写算法大都是cpp，虽然学了很久java，但是算法题还是没用过，这里总结一下基础算法模板

八大排序模板

java
import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 7, 6, 3, 8, 4};

        // Bubble Sort
        int[] bubbleSortedArray = bubbleSort(array.clone());
        System.out.println("Bubble Sort: " + Arrays.toString(bubbleSortedArray));

        // Selection Sort
        int[] selectionSortedArray = selectionSort(array.clone());
        System.out.println("Selection Sort: " + Arrays.toString(selectionSortedArray));

        // Insertion Sort
        int[] insertionSortedArray = insertionSort(array.clone());
        System.out.println("Insertion Sort: " + Arrays.toString(insertionSortedArray));

        // Shell Sort
        int[] shellSortedArray = shellSort(array.clone());
        System.out.println("Shell Sort: " + Arrays.toString(shellSortedArray));

        // Merge Sort
        int[] mergeSortedArray = mergeSort(array.clone());
        System.out.println("Merge Sort: " + Arrays.toString(mergeSortedArray));

        // Quick Sort
        int[] quickSortedArray = quickSort(array.clone());
        System.out.println("Quick Sort: " + Arrays.toString(quickSortedArray));

        // Heap Sort
        int[] heapSortedArray = heapSort(array.clone());
        System.out.println("Heap Sort: " + Arrays.toString(heapSortedArray));

        // Counting Sort
        int[] countingSortedArray = countingSort(array.clone());
        System.out.println("Counting Sort: " + Arrays.toString(countingSortedArray));
    }

    // Bubble Sort
    public static int[] bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // Swap array[j] and array[j+1]
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

    // Selection Sort
    public static int[] selectionSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap array[i] and array[minIndex]
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
        return array;
    }

    // Insertion Sort
    public static int[] insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
        return array;
    }

    // Shell Sort
    public static int[] shellSort(int[] array) {
        int n = array.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = array[i];
                int j;
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }
                array[j] = temp;
            }
        }
        return array;
    }

    // Merge Sort
    public static int[] mergeSort(int[] array) {
        if (array.length <= 1) {
            return array;
        }
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] merged = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                merged[k++] = left[i++];
            } else {
                merged[k++] = right[j++];
            }
        }
        while (i < left.length) {
            merged[k++] = left[i++];
        }
        while (j < right.length) {
            merged[k++] = right[j++];
        }
        return merged;
    }

    // Quick Sort
    public static int[] quickSort(int[] array) {
        quickSortHelper(array, 0, array.length - 1);
        return array;
    }

    private static void quickSortHelper(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSortHelper(array, low, pivotIndex - 1);
            quickSortHelper(array, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                // Swap array[i] and array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        // Swap array[i+1] and array[high] (pivot)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

    // Heap Sort
    public static int[] heapSort(int[] array) {
        int n = array.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            // Swap array[0] and array[i]
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heapify(array, i, 0);
        }
        return array;
    }

    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            // Swap array[i] and array[largest]
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;
            heapify(array, n, largest);
        }
    }

    // Counting Sort
    public static int[] countingSort(int[] array) {
        int max = Arrays.stream(array).max().orElse(0);
        int min = Arrays.stream(array).min().orElse(0);
        int range = max - min + 1;
        int[] count = new int[range];
        int[] output = new int[array.length];
        for (int num : array) {
            count[num - min]++;
        }
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }
        for (int i = array.length - 1; i >= 0; i--) {
            output[count[array[i] - min] - 1] = array[i];
            count[array[i] - min]--;
        }
        return output;
    }
}

二分算法

java
public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 3, 3, 4, 5};
        int target = 3;

        BinarySearch test = new BinarySearch();
        int leftBound = test.binarySearchLeftBound(nums, target);
        int rightBound = test.binarySearchRightBound(nums, target);

        System.out.println("左边界索引: " + leftBound);
        System.out.println("右边界索引: " + rightBound);
    }

    public int binarySearchLeftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                right = mid - 1; // 收缩右边界，继续向左查找
            }
        }
        // 检查 left 越界情况
        if (left >= nums.length || nums[left] != target) {
            return -1; // 没找到目标值
        }
        return left; // 返回左边界的索引
    }

    public int binarySearchRightBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1; // 收缩左边界，继续向右查找
            }
        }
        // 检查 right 越界情况
        if (right < 0 || nums[right] != target) {
            return -1; // 没找到目标值
        }
        return right; // 返回右边界的索引
    }
}

前缀和和差分

java
public class PrefixSumAndDifferenceTest {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};

        PrefixSumAndDifferenceTest test = new PrefixSumAndDifferenceTest();

        // 前缀和
        int[] prefixSum = test.calculatePrefixSum(nums);
        System.out.println("前缀和数组: ");
        for (int num : prefixSum) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 差分数组
        int[] diffArray = test.calculateDifferenceArray(nums);
        System.out.println("差分数组: ");
        for (int num : diffArray) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 差分数组还原
        int[] restoredArray = test.restoreArrayFromDifference(diffArray);
        System.out.println("还原后的数组: ");
        for (int num : restoredArray) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 计算前缀和数组
    public int[] calculatePrefixSum(int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        return prefixSum;
    }

    // 计算差分数组
    public int[] calculateDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] diffArray = new int[n];
        diffArray[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diffArray[i] = nums[i] - nums[i - 1];
        }
        return diffArray;
    }

    // 从差分数组还原原始数组
    public int[] restoreArrayFromDifference(int[] diffArray) {
        int n = diffArray.length;
        int[] restoredArray = new int[n];
        restoredArray[0] = diffArray[0];
        for (int i = 1; i < n; i++) {
            restoredArray[i] = restoredArray[i - 1] + diffArray[i];
        }
        return restoredArray;
    }
}

双链表模板

java
public class LinkedListTemplateTest {
    public static void main(String[] args) {
        LinkedListTemplate<Integer> linkedList = new LinkedListTemplate<>();

        // 头插法插入元素
        linkedList.addFirst(3);
        linkedList.addFirst(2);
        linkedList.addFirst(1);

        // 打印链表
        linkedList.printList();

        // 在指定位置插入元素
        linkedList.addAtIndex(1, 4);

        // 打印链表
        linkedList.printList();

        // 删除指定位置的元素
        linkedList.deleteAtIndex(2);

        // 打印链表
        linkedList.printList();

        // 获取链表的长度
        int length = linkedList.getLength();
        System.out.println("链表长度: " + length);

        // 查找指定值在链表中的索引
        int index = linkedList.indexOf(3);
        System.out.println("值为 3 的元素索引: " + index);
    }
}

class LinkedListTemplate<T> {
    private ListNode<T> head;
    private int length;

    public LinkedListTemplate() {
        this.head = null;
        this.length = 0;
    }

    // 头插法插入元素
    public void addFirst(T value) {
        ListNode<T> newNode = new ListNode<>(value);
        newNode.next = head;
        head = newNode;
        length++;
    }

    // 在指定位置插入元素
    public void addAtIndex(int index, T value) {
        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException("Invalid index");
        }

        if (index == 0) {
            addFirst(value);
        } else {
            ListNode<T> newNode = new ListNode<>(value);
            ListNode<T> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
            length++;
        }
    }

    // 删除指定位置的元素
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= length) {
            throw new IndexOutOfBoundsException("Invalid index");
        }

        if (index == 0) {
            head = head.next;
        } else {
            ListNode<T> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            current.next = current.next.next;
        }
        length--;
    }

    // 获取链表的长度
    public int getLength() {
        return length;
    }

    // 查找指定值在链表中的索引
    public int indexOf(T value) {
        ListNode<T> current = head;
        int index = 0;
        while (current != null) {
            if (current.value.equals(value)) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    // 打印链表
    public void printList() {
        ListNode<T> current = head;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    private static class ListNode<T> {
        T value;
        ListNode<T> next;

        public ListNode(T value) {
            this.value = value;
            this.next = null;
        }
    }
}

双链表模板

java
public class DoublyLinkedListTemplateTest {
    public static void main(String[] args) {
        DoublyLinkedListTemplate<Integer> doublyLinkedList = new DoublyLinkedListTemplate<>();

        // 向双链表尾部添加元素
        doublyLinkedList.addLast(1);
        doublyLinkedList.addLast(2);
        doublyLinkedList.addLast(3);

        // 打印双链表
        doublyLinkedList.printList();

        // 在指定位置插入元素
        doublyLinkedList.addAtIndex(1, 4);

        // 打印双链表
        doublyLinkedList.printList();

        // 删除指定位置的元素
        doublyLinkedList.deleteAtIndex(2);

        // 打印双链表
        doublyLinkedList.printList();

        // 获取双链表的长度
        int length = doublyLinkedList.getLength();
        System.out.println("双链表长度: " + length);

        // 查找指定值在双链表中的索引
        int index = doublyLinkedList.indexOf(3);
        System.out.println("值为 3 的元素索引: " + index);
    }
}

class DoublyLinkedListTemplate<T> {
    private ListNode<T> head;
    private ListNode<T> tail;
    private int length;

    public DoublyLinkedListTemplate() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    // 向双链表尾部添加元素
    public void addLast(T value) {
        ListNode<T> newNode = new ListNode<>(value);
        if (head == null) {
            head = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
        }
        tail = newNode;
        length++;
    }

    // 在指定位置插入元素
    public void addAtIndex(int index, T value) {
        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException("Invalid index");
        }

        if (index == 0) {
            ListNode<T> newNode = new ListNode<>(value);
            newNode.next = head;
            if (head != null) {
                head.prev = newNode;
            } else {
                tail = newNode;
            }
            head = newNode;
        } else if (index == length) {
            addLast(value);
        } else {
            ListNode<T> newNode = new ListNode<>(value);
            ListNode<T> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.prev = current;
            newNode.next = current.next;
            current.next.prev = newNode;
            current.next = newNode;
        }
        length++;
    }

    // 删除指定位置的元素
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= length) {
            throw new IndexOutOfBoundsException("Invalid index");
        }

        if (index == 0) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            } else {
                tail = null;
            }
        } else if (index == length - 1) {
            tail = tail.prev;
            tail.next = null;
        } else {
            ListNode<T> current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }
        length--;
    }

    // 获取双链表的长度
    public int getLength() {
        return length;
    }

    // 查找指定值在双链表中的索引
    public int indexOf(T value) {
        ListNode<T> current = head;
        int index = 0;
        while (current != null) {
            if (current.value.equals(value)) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    // 打印双链表
    public void printList() {
        ListNode<T> current = head;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    private static class ListNode<T> {
        T value;
        ListNode<T> prev;
        ListNode<T> next;

        public ListNode(T value) {
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }
}

二叉树

java
public class BinaryTreeTemplateTest {
    public static void main(String[] args) {
        BinaryTreeTemplate<Integer> binaryTree = new BinaryTreeTemplate<>();

        // 构建二叉树
        binaryTree.insert(4);
        binaryTree.insert(2);
        binaryTree.insert(6);
        binaryTree.insert(1);
        binaryTree.insert(3);
        binaryTree.insert(5);
        binaryTree.insert(7);

        // 前序遍历
        System.out.println("前序遍历:");
        binaryTree.preorderTraversal();

        // 中序遍历
        System.out.println("中序遍历:");
        binaryTree.inorderTraversal();

        // 后序遍历
        System.out.println("后序遍历:");
        binaryTree.postorderTraversal();
    }
}

class BinaryTreeTemplate<T extends Comparable<T>> {
    private Node<T> root;

    public BinaryTreeTemplate() {
        root = null;
    }

    // 插入节点
    public void insert(T value) {
        root = insertRecursive(root, value);
    }

    private Node<T> insertRecursive(Node<T> current, T value) {
        if (current == null) {
            return new Node<>(value);
        }

        if (value.compareTo(current.value) < 0) {
            current.left = insertRecursive(current.left, value);
        } else if (value.compareTo(current.value) > 0) {
            current.right = insertRecursive(current.right, value);
        }

        return current;
    }

    // 前序遍历
    public void preorderTraversal() {
        preorderTraversalRecursive(root);
        System.out.println();
    }

    private void preorderTraversalRecursive(Node<T> node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preorderTraversalRecursive(node.left);
            preorderTraversalRecursive(node.right);
        }
    }

    // 中序遍历
    public void inorderTraversal() {
        inorderTraversalRecursive(root);
        System.out.println();
    }

    private void inorderTraversalRecursive(Node<T> node) {
        if (node != null) {
            inorderTraversalRecursive(node.left);
            System.out.print(node.value + " ");
            inorderTraversalRecursive(node.right);
        }
    }

    // 后序遍历
    public void postorderTraversal() {
        postorderTraversalRecursive(root);
        System.out.println();
    }

    private void postorderTraversalRecursive(Node<T> node) {
        if (node != null) {
            postorderTraversalRecursive(node.left);
            postorderTraversalRecursive(node.right);
            System.out.print(node.value + " ");
        }
    }

    private static class Node<T> {
        T value;
        Node<T> left;
        Node<T> right;

        public Node(T value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
}

八皇后模板

java
public class EightQueensTemplate {
    private static final int BOARD_SIZE = 8;
    private static final char EMPTY = '-';
    private static final char QUEEN = 'Q';

    private static int count =  0;

    public static void main(String[] args) {
        char[][] board = createEmptyBoard();
        solveEightQueens(board, 0);
    }

    private static char[][] createEmptyBoard() {
        char[][] board = new char[BOARD_SIZE][BOARD_SIZE];
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                board[i][j] = EMPTY;
            }
        }
        return board;
    }

    private static void solveEightQueens(char[][] board, int col) {
        if (col == BOARD_SIZE) {
            count++;
            printBoard(board);
            System.out.println();
            return;
        }

        for (int row = 0; row < BOARD_SIZE; row++) {
            if (isSafe(board, row, col)) {
                board[row][col] = QUEEN;
                solveEightQueens(board, col + 1);
                board[row][col] = EMPTY;

            }
        }
    }

    private static boolean isSafe(char[][] board, int row, int col) {
        // Check if there is a queen in the same row
        for (int i = 0; i < col; i++) {
            if (board[row][i] == QUEEN) {
                return false;
            }
        }

        // Check if there is a queen in the upper diagonal
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == QUEEN) {
                return false;
            }
        }

        // Check if there is a queen in the lower diagonal
        for (int i = row, j = col; i < BOARD_SIZE && j >= 0; i++, j--) {
            if (board[i][j] == QUEEN) {
                return false;
            }
        }

        return true;
    }

    private static void printBoard(char[][] board) {
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println(count);
    }
}