数据结构与算法：Java代码实现与优化

在编程的世界里，数据结构与算法是基石，而Java作为一门广泛应用的语言，其实现与优化尤为重要。本文将探讨几种常见数据结构与算法的Java实现，并分享一些优化技巧。

数据结构与算法：Java代码实现与优化

数组与链表：基础但不简单

数组

数组是最基本的数据结构之一。在Java中，数组的声明与初始化简洁明了：

int[] arr = new int[10];

然而，数组的固定长度限制了其灵活性。优化策略之一是使用动态数组，如ArrayList：

import java.util.ArrayList;

ArrayList<Integer> dynamicArr = new ArrayList<>();
dynamicArr.add(1);
dynamicArr.add(2);

链表

链表弥补了数组的不足，支持动态插入和删除。以下是单链表的简单实现：

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

ListNode head = new ListNode(1);
head.next = new ListNode(2);

优化链表操作的关键在于减少指针操作，例如使用尾指针来优化插入操作。

栈与队列：经典的双重奏

栈

栈是后进先出（LIFO）的数据结构。Java中可以使用Stack类：

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.pop();

优化栈操作时，可以考虑使用ArrayDeque，其性能更优：

import java.util.ArrayDeque;

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
int top = stack.pop();

队列

队列是先进先出（FIFO）的数据结构。Java提供了Queue接口及实现类LinkedList：

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
int front = queue.poll();

优化队列操作时，同样推荐使用ArrayDeque：

import java.util.ArrayDeque;

ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
int front = queue.poll();

排序算法：效率与简洁的平衡

快速排序

快速排序是高效的排序算法之一。以下是Java实现：

public class QuickSort {
    public void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            sort(arr, low, pivotIndex - 1);
            sort(arr, pivotIndex + 1, high);
        }
    }

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

优化快速排序的关键在于选择合适的枢轴，例如使用三数取中法。

归并排序

归并排序是稳定的排序算法。以下是Java实现：

public class MergeSort {
    public void sort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= right) {
            temp[k++] = arr[j++];
        }

        for (i = left, k = 0; i <= right; i++, k++) {
            arr[i] = temp[k];
        }
    }
}

优化归并排序可以考虑使用原地归并算法，减少空间复杂度。