前言本节课核心分为 4 大块1.基础简单排序冒泡、选择、插入2.递归基础快速排序前置知识3.快速排序递归实现效率最高4.java.util.Arrays 数组工具类常用方法排序统一默认规则从小到大升序如需降序交换比较判断逻辑即可。一、冒泡排序 BubbleSort1.核心思想相邻两个元素两两比较左小右大不满足则交换每一轮循环结束当前未排序区间最大值会 “冒泡” 到区间最右侧。2.执行规律1.数组长度为 N一共执行 N-1 轮最后只剩 1 个元素天然有序无需比较2.第 i 轮结束倒数第 i 个位置数字确定最大值固定3.每一轮内层循环次数比上一轮少 1 次右侧已有序数据不用重复比较3.易错点索引越界内层循环判断 arr[j] 和 arr[j1]因此 j 最大只能到 arr.length-2必须-1防止 j1 超出数组下标。4.完整代码publicclassBubbleDemo{publicstaticvoidmain(String[]args){int[]arr{2,4,5,3,1};// 外层循环控制总轮数 N-1轮for(inti0;iarr.length-1;i){// 内层循环每轮两两比较-i 跳过右侧已排序数据优化效率for(intj0;jarr.length-1-i;j){if(arr[j]arr[j1]){// 交换两个元素借助第三方临时变量inttemparr[j];arr[j]arr[j1];arr[j1]temp;}}}System.out.println(Arrays.toString(arr));}}5.优缺点•优点逻辑最简单、容易手写、理解门槛低•缺点大量交换操作效率极低适合小规模数组二、选择排序 SelectSort1.核心思想固定当前索引位置拿该位置元素与后面所有未排序元素逐一对比找到最小值后交换到当前固定索引。2.执行规律1.数组长度 N执行 N-1 轮2.第 i 轮i 索引及之前全部有序从 i 开始处理无序区间3.每一轮只交换 1 次找到最小值再交换对比冒泡减少交换次数3.完整代码publicclassSelectionDemo{publicstaticvoidmain(String[]args){int[]arr{3,5,2,1,4};// 外层控制轮数i代表当前要放最小值的位置for(inti0;iarr.length-1;i){// 内层从i1开始和i位置元素对比for(intji1;jarr.length;j){if(arr[i]arr[j]){// 交换inttemparr[i];arr[i]arr[j];arr[j]temp;}}}System.out.println(Arrays.toString(arr));}}4.优缺点•优点交换次数远少于冒泡排序•缺点比较次数依旧很多整体效率仍偏低三、插入排序 InsertSort1.核心思想把数组分为左边有序区、右边无序区依次取出无序区第一个元素从后往前插入到有序区合适位置保证有序区始终升序。类比抓扑克牌手里是有序牌新摸到的牌依次插入对应位置。2.执行规律1.默认第 0 个元素天然有序无序区从索引 1 开始2.取出待插入元素向前循环对比若前面数字更大则后移直到找到插入位置3.稳定排序相等元素相对顺序不变3. 完整代码publicclassInsertDemo{publicstaticvoidmain(String[]args){int[]arr{3,44,38,5,47,15};// i无序区第一个元素索引从1开始for(inti1;iarr.length;i){intji;// j记录当前待插入元素下标单独变量避免破坏外层i// j0 防止越界当前数字 前一个数字则交换while(j0arr[j]arr[j-1]){inttemparr[j];arr[j]arr[j-1];arr[j-1]temp;j--;// 继续向前对比}}System.out.println(Arrays.toString(arr));}}4.优缺点•优点数据接近有序时效率极高稳定排序•缺点大规模乱序数组性能差四、递归快速排序前置1.递归定义方法内部调用自身的编程方式核心大事化小将大问题拆分为同类型小规模子问题。2. 递归两大必备条件缺一不可否则栈溢出递归出口终止条件满足时不再调用自身直接返回结果递推公式拆分逻辑每次调用参数向出口靠近3. 常见练习 1递归求 1~n 累加和公式getSum(n) n getSum(n-1)出口n 1 ; return 1publicstaticintgetSum(intnumber){if(number1){return1;// 出口}returnnumbergetSum(number-1);}调用 getSum(100) 结果 50504. 常见练习 2递归求阶乘 n!阶乘定义5! 5×4×3×2×1公式factorial(n) n * factorial(n-1)出口n 1 ; return 1publicstaticintgetJC(intnumber){if(number1){return1;}returnnumber*getJC(number-1);}调用 getJC(5) 结果 1205. 递归内存原理1.方法调用会压入栈内存main 方法最先入栈2.每次递归调用生成新的方法栈帧参数逐层减小3.触发出口后逐层返回结果方法依次出栈6. 常见报错StackOverflowError 栈内存溢出缺少递归出口 / 递归深度过大五、快速排序 QuickSort重点1.核心特点平均效率最高实际开发常用底层基于分治 递归2. 核心思想分治选定基准数 base教程默认取区间最左侧元素 arr[i]双指针start 从左找大于基准的数end 从右找小于基准的数两指针找到目标元素后交换直到 start end基准最终位置基准归位基准放到 start 下标此时基准左侧全部更小右侧全部更大递归处理基准左侧区间、右侧区间直到区间只有 1 个元素递归出口3. 关键硬性规则极易踩坑若基准取区间第一个元素循环查找时必须先移动 end 指针再移动 start 指针•先动 end相遇位置数字一定小于基准归位后满足左小右大•先动 start相遇位置数字大于基准归位破坏排序规则4. 完整递归代码importjava.util.Arrays;publicclassQuickSortDemo{publicstaticvoidmain(String[]args){int[]arr{6,1,2,7,9,3,4,5,1,8};quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}// arr数组 i区间左边界 j区间右边界publicstaticvoidquickSort(int[]arr,inti,intj){// 递归出口左边界 右边界区间无元素/只有1个无需排序if(ij){return;}intstarti;intendj;intbasearr[i];// 基准数取区间最左侧// 双指针循环直到start与end相遇while(start!end){// 1. 先移动end从右往左找 base 的数字while(startendarr[end]base){end--;}// 2. 再移动start从左往右找 base 的数字while(startendarr[start]base){start;}// 交换start、end指向元素inttemparr[start];arr[start]arr[end];arr[end]temp;}// 基准归位交换左边界i和相遇点startinttemparr[i];arr[i]arr[start];arr[start]temp;// 递归处理左区间 i ~ start-1quickSort(arr,i,start-1);// 递归处理右区间 start1 ~ jquickSort(arr,start1,j);}}5. 效率说明百万级随机数组排序速度远快于冒泡、选择、插入极端有序数组会退化日常场景最优。六、Arrays 数组工具类java.util.Arrays基础信息1.包路径java.util.Arrays使用必须导包2.无构造方法所有方法static 静态直接类名.方法名()调用常用方法汇总1.toString (数组)数组转字符串快速打印数组内容不用手动遍历int[]arr{1,3,2};System.out.println(Arrays.toString(arr));// [1, 3, 2]2.sort (数组)基础升序排序•基本数据类型数组底层快速排序默认升序int[]arr{3,1,2};Arrays.sort(arr);•引用类型数组Integer/String重载方法 sort(数组, Comparator)可自定义升降序注意仅支持包装类int 数组不能直接使用自定义比较器3.binarySearch (有序数组查找值)二分查找前置条件数组必须升序有序返回值规则1.元素存在返回对应下标2.元素不存在-(插入点)-1插入点该数字应该插入的位置保证数组有序减 1 是为了区分插入点 0防止返回 0 歧义示例数组 [2,4,6,8]查找 5 → 插入点 2返回 -2-1 -34.copyOf (原数组新数组长度)数组拷贝底层依赖System.arraycopy自动创建新数组1.新长度 原长度截取前半部分2.新长度 原长度完整复制3.新长度 原长度复制全部剩余位置填充默认值int 填 0int[]old{1,2,3};int[]newArrArrays.copyOf(old,5);// [1,2,3,0,0]*5.copyOfRange(数组from,to)区间拷贝*规则包头不包尾[from,to)包含 from 索引不包含to索引 javaint[]arr{1,2,3,4,5};int[]subArrays.copyOfRange(arr,1,4);// [2,3,4]6.fill (数组填充值)数组批量填充覆盖数组原有全部元素统一赋值int[]arrnewint[5];Arrays.fill(arr,100);// [100,100,100,100]七、四种基础排序对比速记表八、复习易错点汇总1.冒泡内层循环必须-1防下标越界-i优化有序区间2.选择排序内层循环从i1开始不要和自身对比3.插入排序单独定义 j 变量避免修改外层循环 i4.递归必须写出口否则栈溢出每次递归参数向出口靠近5.基准取左边界时快排双指针先移动 end 再移动 start6.Arrays.binarySearch 只对升序数组生效无序数组结果无意义7.copyOfRange 包头不包尾copyOf 长度超过原数组填充默认值
