扑克牌游戏各种算法优劣

一、问题描述模拟手动整理扑克牌的业务场景初始状态左手为空桌面摊放无序扑克牌对应数字数组{789, 678, 456, 345, 123, 90, 89, 67, 45, 34}操作规则每一轮从桌面从右至左完整扫描找出当前桌面上数值最大的扑克牌移至左手作为有序区重复操作直至桌面无牌最终实现所有数字从小到大升序输出规范每完成一轮取最大值操作打印当前完整数组状态全部排序结束后输出全局元素总比较次数。二、四种实现方案完整解析方案 1冒泡排序实现1. 完整 Java 代码java运行public class InsertSort { public static void bubbleSort(int[] datas) { int count 0; int len datas.length; // 外层循环一共执行len-1轮排序 for (int i 0; i len - 1; i) { // 内层相邻元素比较将小值逐步向后沉 for (int j 0; j len - 1 - i; j) { count; // 每次相邻对比比较次数1 if (datas[j] datas[j 1]) { // 逆序则交换两个相邻元素 int temp datas[j]; datas[j] datas[j 1]; datas[j 1] temp; } } // 按指定格式打印本轮数组 System.out.print(第 (i 1) 次的排序结果为); for (int num : datas) { System.out.print(num \t); } System.out.println(); } System.out.println(计算次数为 count); } public static void main(String[] args) { int datas[] {789, 678, 456, 345, 123, 90, 89, 67, 45, 34}; bubbleSort(datas); } }2. 运行输出结果plaintext第1次的排序结果为678 456 345 123 90 89 67 45 34 789 第2次的排序结果为456 345 123 90 89 67 45 34 678 789 第3次的排序结果为345 123 90 89 67 45 34 456 678 789 第4次的排序结果为123 90 89 67 45 34 345 456 678 789 第5次的排序结果为90 89 67 45 34 123 345 456 678 789 第6次的排序结果为89 67 45 34 90 123 345 456 678 789 第7次的排序结果为67 45 34 89 90 123 345 456 678 789 第8次的排序结果为45 34 67 89 90 123 345 456 678 789 第9次的排序结果为34 45 67 89 90 123 345 456 678 789 计算次数为453. 算法核心原理相邻元素两两对比若逆序则交换每一轮遍历后当前无序区间内最大值会 “上浮” 至数组末尾等价于把桌面最大扑克牌移动至左手有序区边界。4. 优缺点优点逻辑简单直观无递归、分区等复杂操作新手极易理解、手写原地排序空间复杂度 \(O(1)\)仅使用交换临时变量内存占用极低稳定排序相等数值元素的原始相对顺序不会改变可优化增加交换标记一轮无交换代表数组已有序可直接终止循环每轮完整打印原始数组输出格式完全匹配题目要求。缺点时间效率差平均、最坏时间复杂度 \(O(n^2)\)本案例数组完全逆序触发最坏性能仅完全有序数组可达到最优 \(O(n)\)元素交换开销大逆序相邻元素都需要交换交换次数远高于选择类排序不支持分治优化无法达到 \(O(n\log n)\) 高效时间复杂度仅适用于少量数据大规模业务场景不会使用。5. 适用场景课堂教学演示、100 以内极小数据集、需要稳定排序、要求完整展示每一步数组变化的场景。方案 2基于快速排序分区思想的最值选择排序1. 完整 Java 代码java运行public class InsertSort { // 全局统计元素比较总次数 private static int count 0; /** * 借用快速排序区间遍历思想查找指定区间[left,right]最大值下标 */ private static int findMaxByQuickPartition(int[] arr, int left, int right) { int maxIdx left; for (int i left; i right; i) { count; if (arr[i] arr[maxIdx]) { maxIdx i; } } return maxIdx; } public static void main(String[] args) { int[] datas {789, 678, 456, 345, 123, 90, 89, 67, 45, 34}; int len datas.length; // 共len-1轮每轮提取当前无序区最大值放到数组尾部 for (int i 1; i len - 1; i) { int unSortRight len - i; int maxIndex findMaxByQuickPartition(datas, 0, unSortRight); // 将最大值交换至无序区末尾 int temp datas[maxIndex]; datas[maxIndex] datas[unSortRight]; datas[unSortRight] temp; // 规范打印每一轮完整数组 System.out.print(第 i 次的排序结果为); for (int num : datas) { System.out.print(num \t); } System.out.println(); } System.out.println(计算次数为 count); } }2. 运行输出数组打印内容、格式与冒泡排序完全一致总比较次数同样为45。3. 算法核心原理外层循环严格模拟题目 “每次取桌面最大牌” 流程内层借鉴快速排序区间遍历逻辑完整扫描无序区间找到最大值下标每一轮仅执行 1 次交换直接将最大值移至有序区边界。4. 优缺点优点高度贴合扑克牌场景逻辑完全对应 “从左至右扫描桌面、选出最大牌移至左手” 的操作交换开销极低每轮仅 1 次元素交换对比冒泡大量相邻交换性能更优原地排序空间复杂度 \(O(1)\)输出格式、轮次逻辑完全匹配题目规范。缺点内层必须完整遍历无序区间平均、最坏时间复杂度 \(O(n^2)\)仅借用快排遍历逻辑未使用分治递归优化不具备 \(O(n\log n)\) 效率不稳定排序相等元素原始相对顺序会被打乱数组接近有序时无法提前终止必须执行全部轮次。5. 适用场景需要严格还原 “逐次提取全局最大值” 操作、小批量数据、需要控制元素交换次数的场景。方案 3数组版二分插入排序二分制排序1. 完整 Java 代码java运行public class InsertSort { // 统计二分查找比较次数 private static int count 0; public static void binaryInsertSort(int[] arr) { int len arr.length; // 从第二个元素开始向前插入 for (int i 1; i len; i) { int temp arr[i]; int left 0; int right i - 1; // 二分查找有序区内的插入位置优化比较次数 while (left right) { count; int mid (left right) / 2; if (temp arr[mid]) { right mid - 1; } else { left mid 1; } } // 将大于temp的元素统一后移 for (int j i - 1; j left; j--) { arr[j 1] arr[j]; } arr[left] temp; // 打印本轮排序后的完整数组 System.out.print(第 i 次的排序结果为); for (int num : arr) { System.out.print(num \t); } System.out.println(); } System.out.println(计算次数为 count); } public static void main(String[] args) { int datas[] {789, 678, 456, 345, 123, 90, 89, 67, 45, 34}; binaryInsertSort(datas); } }2. 运行输出plaintext第1次的排序结果为678 789 456 345 123 90 89 67 45 34 第2次的排序结果为456 678 789 345 123 90 89 67 45 34 第3次的排序结果为345 456 678 789 123 90 89 67 45 34 第4次的排序结果为123 345 456 678 789 90 89 67 45 34 第5次的排序结果为90 123 345 456 678 789 89 67 45 34 第6次的排序结果为89 90 123 345 456 678 789 67 45 34 第7次的排序结果为67 89 90 123 345 456 678 789 45 34 第8次的排序结果为45 67 89 90 123 345 456 678 789 34 第9次的排序结果为34 45 67 89 90 123 345 456 678 789 计算次数为193. 算法核心原理将数组划分为左侧有序区、右侧无序区依次取出无序区第一个元素通过二分查找快速定位有序区插入下标批量后移元素完成插入逐步扩充有序区间实现升序。4. 优缺点优点比较次数最优二分查找将对比次数由线性降至对数级本案例仅 19 次比较远少于冒泡、最值选择稳定排序相等元素相对顺序保留原地排序空间复杂度 \(O(1)\)数组越接近有序整体执行效率越高。缺点整体时间复杂度仍为 \(O(n^2)\)二分仅优化对比次数元素批量后移操作仍是线性开销逻辑与题目 “扫描桌面取最大牌” 场景贴合度低无法直观模拟手动操作无分治并行优化能力海量数据场景效率低下。5. 适用场景小批量数据、需要最小化元素比较次数、数组接近有序、要求稳定排序的场景。方案 4ArrayList 集合版二分插入排序二分制排序1. 完整 Java 代码java运行import java.util.ArrayList; import java.util.List; public class InsertSort { static int counts 0; /** * 二分查找有序集合的插入下标并完成插入 */ public static ListInteger binarySort(ListInteger list, int num) { int high, low, mid; low 0; high list.size() - 1; while (low high) { counts; mid (low high) / 2; if (num list.get(mid)) { high mid - 1; } else { low mid 1; } } list.add(low, num); return list; } /** * 二分插入排序主流程 * param n 待排序元素总数量 */ public static void method3(int n) { ListInteger list new ArrayList(); int datas[] {789, 678, 456, 345, 123, 90, 89, 67, 45, 34}; for (int i 0; i n; i) { if (list.size() 0) { // 有序集合为空直接存入第一张牌 list.add(datas[i]); counts; } else { list binarySort(list, datas[i]); } // 仅打印左手有序牌堆 System.out.print(第 list.size() 次的排序结果为); for (int j 0; j list.size(); j) { System.out.print(list.get(j) \t); } System.out.println(); } System.out.println(计算次数为 counts); } public static void main(String[] args) { method3(10); } }2. 核心设计思路结合扑克牌场景数据结构映射int[] datas桌面无序扑克牌ArrayList list左手存放的有序牌堆有序区执行流程循环依次取出桌面单张牌通过二分查找找到在左手有序牌堆的正确位置调用list.add(low, num)自动完成元素后移插入计数规则第一张牌直接存入无二分对比手动计数counts后续每张牌二分查找时每一次数值对比执行一次counts总比较次数 19与数组版二分插入完全一致打印逻辑list.size()代表当前左手牌堆数量仅打印已拿在手中的有序扑克牌视觉贴合 “左手有序区” 设定。3. 与数组版二分插入排序异同相同点核心逻辑均为二分查找优化插入位置总比较次数均为 19稳定排序最终升序结果一致时间复杂度 \(O(n^2)\)二分仅优化对比次数元素移位为线性开销。不同点表格对比维度数组版二分插入ArrayList 二分插入排序存储容器固定长度原生数组 int []动态可变长 ArrayList 集合元素移位手动 for 循环批量移位集合add(index,val)底层自动移位代码简洁空间开销\(O(1)\) 原地排序底层数组预留扩容空间额外内存开销更大代码可读性需要手动控制下标移位循环二分逻辑封装独立方法分层清晰打印内容完整打印原始数组有序 无序仅打印左手有序区贴合题目左手场景4. 本方案优缺点优点场景贴合度高ArrayList 天然模拟左手有序牌堆输出仅展示已整理好的牌代码简洁依托集合内置方法省去手动移位循环对比次数最少查询效率最优稳定排序相等元素顺序不变动态容器无需提前定义数组长度增删操作便捷。缺点底层时间复杂度仍为 \(O(n^2)\)大批量数据效率差ArrayList 中间插入会触发底层数组拷贝大批量插入性能弱于原生数组不匹配题目 “从右往左扫描桌面找最大值” 核心操作逻辑仅最终排序结果一致无法纯原地排序存在额外内存占用。三、四种算法横向综合对比总表表格对比维度冒泡排序快排思想最值选择排序数组二分插入排序ArrayList 二分插入排序本案例总比较次数45 次45 次19 次19 次存储容器固定 int 数组固定 int 数组固定 int 数组动态 ArrayList 集合打印内容完整原始数组有序 无序完整原始数组有序 无序完整原始数组有序 无序仅打印左手有序区元素移位方式相邻元素两两交换每轮仅交换 1 次最大值手动循环批量后移集合底层自动移位贴合题目 “扫描取最大牌” 场景一般高度贴合不贴合不贴合代码实现难度极低低中等中等集合 二分排序稳定性稳定不稳定稳定稳定空间复杂度\(O(1)\)\(O(1)\)\(O(1)\)略高于\(O(1)\)集合扩容最优时间复杂度\(O(n)\)有序优化\(O(n^2)\)\(O(n^2)\)\(O(n^2)\)最坏 / 平均复杂度\(O(n^2)\)\(O(n^2)\)\(O(n^2)\)\(O(n^2)\)四、整体总结若严格还原题目桌面从右至左扫描、逐次取出全局最大牌的手动操作逻辑优先选择【快排思想最值选择排序】行为逻辑与题目完全对应若面向零基础教学、追求最简单易懂的代码选择【冒泡排序】若核心需求是尽可能减少元素比较次数、数组接近有序优先选择二分插入排序其中原生数组版本内存开销更低若需要直观展示 “左手有序牌堆”、简化元素移位代码选择【ArrayList 集合版二分插入排序】四种方案均属于平方阶基础排序算法仅适用于少量扑克牌 / 数字若处理大规模数据应使用原生快速排序、归并排序等 \(O(n\log n)\) 级高效分治排序。