扑克牌游戏各种算法优劣

一、问题描述

模拟手动整理扑克牌的业务场景：

1. 初始状态：左手为空，桌面摊放无序扑克牌，对应数字数组{789, 678, 456, 345, 123, 90, 89, 67, 45, 34}；
2. 操作规则：每一轮从桌面从右至左完整扫描，找出当前桌面上数值最大的扑克牌，移至左手作为有序区；重复操作直至桌面无牌，最终实现所有数字从小到大升序；
3. 输出规范：每完成一轮取最大值操作，打印当前完整数组状态；全部排序结束后输出全局元素总比较次数。

二、四种实现方案完整解析

方案 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 计算次数为：45

3. 算法核心原理

相邻元素两两对比，若逆序则交换；每一轮遍历后，当前无序区间内最大值会 “上浮” 至数组末尾，等价于把桌面最大扑克牌移动至左手有序区边界。

4. 优缺点

优点

1. 逻辑简单直观，无递归、分区等复杂操作，新手极易理解、手写；
2. 原地排序，空间复杂度 \(O(1)\)，仅使用交换临时变量，内存占用极低；
3. 稳定排序，相等数值元素的原始相对顺序不会改变；
4. 可优化：增加交换标记，一轮无交换代表数组已有序，可直接终止循环；
5. 每轮完整打印原始数组，输出格式完全匹配题目要求。

缺点

1. 时间效率差：平均、最坏时间复杂度 \(O(n^2)\)；本案例数组完全逆序，触发最坏性能；仅完全有序数组可达到最优 \(O(n)\)；
2. 元素交换开销大：逆序相邻元素都需要交换，交换次数远高于选择类排序；
3. 不支持分治优化，无法达到 \(O(n\log n)\) 高效时间复杂度；
4. 仅适用于少量数据，大规模业务场景不会使用。

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. 高度贴合扑克牌场景：逻辑完全对应 “从左至右扫描桌面、选出最大牌移至左手” 的操作；
2. 交换开销极低：每轮仅 1 次元素交换，对比冒泡大量相邻交换性能更优；
3. 原地排序，空间复杂度 \(O(1)\)；
4. 输出格式、轮次逻辑完全匹配题目规范。

缺点

1. 内层必须完整遍历无序区间，平均、最坏时间复杂度 \(O(n^2)\)；
2. 仅借用快排遍历逻辑，未使用分治递归优化，不具备 \(O(n\log n)\) 效率；
3. 不稳定排序，相等元素原始相对顺序会被打乱；
4. 数组接近有序时无法提前终止，必须执行全部轮次。

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 计算次数为：19

3. 算法核心原理

将数组划分为左侧有序区、右侧无序区；依次取出无序区第一个元素，通过二分查找快速定位有序区插入下标，批量后移元素完成插入，逐步扩充有序区间实现升序。

4. 优缺点

优点

1. 比较次数最优：二分查找将对比次数由线性降至对数级，本案例仅 19 次比较，远少于冒泡、最值选择；
2. 稳定排序，相等元素相对顺序保留；
3. 原地排序，空间复杂度 \(O(1)\)；
4. 数组越接近有序，整体执行效率越高。

缺点

1. 整体时间复杂度仍为 \(O(n^2)\)：二分仅优化对比次数，元素批量后移操作仍是线性开销；
2. 逻辑与题目 “扫描桌面取最大牌” 场景贴合度低，无法直观模拟手动操作；
3. 无分治并行优化能力，海量数据场景效率低下。

5. 适用场景

小批量数据、需要最小化元素比较次数、数组接近有序、要求稳定排序的场景。

方案 4：ArrayList 集合版二分插入排序（二分制排序）

1. 完整 Java 代码

java

运行

import java.util.ArrayList; import java.util.List; public class InsertSort { static int counts = 0; /** * 二分查找有序集合的插入下标，并完成插入 */ public static List<Integer> binarySort(List<Integer> 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) { List<Integer> 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. 核心设计思路（结合扑克牌场景）

1. 数据结构映射
   • int[] datas：桌面无序扑克牌；
   • ArrayList list：左手存放的有序牌堆（有序区）；
2. 执行流程循环依次取出桌面单张牌，通过二分查找找到在左手有序牌堆的正确位置，调用list.add(low, num)自动完成元素后移插入；
3. 计数规则
   • 第一张牌直接存入，无二分对比，手动计数counts++；
   • 后续每张牌二分查找时，每一次数值对比执行一次counts++，总比较次数 19，与数组版二分插入完全一致；
4. 打印逻辑list.size()代表当前左手牌堆数量，仅打印已拿在手中的有序扑克牌，视觉贴合 “左手有序区” 设定。

3. 与数组版二分插入排序异同

相同点

1. 核心逻辑均为二分查找优化插入位置，总比较次数均为 19；
2. 稳定排序，最终升序结果一致；
3. 时间复杂度 \(O(n^2)\)，二分仅优化对比次数，元素移位为线性开销。

不同点

表格

4. 本方案优缺点

优点

1. 场景贴合度高：ArrayList 天然模拟左手有序牌堆，输出仅展示已整理好的牌；
2. 代码简洁：依托集合内置方法省去手动移位循环；
3. 对比次数最少，查询效率最优；
4. 稳定排序，相等元素顺序不变；
5. 动态容器无需提前定义数组长度，增删操作便捷。

缺点

1. 底层时间复杂度仍为 \(O(n^2)\)，大批量数据效率差；
2. ArrayList 中间插入会触发底层数组拷贝，大批量插入性能弱于原生数组；
3. 不匹配题目 “从右往左扫描桌面找最大值” 核心操作逻辑，仅最终排序结果一致；
4. 无法纯原地排序，存在额外内存占用。

三、四种算法横向综合对比总表

表格

四、整体总结

1. 若严格还原题目桌面从右至左扫描、逐次取出全局最大牌的手动操作逻辑：优先选择【快排思想最值选择排序】，行为逻辑与题目完全对应；
2. 若面向零基础教学、追求最简单易懂的代码：选择【冒泡排序】；
3. 若核心需求是尽可能减少元素比较次数、数组接近有序：优先选择二分插入排序，其中原生数组版本内存开销更低；
4. 若需要直观展示 “左手有序牌堆”、简化元素移位代码：选择【ArrayList 集合版二分插入排序】；
5. 四种方案均属于平方阶基础排序算法，仅适用于少量扑克牌 / 数字；若处理大规模数据，应使用原生快速排序、归并排序等 \(O(n\log n)\) 级高效分治排序。