算法与数据结构：基础与实战

数据结构基础

数据结构是组织和存储数据的方式，选择合适的数据结构可以显著提高程序的效率。

数组

数组是最基本的数据结构，在连续的内存空间中存储相同类型的元素。

public class ArrayExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        System.out.println("总和: " + sum);
    }
}

链表

链表由节点组成，每个节点包含数据和指向下一个节点的指针。

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListExample {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

栈和队列

栈是后进先出（LIFO）的数据结构，队列是先进先出（FIFO）的数据结构。

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

public class StackQueueExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        System.out.println(queue.poll());
    }
}

哈希表

哈希表通过哈希函数将键映射到值，实现快速查找。

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 5);
        map.put("banana", 3);
        map.put("orange", 7);
        
        System.out.println(map.get("apple"));
        
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

排序算法

排序算法是将一组数据按照特定顺序排列的方法。

快速排序

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }
    
    private static 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;
    }
}

归并排序

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr.length > 1) {
            int mid = arr.length / 2;
            int[] left = new int[mid];
            int[] right = new int[arr.length - mid];
            
            System.arraycopy(arr, 0, left, 0, mid);
            System.arraycopy(arr, mid, right, 0, arr.length - mid);
            
            mergeSort(left);
            mergeSort(right);
            merge(arr, left, right);
        }
    }
    
    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }
}

搜索算法

搜索算法用于在数据集合中查找特定元素。

二分查找

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

算法复杂度

算法复杂度描述了算法运行所需的时间和空间资源。

算法	时间复杂度(平均)	时间复杂度(最坏)	空间复杂度
冒泡排序	O(n²)	O(n²)	O(1)
快速排序	O(n log n)	O(n²)	O(log n)
归并排序	O(n log n)	O(n log n)	O(n)
二分查找	O(log n)	O(log n)	O(1)
哈希表查找	O(1)	O(n)	O(n)

总结

算法与数据结构是程序员的基本功，掌握常用的数据结构和算法不仅能帮助你写出更高效的代码，也是面试中的重要考察点。建议通过刷题和实践来加深理解。