一、快速排序算法：核心分治思想与高效实现
快速排序（Quick Sort）是经典的分治排序算法，凭借O(n log n)的平均时间复杂度、空间效率高、原地排序等优势，在工程实践中被广泛应用。它的核心是通过“基准数定位+双指针交换+递归分治”的逻辑，将大数组拆解为小数组，逐层完成排序。
核心分治思想与游标移动逻辑
快速排序的核心是分治策略：将待排序数组拆分为“基准数+左侧子数组+右侧子数组”，左侧子数组均小于基准数，右侧均大于基准数，再对左右子数组递归执行同样的操作，直至子数组不可再拆分（长度为1）。这一过程依赖基准数定位和双指针交换机制。
双指针交换是快速排序的核心操作，目的是让左右指针相向移动，找到“左侧大于基准数、右侧小于基准数”的元素对并交换，最终将基准数归位到正确的位置，完成一次分区。
指针移动逻辑： I指针（左指针）：从左向右移动，寻找第一个大于基准数的元素，若找到则停止；若未找到（I超过J），直接进入最终交换。 J指针（右指针）：从右向左移动，寻找第一个小于基准数的元素，若找到则停止；若未找到（J超过I），直接进入最终交换。
交换时机：当I和J均找到符合条件的元素后，交换二者对应的数组元素，之后继续移动指针。 最终归位：当I和J相遇时，无论相遇位置的元素是大于还是小于基准数，都将基准数与相遇位置的元素交换，此时基准数就位于了分区后的正确位置。
递归终止条件
分区完成后，数组被拆分为左侧子数组（left到pivotIndex-1）和右侧子数组（pivotIndex+1到right），此时需要对这两个子数组递归执行相同的分区、交换操作，直至子数组的长度为1（此时数组自然有序，无需排序）。
递归终止条件：当待排序区间的左边界left大于等于右边界right时，说明该区间长度小于等于1，直接终止递归。 递归核心：递归的本质是“分而治之”，通过不断拆分大区间为小区间，直到小区间无需排序，最终将所有小区间有序合并，得到完整有序的数组。
完整快速排序代码
import java.util.Arrays; public class QuickSortComplete { // 快速排序入口方法 public void quickSort(int[] array, int left, int right) { // 递归出口：区间长度<=1，直接返回 if (left >= right) { return; } // 1. 分区：获取基准数归位后的下标 int pivotIndex = partition(array, left, right); // 2. 递归排序左侧子数组 [left, pivotIndex-1] quickSort(array, left, pivotIndex - 1); // 3. 递归排序右侧子数组 [pivotIndex+1, right] quickSort(array, pivotIndex + 1, right); } // 分区方法（同上述单次分区逻辑） private int partition(int[] array, int left, int right) { int pivot = array[left]; int i = left; int j = right; while (i < j) { while (i < j && array[j] >= pivot) { j--; } while (i < j && array[i] <= pivot) { i++; } if (i < j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } array[left] = array[i]; array[i] = pivot; return i; } public static void main(String[] args) { QuickSortComplete sorter = new QuickSortComplete(); int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; System.out.println("排序前数组：" + Arrays.toString(arr)); sorter.quickSort(arr, 0, arr.length - 1); System.out.println("排序后数组：" + Arrays.toString(arr)); // 输出：排序后数组按升序排列 } }内存执行流程与变量作用域
快速排序的递归过程依赖JVM的栈结构，理解栈帧变化和变量作用域，能帮助我们更清晰地掌握算法的执行逻辑，避免陷入递归的“思维迷宫”。
栈帧变化模拟
递归的本质是方法的嵌套调用，每次递归调用都会在JVM的栈空间中创建一个新的栈帧，用于存储当前方法的参数、局部变量和返回地址，递归结束后栈帧出栈，释放内存。
以数组[3,1,4,2]为例，快速排序的栈帧变化流程如下：
- 首次调用：调用
quickSort(array, 0, 3)，创建第一个栈帧，存储参数left=0、right=3，执行分区后，基准数3归位到下标2，递归调用quickSort(array,0,1)和quickSort(array,3,3)。 - 左子递归入栈：调用
quickSort(array,0,1)，创建第二个栈帧，分区后基准数1归位到下标0，递归调用quickSort(array,0,-1)和quickSort(array,1,1)。 - 左子递归的子调用入栈：
quickSort(array,0,-1)触发递归出口，直接出栈；quickSort(array,1,1)也触发出口，出栈；第二个栈帧执行完毕，出栈。 - 右子递归入栈：回到首次调用，执行
quickSort(array,3,3)，触发出口，出栈。 - 首次调用出栈：首次调用执行完毕，栈帧出栈，完成整个排序过程。
核心要点：栈帧遵循“先进后出”的原则，递归调用时栈帧入栈，递归出口触发时栈帧出栈，递归深度不能超过JVM栈的容量（否则会抛出栈溢出异常StackOverflowError）。
变量作用域
快速排序的方法中，变量的作用域决定了变量的生命周期，需要重点关注局部变量和数组引用的差异： 局部变量（如temp）：局部变量存储在当前方法的栈帧中，当方法执行结束、栈帧出栈时，局部变量会自动销毁，内存被回收。例如分区方法中的temp，仅在单次分区过程中存在，分区结束后就被销毁，不会影响其他方法的执行。 数组引用的共享性：数组是引用类型，array这个引用变量指向堆中的数组对象。在递归过程中，虽然每个栈帧都有自己独立的array引用（但指向同一个堆中的数组），因此对数组的修改是全局生效的。例如在分区方法中修改数组元素，所有递归方法中看到的数组都是修改后的状态，这也是快速排序能实现原地排序的核心原因。
二、ArrayList底层数据结构与扩容机制
数组的核心痛点是长度固定，无法动态扩容，当数据量超过数组容量时，需要手动创建新数组并复制数据，开发效率低且易出错。ArrayList作为Java中最常用的可变数组，通过封装动态扩容的数组，解决了这一痛点，同时提供了高效的增删改查操作，是日常开发中的“高频工具类”。
底层封装与扩容策略
ArrayList的核心是封装一个动态扩容的数组，通过合理的扩容策略平衡内存占用和性能开销，其底层实现围绕初始容量、扩容触发条件和扩容规则展开。
默认容量与扩容触发条件
ArrayList采用“懒加载”策略，初始时底层数组为空，当首次添加元素时才会初始化底层数组。 默认初始容量：若创建ArrayList时未指定初始容量，底层数组的默认初始容量为10（JDK 1.8+）。 扩容触发条件：当ArrayList中元素的个数（size属性，记录有效数据的数量）等于底层数组的容量时，再次添加元素会触发扩容操作。例如底层数组容量为10，当size为10时，添加第11个元素就会触发扩容。
扩容倍数规则
扩容的核心是创建新数组并复制数据，ArrayList的扩容规则兼顾了性能和内存利用率，具体规则为： 新容量约为原容量的1.5倍。 计算公式：新容量 = 原容量 + 原容量右移1位（等价于原容量1.5）。例如原容量为10，右移1位是5，新容量为10+5=15；原容量为15，右移1位是7，新容量为15+7=22。
扩容流程：
- 计算新容量；
- 创建新数组，容量为新容量；
- 将原数组的所有元素复制到新数组；
- 将ArrayList的底层数组引用指向新数组；
- 后续添加元素直接在新数组中进行。
代码（ArrayList扩容逻辑）：
import java.util.Arrays; public class ArrayListSimulation { // 模拟ArrayList的核心属性：底层数组、有效元素个数 private Object[] elementData; private int size; // 构造方法：默认容量10 public ArrayListSimulation() { this.elementData = new Object[10]; this.size = 0; } // 构造方法：指定初始容量 public ArrayListSimulation(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException("初始容量不能为负数"); } this.elementData = new Object[initialCapacity]; this.size = 0; } // 添加元素：触发扩容的核心逻辑 public void add(Object e) { // 扩容检查：如果有效元素个数等于数组容量，需要扩容 if (size == elementData.length) { // 计算新容量：原容量 * 1.5（通过位运算实现，效率高） int newCapacity = elementData.length + (elementData.length >> 1); // 创建新数组 Object[] newArray = new Object[newCapacity]; // 复制原数组元素到新数组 System.arraycopy(elementData, 0, newArray, 0, size); // 指向新数组 elementData = newArray; System.out.println("触发扩容，原容量：" + (newCapacity - (newCapacity - elementData.length)) + ", 新容量：" + newCapacity); } // 在size位置添加元素，然后size++ elementData[size] = e; size++; } // 获取有效元素个数 public int size() { return size; } // 获取底层数组（用于测试） public Object[] getElementData() { return elementData; } public static void main(String[] args) { ArrayListSimulation list = new ArrayListSimulation(); // 添加11个元素，观察扩容过程 for (int i = 0; i < 11; i++) { list.add(i); } System.out.println("有效元素个数：" + list.size()); System.out.println("最终数组容量：" + list.getElementData().length); // 输出：添加第11个元素时触发扩容，原容量10，新容量15，最终数组容量15，有效元素个数11 } }增删改查的底层逻辑
ArrayList基于动态数组实现了高效的增删改查操作，核心是通过size属性控制有效数据的范围，避免操作底层数组的无效空间，同时针对不同操作优化了实现逻辑。
插入操作（Add）
插入操作的核心是“先检查扩容，再在指定位置插入，最后更新size”，分为在末尾插入和在指定位置插入两种情况，其中在指定位置插入需要移动后续元素。
末尾插入：直接将元素放在elementData[size]位置，然后size++，时间复杂度O(1)。
指定位置插入：
- 检查插入位置的合法性（位置必须在0到size之间）；
- 检查是否需要扩容；
- 将插入位置及之后的元素整体向后移动一位（从后往前移动，避免元素覆盖）；
- 在插入位置放入新元素；
size++，时间复杂度O(n)（移动元素开销）。
代码（指定位置插入逻辑）：
public class ArrayListAddSimulation { private Object[] elementData = new Object[10]; private int size = 0; // 指定位置插入元素 public void add(int index, Object e) { // 1. 检查索引合法性：0 <= index <= size if (index < 0 || index > size) { throw new IndexOutOfBoundsException("索引越界，允许范围[0," + size + "]"); } // 2. 检查扩容 if (size == elementData.length) { int newCapacity = elementData.length + (elementData.length >> 1); Object[] newArray = new Object[newCapacity]; System.arraycopy(elementData, 0, newArray, 0, size); elementData = newArray; } // 3. 移动元素：从size位置到index位置，依次后移一位（从后往前遍历，避免覆盖） for (int i = size; i > index; i--) { elementData[i] = elementData[i - 1]; } // 4. 插入元素 elementData[index] = e; // 5. 更新size size++; } // 获取元素（辅助方法） public Object get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界"); } return elementData[index]; } // 转换为字符串（仅打印有效元素） @Override public String toString() { if (size == 0) return "[]"; StringBuilder sb = new StringBuilder("["); for (int i = 0; i < size; i++) { sb.append(elementData[i]); if (i != size - 1) sb.append(","); } sb.append("]"); return sb.toString(); } public static void main(String[] args) { ArrayListAddSimulation list = new ArrayListAddSimulation(); list.add(0, "A"); list.add(1, "B"); list.add(1, "C"); // 在索引1插入C，原B后移 System.out.println(list); // 输出：[A,C,B]，说明插入后元素正确后移 } }删除操作（Remove）
删除操作分为删除指定位置元素和删除指定元素，核心是“移动后续元素覆盖待删除元素，再更新size”，同时需要注意遍历方向对删除结果的影响。
删除指定位置元素：
- 检查索引合法性；
- 将待删除位置之后的所有元素整体向前移动一位（从前往后移动）；
- 将最后一个元素置为null（帮助JVM回收，避免内存泄漏）；
size--，时间复杂度O(n)（移动元素开销）。
删除指定元素： 问题：若从前往后遍历，删除元素后索引会发生变化，可能导致漏删。例如数组[1,2,2,3]，从前往后删除2，第一次删除索引1的2后，后续元素前移，原索引2的2变为索引1，下一次遍历到索引2，会跳过这个2，导致漏删。
解决方案：从后往前遍历，删除元素后，后续元素的位置不影响前面的遍历，可避免漏删。因为从后往前删除时，删除元素的位置之前的元素索引不会发生变化，能保证所有符合条件的元素都被删除。
代码示例
public class ArrayListRemoveSimulation { private Object[] elementData = new Object[10]; private int size = 0; // 添加元素（辅助方法） public void add(Object e) { if (size == elementData.length) { int newCapacity = elementData.length + (elementData.length >> 1); elementData = new Object[newCapacity]; } elementData[size++] = e; } // 删除所有指定元素：从后往前遍历，避免漏删 public void remove(Object e) { // 从后往前遍历，找到等于e的元素并删除 for (int i = size - 1; i >= 0; i--) { if (elementData[i] == e || (elementData[i] != null && elementData[i].equals(e))) { // 移动元素：将i之后的元素向前移动一位 for (int j = i; j < size - 1; j++) { elementData[j] = elementData[j + 1]; } // 最后一个元素置null，避免内存泄漏 elementData[size - 1] = null; size--; } } } @Override public String toString() { if (size == 0) return "[]"; StringBuilder sb = new StringBuilder("["); for (int i = 0; i < size; i++) { sb.append(elementData[i]); if (i != size - 1) sb.append(","); } sb.append("]"); return sb.toString(); } public static void main(String[] args) { ArrayListRemoveSimulation list = new ArrayListRemoveSimulation(); list.add(1); list.add(2); list.add(2); list.add(3); System.out.println("删除前：" + list); // 输出：[1,2,2,3] list.remove(2); System.out.println("删除后：" + list); // 输出：[1,3]，所有2都被删除，无漏删 } }打印重写（ToString）
ArrayList重写了toString()方法，核心是仅遍历0到size-1的有效元素，而不是遍历整个底层数组，避免打印底层数组中预留的默认值（如null或0），确保输出结果只包含用户添加的有效元素。
原因：底层数组的容量可能大于size（例如扩容后容量为15，但size为11），剩余位置是未使用的，默认值为null（对象数组），如果遍历整个数组，会输出大量无意义的null，影响可读性。
实现逻辑：重写toString()时，通过循环遍历索引0到size-1的元素，拼接字符串，仅展示有效数据。
示例：
import java.util.ArrayList; public class ArrayListToStringDemo { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); // ArrayList重写toString，仅打印有效元素 System.out.println(list); // 输出：[1, 2, 3] // 若直接打印底层数组（假设获取到），会包含null Object[] arr = new Object[10]; arr[0] = 1; arr[1] = 2; arr[2] = 3; System.out.println(Arrays.toString(arr)); // 输出：[1, 2, 3, null, null, null, null, null, null, null]，包含大量null } }
