最近在整理字符编码和排序算法的资料时我发现两个看似独立的主题经常被放到一起讨论一个是“ASC码表”另一个是“快速排序”。前者是字符编码的基础后者是排序算法的高频考点。真正遇到字符串按字母序排序、内存中的字符数组排序时你会发现这两个知识点其实是紧密相关的——快速排序在比较元素时最底层的依据通常就是字符对应的码值。这篇文章我会先从 ASC 码表讲清楚字符为什么有“大小”、常见码值区间如何记忆再完整拆解快速排序的分区过程和递归逻辑给出 C、Java、Python 三种可运行实现最后用一个“字符串按 ASC 码值排序”的综合示例把两部分串起来并整理成一张高频问题排查清单。1. 先理解 ASC 码表1.1 ASC 码表是什么“ASC码表”可以说是“ASCII码表”的常用简写。ASCII 全称是 American Standard Code for Information Interchange中文常翻译为“美国信息交换标准代码”。它用 7 位二进制数表示一个字符所以一共可以表示 128 个字符编码范围从 0 到 127。为了让二进制阅读更方便我们通常把它写成十六进制也就是 0x00 到 0x7F。很多人第一次接触字符时会误以为计算机内部存储的是字母“A”或数字“1”的图形。实际上计算机只能存储二进制整数。为了把字符变成可以存储和传输的数据ASCII 标准给每个常用字符规定了一个整数编号。比如字符A对应的编号是 65字符0对应的编号是 48。程序拿到编号 65 后再去对照 ASCII 码表就知道它应该显示为大写字母A。因此ASC 码表本质上就是“字符”和“整数编号”之间的一份映射表这也是后续理解字符比较、字符排序的前提。在 ASCII 的 128 个编码值中又可以分为几个区间0 到 31 属于控制字符它们大多不能直接打印比如换行符的码值是 10回车符是 13制表符是 9。32 到 126 是可打印字符也就是空格、标点符号、数字、大写字母、小写字母等用户能直接看到的字符。127 对应的是删除键 DEL。虽然在现代计算机中中文、日文等字符早已超出 ASCII 范围但 ASCII 码表依然是所有字符编码体系的共同基础。1.2 必须记牢的三个典型编码区间ASC 码表并不需要把所有 128 个字符全背下来但有几个关键区间必须像乘法口诀一样熟练。为了直观这里整理成表格含义十进制十六进制说明空字符00x00C 语言字符串结尾的\0换行100x0A\n空格320x20第一个可打印字符数字0480x300到9连续49 对应1大写A650x41A到Z连续66 对应B小写a970x61a到z连续98 对应bDEL1270x7F删除控制字符这三组连续区间的意义很大。比如数字字符 48 到 57大写字母 65 到 90小写字母 97 到 122都各自连续。这意味着判断一个字符是不是大写字母可以直接使用ch A ch Z而不是去记 65 和 90 的魔法数字。同时小写字母与大写字母之间相差 32例如a是 97A是 65a - A得到 32。大写转小写时可以写成ch 32小写转大写时写成ch - 32。但更推荐直接使用32或-32的逻辑在 C 语言标准库和 Java 中也都有tolower、toLowerCase等方法不必真的手写数字。有一点要注意ASCII 表中大写字母区间和小写字母区间并不是紧挨着的。大写字母Z是 90小写字母a是 97中间还有 91 到 96 这 6 个符号分别是[、\、]、^、_、。所以对混合字符串做排序时不能简单认为“大写字母一定全部排在小写字母前面”还要看中间这些符号是否出现。1.3 在 C、Java、Python 中查看字符的码值理解了概念后最简单的方式是在代码中直接打印字符对应的码值。以 C 语言为例字符类型char本质上是 1 字节的整数可以直接用printf以%d格式输出。#include stdio.h int main() { char ch A; printf(ch %c, ASCII %d\n, ch, ch); return 0; }输出结果ch A, ASCII 65在 Java 中char是一个 16 位无符号整数当字符属于 ASCII 可打印字符时它的数值和 ASCII 码表一致。把char直接赋值给int即可看到码值。public class AsciiDemo { public static void main(String[] args) { char ch a; int code ch; System.out.println(ch ch , code code); } }输出结果ch a, code 97在 Python 中可以使用内置函数ord()获取字符的 Unicode 码点。对于 ASCII 范围内的字符码点值与 ASCII 码表完全一致。反向操作使用chr()。ch 0 code ord(ch) print(fch {ch}, code {code}) print(fcode {code}, ch {chr(code)})输出结果ch 0, code 48 code 48, ch 0这里补充说明一下Java 和 Python 中的char、ord()得到的是 Unicode 码点但由于 ASCII 是 Unicode 的基础子集所以英文数字范围内的字符不会产生出入。只有面对中文、特殊符号时得到的值才会超过 127那一部分已经不在 ASC 码表范围内了。2. 字符比较与排序为什么 ASC 码值决定结果2.1 排序的比较规则最终落到编码值很多初学者对“字符串排序”感到困惑尤其是混合了大写、小写、数字、标点的字符串。其实在计算机底层比较两个字符是否相等、谁大谁小都是直接比较两个字符的编码值。比如B的码值是 66a的码值是 97因此B a成立。C 语言的strcmp函数、Java 的String.compareTo方法本质上都会逐字符比较码值。这一点对理解快速排序非常重要。快速排序在分区时需要反复做“比较”操作当前元素是否小于基准值当前元素是否大于基准值如果排序的是整数数组比较对象就是整数本身如果排序的是字符数组比较对象背后其实就是 ASC 码值。换句话说ASC 码表决定了“字典序”背后的数值顺序快速排序则负责按照这个顺序把元素排好。2.2 大小写与标点之间的几个常见误区常见的误区有两个。第一个误区认为所有大写字母都排在所有小写字母前面。从整体看大写字母 A-Z65-90确实都在小写字母 a-z97-122前面但这不表示任意一个大写字母都一定紧挨在任意小写字母前面。大写字母区间结束之后还有 91 到 96 的标点符号然后才是小写字母区间。第二个误区认为0的数值是 0。事实上字符0的 ASC 码值是 48而不是数字 0。0、1……这种“数字字符”的码值是从 48 开始的连续区间。所以比较9和A时9是 57A是 65仍然9 A尽管从普通数字看9显然大于0但这里比较的是字符编码。举个例子对字符数组[a, B, 0, _]按 ASC 码值从小到大排序0是 48B是 66_是 95a是 97所以结果应该是[0, B, _, a]。如果把排序规则改成人眼理解的“字母序”“忽略大小写”结果又会完全不同。因此在做任何排序之前先要明确你的排序比较规则是纯 ASC 码值序、字典序还是自定义规则。3. 快速排序用一个例子把分区讲明白3.1 分治思想快速排序是由英国计算机科学家 C. A. R. Hoare 提出的经典排序算法核心思想是“分治”。每一轮过程中先从待排序区间中选一个基准值然后通过一次扫描把数组分成两部分左边部分的值都不大于基准值右边部分的值都不小于基准值。基准值最终会被放到正确的位置上。之后继续对基准值左、右两侧的子区间递归执行同样的操作。当子区间长度为 0 或 1 时不再递归。分治思想最大的好处是“大事化小”。每一趟分区只需要聚焦于当前区间不需要关心整个数组的其他区域。只要每个基准值都放到了最终位置所有元素也就自然有序了。3.2 第一次分区的完整过程这里用经典的“左右指针交换法”来演示。取数组arr [5, 1, 6, 2, 4, 3]选择最左侧元素作为基准值pivot arr[0] 5 left 0 right 5在分区过程中右侧指针j从右向左寻找第一个小于基准值的元素左侧指针i从左向右寻找第一个大于基准值的元素。找到后如果i仍然小于j就交换这两个元素。然后继续循环直到i和j相遇。第一轮寻找过程如下j从 5 开始向左找到arr[5] 3满足小于 5停止。i从 0 开始向右找到arr[2] 6满足大于 5停止。交换arr[2]和arr[5]数组变成[5, 1, 3, 2, 4, 6]第一轮结束后继续第二轮。j继续从 5 开始向左找。此时arr[5] 6不小于 5所以j继续左移直到j 4此时arr[4] 4小于 5停止。i从 2 开始向右找大于 5 的元素但移动过程中arr[2] 3、arr[3] 2都不大于 5i一直移动到 4与j相遇。循环结束。最后把基准值arr[left]与arr[i]交换交换前[5, 1, 3, 2, 4, 6] 交换后[4, 1, 3, 2, 5, 6]此时第一次分区完成基准值 5 被放到了索引 4 的位置。可以看到5 左边所有元素[4, 1, 3, 2]都小于 55 右边只有元素 6且 6 大于 5。3.3 递归排序子数组第一次分区结束后原数组被分成了三个部分左侧子数组[4, 1, 3, 2] 基准值 5 右侧子数组[6]接下来递归处理左侧子数组和右侧子数组。左侧子数组长度大于 1继续选择 4 作为基准值执行同样的分区逻辑。右侧子数组只有一个元素 6长度为 1已经满足left right直接返回即可。这个递归过程会一直持续到所有子数组长度都为 0 或 1。理论上快速排序的递归深度取决于基准值选择的“运气”。如果每次都能把数组近乎平分递归深度就是 O(logn)如果每次只消除一个元素递归深度就可能退化到 O(n)。4. 快速排序代码实现C、Java、Python4.1 C 语言实现C 语言版本需要注意指针的使用交换函数需要传入指针才能修改数组元素。下面是完整代码#include stdio.h void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } 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--; } // 从左向右找大于基准值的元素 while (i j arr[i] pivot) { i; } // 找到后交换 if (i j) { swap(arr[i], arr[j]); } } // 基准值归位 swap(arr[left], arr[i]); return i; } void quickSort(int arr[], int left, int right) { if (left right) { return; } int pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } int main() { int arr[] {5, 1, 6, 2, 4, 3}; int len sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, len - 1); for (int i 0; i len; i) { printf(%d , arr[i]); } printf(\n); return 0; }程序中partition是最核心的部分。外层while (i j)负责左右指针相向移动直到相遇。内层两个while条件分别处理“右指针找小”和“左指针找大”。这里使用和目的是跳过和基准值相等的元素避免指针卡死。当左右指针相遇时再把基准值换到相遇位置这样一次分区就完成了。运行程序后输出1 2 3 4 5 64.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 pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 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--; } while (i j arr[i] pivot) { i; } if (i j) { swap(arr, i, j); } } swap(arr, left, i); return i; } public static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } public static void main(String[] args) { int[] arr {5, 1, 6, 2, 4, 3}; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } }Java 示例中使用了Arrays.toString方便输出数组。如果你的环境不支持也可以手动循环打印。Java 的char类型同样是数值类型因此这个实现稍作修改即可排序字符数组。运行结果[1, 2, 3, 4, 5, 6]4.3 Python 实现Python 版本建议采用与原地方案接近的写法。虽然代码看起来比列表推导式复杂但它没有创建大量额外列表更贴近工程算法对空间的要求。def quick_sort(arr, left, right): if left right: return p partition(arr, left, right) quick_sort(arr, left, p - 1) quick_sort(arr, p 1, right) def partition(arr, left, right): pivot arr[left] i left j right while i j: while i j and arr[j] pivot: j - 1 while i j and arr[i] pivot: i 1 if i j: arr[i], arr[j] arr[j], arr[i] arr[left], arr[i] arr[i], arr[left] return i arr [5, 1, 6, 2, 4, 3] quick_sort(arr, 0, len(arr) - 1) print(arr)运行结果[1, 2, 3, 4, 5, 6]另外网上常见的简洁版快速排序通过列表推导式实现代码如下def quick_sort_simple(arr): if len(arr) 1: return arr pivot arr[0] left [x for x in arr[1:] if x pivot] right [x for x in arr[1:] if x pivot] return quick_sort_simple(left) [pivot] quick_sort_simple(right)简洁版可读性很高非常适合入门理解。但它的缺点是每一层递归都会创建多个新列表空间占用明显高于原地方案如果数据规模较大还可能出现较多的内存复制开销。所以简洁版适用于演示算法思想工程或面试手写时更推荐使用原地递归版本。5. 快速排序的复杂度、稳定性与优化方向5.1 时间复杂度快速排序的时间复杂度取决于基准值的选择。平均情况下每一趟分区大概能把数组分成两个规模相近的子区间递归树高度约为 log2n每一层所有子区间比较次数的总和约为 n所以总时间复杂度是 O(nlogn)。这也是快速排序名字中“快速”二字的由来。最坏情况下如果每次选择的基准值都是当前数组中的最小值或最大值例如对一个已经有序的数组仍取最左侧元素为基准那么每趟分区只能确定一个元素的位置剩下的子区间长度始终是 n-1、n-2、n-3……此时总比较次数接近 n²时间复杂度退化为 O(n²)。因此如果你在线上排序一个本身接近有序的数组固定取首元素作为基准的朴素快排有可能表现很差。5.2 空间复杂度与稳定性快速排序的空间复杂度不是 O(1)因为递归过程需要消耗函数调用栈空间。平均情况下递归深度为 O(logn)最坏情况下递归深度为 O(n)。如果数据量极大且递归深度过深在 C 语言中可能造成栈溢出在 Python 中则会触发RecursionError。稳定性方面快速排序是不稳定排序。所谓稳定性是指如果原数组中有两个相等元素排序后它们的相对顺序是否保持不变。在快速排序的分区过程中相等元素可能因为指针扫描和交换而被移动无法保证相对顺序。这一特性意味着如果业务要求“先按成绩排序成绩相同的人再按姓名排序”那么最好不要在主排序中使用不稳定的快速排序。Java 对对象数组进行排序时底层使用的 TimSort 是稳定排序对基本类型数组使用 DualPivotQuicksort是不稳定排序但因为是基本类型相等元素没有身份差异所以不会造成业务问题。5.3 常用优化方向为了避免最坏情况常见的优化有以下几种。第一随机基准值。在每次分区前随机选取当前区间中的一个元素作为基准值并与arr[left]交换。这样即使输入是近乎有序的数组也不容易每次选中极端值。第二三数取中法。取arr[left]、arr[right]、arr[(leftright)/2]三个位置的中位数作为基准值。这种方式能在一定程度上规避有序输入带来的最坏情况。第三小区间使用插入排序。递归到区间长度小于某个阈值时直接使用插入排序。插入排序在小规模数据上常数小而且可以避免过多的递归调用。第四三路快速排序。当数组中存在大量重复元素时基本快排很容易因为相等元素过多而导致分区不平衡。三路快排将区间分成小于、等于、大于基准值三部分只递归处理小于和大于的两部分可以显著提升重复元素场景的性能。6. 综合示例字符串按 ASC 码值快速排序6.1 需求分析刚才我们把 ASC 码表和快速排序分开介绍现在用一个综合场景把它们连起来。假设有一个字符串dbAC我们要求对这个字符串中的字符按 ASC 码值从小到大排序并输出排序后的字符串。先手动推演d的码值是 100b是 98A是 65C是 67。按码值升序排列应该是A (65)、C (67)、b (98)、d (100)也就是输出ACbd。这个示例比普通整数排序更有意思因为它要求我们从整型快排自然过渡到字符型快排。唯一要注意的是C 语言字符串末尾有一个\0它的码值是 0如果把它误当作字符参与排序排序结果就会变成空字符在前printf(%s)输出时会被截断看到的内容会异常。6.2 C 语言综合代码下面代码是对上一节快速排序的“字符版”改造。比较条件仍然使用字符比较而字符比较的实际依据就是 ASC 码值。#include stdio.h void swapChar(char *a, char *b) { char temp *a; *a *b; *b temp; } int partitionChar(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--; } while (i j arr[i] pivot) { i; } if (i j) { swapChar(arr[i], arr[j]); } } swapChar(arr[left], arr[i]); return i; } void quickSortChar(char arr[], int left, int right) { if (left right) { return; } int pivotIndex partitionChar(arr, left, right); quickSortChar(arr, left, pivotIndex - 1); quickSortChar(arr, pivotIndex 1, right); } int main() { char str[] dbAC; int len sizeof(str) / sizeof(str[0]) - 1; // 去掉末尾的 \0 printf(排序前: %s\n, str); quickSortChar(str, 0, len - 1); printf(排序后: %s\n, str); return 0; }运行结果排序前: dbAC 排序后: ACbd为什么大写A、C会排在前面因为它们对应的码值是 65 和 67。而小写b、d的码值是 98 和 100要远远大于大写字母所以排在了后面。如果你按人眼常见的“先A、再C、再d、再b”这种键序去理解反而解释不了这个结果。这正好说明了 ASC 码表对排序结果的影响。6.3 运行结果解释与实际扩展在这个例子中排序算法本身只负责“按比较函数确定的顺序”重新排列元素而比较函数如果是原始字符比较比较的依据就是 ASC 码值。这个逻辑可以扩展到任意字符串两个字符串比较时从左到右依次比较对应位置字符的码值一旦发现某个字符不同就可以确定两个字符串的大小。如果你想将这段代码推广到中文字符串按拼音排序那就要额外考虑汉字编码、拼音规则等复杂逻辑。ASC 码表只适合 ASCII 可见字符、英文文本的排序场景。理解了这一点以后再面对字符排序问题时就知道应该从编码层和排序规则层两个角度去分析。7. 常见问题排查清单问题现象常见原因解决思路数组排序后结果不对partition中的边界条件写错左右指针越界后仍继续扫描用长度为 2 的数组手动跟踪i、j的变化确认每个内层while都必须带i j递归卡住或报栈溢出递归出口遗漏left right或基准位置不正确检查quickSort是否对左右子区间递归并确保每次pivotIndex必在区间内大量重复元素时性能退化固定取首元素作基准重复元素让分区极度不平衡使用三路快速排序或采用随机基准值优化字符数组字符串输出异常把字符串结束符\0