如果把“ASC 码表”和“快速排序”放在一起看很多人会觉得一个考记忆、一个考算法没什么关系。实际上它们的关系很直接快速排序要反复比较两个元素的大小而做字符排序时这个大小标准就是 ASC 码表上的码值。对初学者来说先搞懂码表再写一次快速排序很多关于字符串排序、字典序、字符乱序的困惑会一起解开。这篇文章我打算按一条完整链路来拆先讲清楚 ASC 码表到底在排什么再讲快速排序的核心思路然后分别用 C 语言和 Java 把代码跑起来最后补上字符排序、重复元素、有序数组等场景下的坑和优化方向。不管你是刚学数据结构还是准备笔试手写快排都可以照着复现一遍。1. 先看 ASC 码表字符排序时的“大小规则”1.1 ASC、ASCII、ASCLL 到底哪个准确很多人会直接搜“ASC 码表”也见过搜“ASCLL”“ASKII”的。标准写法是ASCII全称 American Standard Code for Information Interchange中文一般叫“美国信息交换标准代码”。它做的事情是把英文字母、数字、符号、控制字符和数字编号对应起来。需要先避免一个概念误区ASCII 不是一个“排序算法”而是一张“字符编码表”。它的作用是告诉你当程序说char a A时这个A在内存里实际对应的数值是什么。标准 ASCII 的范围是 0 到 127一共 128 个字符其中 0 到 31 是控制字符32 到 126 是可打印字符127 是 DEL 删除字符。128 到 255 被称为扩展 ASCII但不同系统和字符集实现有差异初学阶段主要记 0 到 127 就够用。有个好处是现代字符集基本都向下兼容 ASCII。比如 Unicode 的前 128 个码位和 ASCII 完全一致。所以在 Java、Python、C、JavaScript 这些常见环境里只要操作的是英文字母、数字、英文标点比较字符大小本质上就是在比较 ASCII 码值。1.2 必背码值0、32、48、65、97、127记忆 ASCII 码表不需要把 0 到 127 全部背下来真正高频的是下面这些锚点。只要记住这些其他数字就能推导出来。含义十进制码值记忆锚点NUL 空字符0C 字符串的结束符\0LF 换行10对应代码里的\nCR 回车13对应代码里的\r空格32可打印字符的起点048数字字符起点从 48 到 57A65大写字母起点从 65 到 90a97小写字母起点从 97 到 122DEL 删除127标准 ASCII 最后一位比较常见的手写大小写转换也和这张表有关。因为大写字母A是 65小写字母a是 97两者相差 32。所以char c A; c 32;就可以得到a。这里最容易忽略的是“大小写字母并不是紧挨着排列的”。ASCII 的顺序是控制字符、标点符号、数字0-9、大写字母A-Z、部分标点、小写字母a-z、最后是 DELETE。因此按 ASCII 排序时0 A Z a z是确定的事实。很多人以为先有大写后有小写但实际上大写和小写之间夹着 [ \ ] ^ _ 这四个标点。1.3 字符比较的时候程序到底在比较什么在 C 语言中char本质上是整数类型。字符字面量A参与运算时实际使用的是码值 65。所以下面的写法在语法上没有问题char ch A; if (ch 0) { // 实际比较的是 65 48 }Java 里的char是无符号 16 位整数A也是 65。但要注意Java 的char是 Unicode 编码单元可以表示中文。中文字符的码值远大于 127所以一个中文中和一个英文a并没有所谓“ASCII 比较”而是走了 Unicode 码值比较。对于英文字符Unicode 前 128 位和 ASCII 完全一致这一点不影响日常使用。字符串比较则更加直观。比如 Java 中两个字符串调用compareTo会从第一个字符开始逐位比较码值如果第一个字符不同直接按码值决定大小。如果第一个字符相同继续比较第二个字符。如果前面所有字符都相同短的字符串更小。如果完全相同返回 0。这也是很多排序结果看起来“不符合直觉”的原因。比如Apple和banana比较时A 65b 98所以程序会认为Apple banana。但在日常按字母表排序时我们通常会把大小写视为同一级。计算机只认码值所以结果就是大写排前、小写排后。1.4 码表在实践里最常见的用途不要以为 ASCII 码表只是笔试里的背诵题。实际编码中很多基础逻辑都会用到这些码值。第一个是大小写转换。当你需要自己实现转换而不是调用现成 API 时一般写法是if (c A c Z) { c (char) (c 32); }第二个是数字字符转整型。比如把5转成数字 5int value 5 - 0;因为字符0到9的码值是连续的 48 到 57所以差值正好是数字本身。第三个是字符串数组排序。如果需要按字典序排字符串程序每比较两个字符实际比较的就是码值。只要碰到英文字符串最终效果由 ASCII 表决定碰到中文字符串则要看具体字符编码环境不能完全照搬 ASCII。我建议你把码表看成“排序规则的定义”而不是一个孤立知识点。快速排序里比较两个字符最终要比的就是这些数字。2. 快速排序核心原理先理解一次划分2.1 快速排序最有价值的一句话快速排序是典型的分治算法。处理一个数组时先选一个元素作为基准值 pivot然后通过一轮分区操作让基准值左侧的元素都小于等于它右侧的元素都大于等于它。分区结束后基准值已经回到它最终应该处于的位置。接下来对左右两个子区间分别递归做同样的操作。在数组完全有序后二分结构自然形成算法结束。快速排序之所以叫“快速”不是因为代码看起来短而是因为每一轮分区都能把一个元素放到最终位置并且对数据做了近似二分平均时间复杂度能做到 O(n log n)。2.2 挖坑法逐步推演一轮分区快速排序的分区实现方式有很多种比如 Lomuto 分区、Hoare 分区、挖坑法。对新手来说挖坑法最容易在纸上模拟也容易理解“为什么最后要把 pivot 填回去”。这里用一个例子[3, 6, 2, 8, 1, 9, 4, 7, 5]取第一个元素3作为 pivot。把 low 位置看作一个“坑”因为 pivot 已经把arr[0]的值取出来了。初始状态索引: 0 1 2 3 4 5 6 7 8 值: 3 6 2 8 1 9 4 7 5 坑: 0 (arr[0] 已被 pivot 保存)从右侧向左找小于 pivot 的元素。5、7、4、9都不小于3继续向左找到1。1比3小把1填到索引 0索引 4 变成新坑1 6 2 8 1 9 4 7 5 坑: 4注意这时候索引 4 的值还是1但逻辑上它的值已经被复制走了可以覆盖。接着从左向右找大于 pivot 的元素。6比3大把6填到索引 4索引 1 变成新坑1 6 2 8 6 9 4 7 5 坑: 1再从右往左找小于 pivot 的元素。索引 3 的8不小于 3继续向左索引 2 的2小于 3把2填到索引 1索引 2 变成新坑1 2 2 8 6 9 4 7 5 坑: 2此时 left 指针和 right 指针相遇都在索引 2。把保存的 pivot 值3填回坑中1 2 3 8 6 9 4 7 5至此第一轮分区结束。返回基准值索引 2。可以看到索引 2 左侧是1和2都小于 3右侧是8、6、9、4、7、5都大于 3。3已经放到了最终位置接下来只需要对[0, 1]和[3, 8]两个子区间递归排序。2.3 为什么要先从右侧找挖坑法里基准值取的是arr[low]所以初始坑在左侧。先从右侧找一个小于 pivot 的元素把左侧的坑填掉左侧少了坑右侧多了一个“空位”然后再从左向右找一个大于 pivot 的元素填右侧。整个过程是“交替填坑”。如果你把顺序反了也不是完全不能实现但代码逻辑就要改。对新手而言最容易复现的还是固定写法基准在左先右后左。这么做的根本目的是保证任意时刻都留有一个可以覆盖的坑位直到左右指针相遇再将 pivot 放入最终的坑。2.4 快速排序的复杂度和稳定性边界快速排序的复杂度并不是固定不变的平均时间复杂度O(n log n)最坏时间复杂度O(n^2)平均额外空间O(log n)主要来自递归调用栈最坏额外空间O(n)最坏情况通常发生在每次选到的基准值都是当前区间最大值或最小值时。比如对一个已经排好序的数组如果仍然固定取第一个元素作为 pivot那么每次分区都只能排除一个元素递归深度接近 n。快速排序也不是稳定排序。这里说的“稳定”是指如果两个元素排序键相同排序后它们的相对顺序是否保持不变。快速排序在交换过程中可能越过相同键的元素所以无法保证稳定。如果业务场景要求排序稳定应该优先用归并排序而不是快速排序。需要注意的是代码里内层循环的条件要写或不能只写或。如果遇到相同值缺少等号可能导致指针无法越过相等元素极端情况下会出现死循环。3. 用两套代码跑通快速排序3.1 C 语言版快速排序下面是一份可以直接编译运行的 C 语言快速排序分区采用挖坑法。#include stdio.h int partition(int arr[], int low, int high) { int pivot arr[low]; int i low; int j high; while (i j) { while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; i; } while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; j--; } } arr[i] pivot; return i; } void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } int main() { int arr[] {3, 6, 2, 8, 1, 9, 4, 7, 5}; int n sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); for (int i 0; i n; i) { printf(%d , arr[i]); } return 0; }预期输出是1 2 3 4 5 6 7 8 9如果你运行结果不是这样优先检查两个地方第一个是递归区间左区间是[low, pi - 1]右区间是[pi 1, high]不要把 pivot 自己也传进去第二个是内层条件是否漏了等号漏等号在重复元素多的数组上容易出现死循环。3.2 Java 版快速排序Java 版本的逻辑和 C 语言一致只是数组获取长度的方式不同。下面是完整可运行的示例import java.util.Arrays; public class QuickSortDemo { public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int index partition(arr, left, right); quickSort(arr, left, index - 1); quickSort(arr, index 1, right); } public static int partition(int[] arr, int left, int right) { int pivot arr[left]; int i left; int j right; while (i j) { while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; i; } while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; j--; } } arr[i] pivot; return i; } public static void main(String[] args) { int[] arr {3, 6, 2, 8, 1, 9, 4, 7, 5}; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } }Java 实现中要注意一点数组下标从 0 开始所以第一次调用传入arr.length - 1不是arr.length。如果写成arr.length会在递归中越界或漏排最后一个元素。3.3 把快速排序用到字符数组上前面说 ASC 码表决定字符比较结果这里直接做一个字符排序实验。假设字符数组是{b, A, 1, a, Z, }。把上面的 partition 改成 char 类型即可逻辑不用变public static void quickSortChars(char[] arr, int left, int right) { if (left right) { return; } int index partitionChars(arr, left, right); quickSortChars(arr, left, index - 1); quickSortChars(arr, index 1, right); } public static int partitionChars(char[] arr, int left, int right) { char pivot arr[left]; int i left; int j right; while (i j) { while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; i; } while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; j--; } } arr[i] pivot; return i; }排序后如果只输出字符本身空格可能看不出来。建议同时输出码值for (char c : arr) { System.out.println( c - (int) c); }排序结果是 - 32 1 - 49 A - 65 Z - 90 a - 97 b - 98这个结果直观说明了几个问题空格排在最前面数字字符在字母前面大写字母在小写字母前面。如果只看字符输出 1AZab一开始会觉得顺序有点怪但结合码值就完全合理。3.4 字符串数组如何结合 ASCII 排序如果要对字符串数组排序不能直接写arr[j] pivot因为 C 里没有字符串内置比较运算符Java 中字符串对象也不是基础类型直接比较只会比较引用。Java 应该用compareTopublic static void quickSortStrings(String[] arr, int left, int right) { if (left right) { return; } int index partitionStrings(arr, left, right); quickSortStrings(arr, left, index - 1); quickSortStrings(arr, index 1, right); } public static int partitionStrings(String[] arr, int left, int right) { String pivot arr[left]; int i left; int j right; while (i j) { while (i j arr[j].compareTo(pivot) 0) { j--; } if (i j) { arr[i] arr[j]; i; } while (i j arr[i].compareTo(pivot) 0) { i; } if (i j) { arr[j] arr[i]; j--; } } arr[i] pivot; return i; }比如数组{peach, apple, Banana, banana, 123}按compareTo排序后结果会是123 Banana apple banana peach原因是1的码值是 49B的码值是 66a的码值是 97b的码值是 98p的码值是 112。这种“大写字母全部排在小写字母前面”的结果和很多人以为的词典顺序不同。如果业务里需要忽略大小写排序就别直接用快速排序的原始码值比较应该自己写比较器比如 Java 的compareToIgnoreCase。4. 实际场景里的基准值、重复元素和递归优化4.1 避免最坏情况三数取中默认取第一个元素作为 pivot实现简单但遇到有序数组或逆序数组时性能会退化到 O(n^2)。工程上常见的做法是三数取中取当前区间的第一个、中间、最后一个元素把三者的中位数作为 pivot。Java 示例private static int medianOfThree(int[] arr, int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[mid]) { swap(arr, left, mid); } if (arr[left] arr[right]) { swap(arr, left, right); } if (arr[mid] arr[right]) { swap(arr, mid, right); } return mid; }使用前把arr[mid]和arr[left]交换再继续原来的 partition 逻辑。三数取中能明显降低最坏情况出现的概率特别是应对“数组已经基本有序”的场景。如果面临的数据完全不可控还可以使用随机选择 pivot 的方式。随机化的意义不是一定能让算法更快而是让最坏情况不总是固定出现在某些输入上。4.2 小区间切换插入排序快速排序在小数组上的表现不一定最好因为递归和分区存在额外开销。当子区间长度很小时切换到插入排序可以节省时间。一种常见做法是在递归入口加一个阈值private static final int INSERTION_SORT_THRESHOLD 16; public static void quickSortOptimized(int[] arr, int left, int right) { if (left right) { return; } if (right - left INSERTION_SORT_THRESHOLD) { insertionSort(arr, left, right); return; } int index partition(arr, left, right); quickSortOptimized(arr, left, index - 1); quickSortOptimized(arr, index 1, right); }插入排序代码不复杂这里就不展开了。阈值取多少不是固定值通常在 7 到 20 之间都常见。实际效果和你运行的数据规模有关不必纠结必须用某个值。4.3 大量重复元素三路快速排序普通快速排序遇到大量重复元素时会很吃亏。比如一个 10 万元素全是2的数组如果按挖坑法实现每次递归只能排除一个位置排序耗时非常接近最坏 O(n^2)。解决思路是使用三路快速排序。它把数组分成三块小于 pivot、等于 pivot、大于 pivot。等于 pivot 的区间不需要再递归因此大量重复值时效率很高。public static void quickSort3Way(int[] arr, int left, int right) { if (left right) { return; } int pivot arr[left]; int lt left; int gt right; int i left 1; while (i gt) { if (arr[i] pivot) { swap(arr, lt, i); lt; i; } else if (arr[i] pivot) { swap(arr, i, gt); gt--; } else { i; } } quickSort3Way(arr, left, lt - 1); quickSort3Way(arr, gt 1, right); }这里的关键是看i的移动方式遇到小于 pivot 的元素和lt交换lt和i同时前进。遇到大于 pivot 的元素和gt交换但i不前进因为交换过来的新元素还没比较过。遇到等于 pivot 的元素直接让i前进。结束之后区间[left, lt - 1]都小于 pivot[lt, gt]都等于 pivot[gt 1, right]都大于 pivot。4.4 递归转非递归快速排序的递归深度在平均情况下不高但极端情况下可能栈溢出。如果你不想依赖递归可以用显式栈保存待排序区间1. 初始把 [0, n-1] 压入栈。 2. 循环中弹出 left 和 right。 3. 如果 left right跳过。 4. 执行 partition得到 index。 5. 把左区间 [left, index - 1] 压栈。 6. 把右区间 [index 1, right] 压栈。 7. 直到栈为空。这样解决的问题是递归调用栈太深但并不能解决时间复杂度退化。如果数据极端无序仍然要配合随机基准或三数取中。4.5 手写快速排序和语言内置 sort 怎么选在实际项目中语言自带排序函数通常更可靠。Java 的Arrays.sort、C 语言的qsort、C 的std::sort都做了大量优化。对比点手写快速排序语言内置 sort学习价值高适合理解分治和递归低直接用即可稳定性手写版本通常不稳定Java 对象数组默认稳定基础类型数组不一定稳定重复元素处理需要自行优化一般内置处理适合场景笔试、教学、特殊排序规则生产环境默认推荐如果你工作中只需要普通排序调内置函数就够了。手写快速排序更多用于理解算法、应对面试或者当内置函数的比较规则无法满足需求时在自己实现的排序逻辑里加入自定义比较。5. 字符排序和快排报错时的排查顺序5.1 排序结果不对先从这几个地方查如果运行结果不是从小到大我的排查顺序通常是第一看比较条件是否写反。应该从右向左跳过大于等于 pivot 的元素找到小于 pivot 的元素从左向右跳过小于等于 pivot 的元素找到大于 pivot 的元素。如果方向反了结果会变成降序。第二看递归区间是否写对。partition 返回后基准值已经在正确位置左右递归不能包含它。常见错误是把右区间写成[index, right]这样基准值会再次参与排序虽然很多时候不会报错但逻辑已经不对。第三看 partition 结束后是否把