一、快速排序 QuickSort1. 算法思想分治思想选基准值以数组最左侧元素作为基准 base左右双指针遍历右指针先往左找小于基准的数左指针往右找大于基准的数两数交换指针相遇时基准归位此时基准左边全部≤基准右边全部≥基准递归处理基准左侧、右侧子数组直到区间只有一个元素递归终止2. 完整源码 QuickSort.javapackage com.qcby.sort; import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] arr {5,7,4,2,0,3,1,6}; sort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } /** * 快速排序递归方法 * param arr 待排序数组 * param left 左边界下标 * param right 右边界下标 */ public static void sort(int[] arr,int left,int right) { // 递归终止左边界右边界区间无元素/单个元素无需排序 if(leftright) { return; } // 选取最左侧作为基准值 int base arr[left]; int ileft; // 左指针 int jright; // 右指针 // 左右指针未相遇时循环遍历 while(i!j) { // 右指针向左寻找小于base的元素 while(arr[j]basei!j) { j--; } // 左指针向右寻找大于base的元素 while(arr[i]basei!j) { i; } // 交换i、j指针位置元素 int temp arr[i]; arr[i]arr[j]; arr[j]temp; } // 基准值归位把相遇位置元素放到原基准位基准放入中间分割点 arr[left]arr[i]; arr[i]base; // 递归排序左区间 [left, i-1] sort(arr,left,i-1); // 递归排序右区间 [i1, right] sort(arr,i1,right); } }3. 运行结果输入数组{5,7,4,2,0,3,1,6}输出[0, 1, 2, 3, 4, 5, 6, 7]4. 优缺点总结优点平均时间复杂度 O (nlogn)实际排序效率极高是工业最常用排序缺点最坏 O (n²)有序数组选首元素做基准递归深度大时会栈溢出二、手动模拟 ArrayList 底层实现需求说明基于原生数组手动实现简易 ArrayList实现三大核心功能add () 添加元素数组满时自动 1.5 倍扩容delete () 删除数组中所有匹配值的元素toString () 自定义格式化打印集合1. 自定义集合 ArrayList.javapackage com.qcby.array; public class ArrayList { // 底层存储数组初始容量10 int[] arr new int[10]; // 实际存储元素个数 int size 0; /** * 添加元素自动扩容 * param value 待添加数字 */ public void add(int value) { // 判断数组是否存满 if(sizearr.length) { // 扩容为原长度1.5倍 int[] brr new int[(int) (arr.length*1.5)]; // 拷贝旧数组数据到新数组 for(int i0;iarr.length;i) { brr[i]arr[i]; } // 底层数组指向扩容后的新数组 arrbrr; } // 存入元素 arr[size]value; // 有效元素数量1 size; } /** * 删除数组中所有等于value的元素 * param value 需要删除的目标值 */ public void delete(int value) { // 倒序遍历防止删除后元素前移导致漏删 for(int i size-1;i0;i--) { if(arr[i]value) { // 当前元素后所有元素向前覆盖一位 for(int ji1;jsize;j) { arr[j-1]arr[j]; } // 有效长度-1 size--; } } } /** * 重写toString格式化输出集合 */ public String toString() { String str [; for(int i0;isize;i) { if(isize-1) { str strarr[i]; }else { str strarr[i] , ; } } str str]; return str; } }2. 测试类 Test.javapackage com.qcby.array; public class Test { public static void main(String[] args) { ArrayList list new ArrayList(); // 添加大量测试数据触发自动扩容 list.add(10); list.add(5); list.add(14); list.add(1); list.add(26); list.add(7); list.add(26); list.add(19); list.add(31); list.add(26); list.add(26); list.add(179); list.add(20); list.add(26); list.add(50); list.add(80); list.add(90); System.out.println(原始集合list.toString()); list.delete(1); System.out.println(删除1后list.toString()); list.delete(26); System.out.println(删除全部26后list.toString()); } }3. 核心知识点解析1自动扩容机制底层数组初始容量10当size arr.length代表数组已满新建长度为原数组 1.5 倍的数组循环拷贝旧数组元素替换底层数组2删除设计倒序遍历正序遍历删除元素时数组元素前移会跳过下一个待判断元素出现漏删倒序从尾部向前遍历删除元素不会影响前面未遍历下标可删除所有匹配值3自定义 toString拼接字符串输出标准集合格式[10, 5, 14...]区分底层数组空余位置只打印有效 size 范围内元素三、总结快速排序不要忘记基准归位操作否则数组排序完全错乱递归终止条件leftright不能省略否则无限递归栈溢出自定义 ArrayList扩容必须替换底层数组引用arrbrr否则扩容失效删除必须倒序遍历否则重复元素无法全部删除size 代表有效元素个数打印、增删全部依赖 size不能使用数组 length四、拓展优化方向快速排序优化基准随机基准 / 三数取中法、小数组改用插入排序、非递归实现避免栈溢出自定义 ArrayList使用泛型支持任意引用类型、按下标删除、get/set 方法、缩容机制