Hello大家好。最近整理计算机基础笔记时有一个很有意思的发现很多初学者会在笔试或面试题里同时遇到“ASC码表”和“快速排序”这两个知识点。表面看一个是字符编码一个是排序算法好像没什么交集但实际做工程时字符排序、字符串字典序、甚至不少数据比对问题底层都离不开“字符在码表中的位置”而快速排序又是理解这些排序过程最经典的算法之一。这篇文章会围绕“ASC码表”与“快速排序”展开先讲清楚字符码值到底是什么再用 C 语言和 Java 分别写一套可以直接运行的快速排序实现最后用一个“按 ASCII 码值给字符排序”的完整案例把这两个知识点串起来。如果你正准备学算法、复习数据结构或者曾经被快速排序的边界条件绕晕过这篇文章应该能帮上忙。1. 从“ASC码表”与快速排序说起1.1 ASC码表是什么先说明一个小的命名差异网上搜“ASC码表”时搜出来的大多是“ASCII 码表”。ASC 是 ASCII 在部分中文教材和资料里的缩写叫法全称是 American Standard Code for Information Interchange即美国信息交换标准代码。ASCII 是一种基于拉丁字母的字符编码标准它用二进制数来表示字符。为什么需要编码因为计算机内部只认 0 和 1字符要能存储、传输和显示就必须先被转换成一串二进制数。比如字符A在 ASCII 码表中对应十进制 65即二进制01000001字符a对应十进制 97。当程序执行char c A;时变量c在内存里保存的本质上就是数字 65。标准 ASCII 使用 7 位二进制数表示字符范围从 0 到 127一共 128 个字符。之后的扩展 ASCII 使用 8 位范围扩展到 0 到 255。需要特别注意的是0 到 127 这一部分在不同系统之间基本是统一的而 128 到 255 这一部分在不同编码方案里可能表示不同字符。1.2 为什么算法入门绕不开快速排序快速排序是计算机科学家 Tony Hoare 在 1960 年左右提出的排序算法。它采用分治思想把一个大数组拆成两个小数组分别解决后再合并结果甚至不需要额外合并因为元素在分区过程中已经移动到了正确位置。快速排序在平均情况下时间复杂度为 O(n log n)而且它是原地排序不需要像归并排序那样申请大量额外空间。正因如此很多编程语言的内置排序函数在设计时都考虑过快速排序或其改进版本。理解快速排序不只是为了应付面试更有助于理解底层排序机制以及为什么某些输入会让快排变慢。1.3 这篇文章适合谁读如果你属于下面几类读者阅读本文会比较顺畅刚开始学数据结构的同学想把快速排序完整啃下来。准备笔试面试、需要手写排序算法的开发者。需要处理字符排序、但搞不清为什么字符排序结果和预期不一样的开发者。想理解字符编码与程序排序关系的零基础学习者。阅读本文后你至少能掌握三件事ASCII 码表的整体结构以及如何在代码中查看任意字符的码值。快速排序的原理、C 与 Java 实现、核心边界条件。如何按 ASCII 码对字符数组进行快速排序并理解字符排序的本质。2. ASCII 编码基础与码表速查2.1 ASCII 编码的基本设计ASCII 码表通常用“十进制 十六进制 字符”的形式展示。比如数字字符0的 ASCII 码是 48十六进制 0x30大写字母A是 65十六进制 0x41小写字母a是 97十六进制 0x61。这些数字不是乱定的它们之间有非常清晰的规律数字0到9的 ASCII 码是连续的范围 48 到 57。大写字母A到Z的 ASCII 码是连续的范围 65 到 90。小写字母a到z的 ASCII 码是连续的范围 97 到 122。同一个字母的大小写 ASCII 码相差 32例如A是 65a是 97差值正好 32。所以在做字符处理时经常能看到char - 0这样的写法。例如8 - 0等价于56 - 48结果是整数 8。大小写转换也可以利用char 32或char - 32实现不过真实工程中更推荐使用标准库函数因为可读性更好也更安全。2.2 ASCII 码表整体结构整个 ASCII 码表可以按字符类型划分成几个区间先看最核心的部分。区间十进制字符类型说明0 - 31控制字符不可打印主要用于控制终端例如换行、回车等32空格可打印字符的最小值33 - 47标点与符号如!、、#、$、%、、等48 - 57数字0到9数字字符是连续的区间58 - 64标点与符号如:、;、、、、?、65 - 90大写字母A到Z大写字母连续区间91 - 96标点与符号如[、\、]、^、_、97 - 122小写字母a到z小写字母连续区间123 - 126标点与符号如{、|、}、~127DEL 删除字符控制字符程序员日常用得最多的几个 ASCII 码值可以单独保存一份速查表字符十进制十六进制二进制换行\n100x0A0000 1010回车\r130x0D0000 1101空格320x200010 00000480x300011 0000A650x410100 0001a970x610110 0001建议收藏这份表后面做算法题时遇到字符比较、判断数字、大小写转换会非常方便。2.3 代码中如何查看字符的 ASCII 码值不要死记硬背实际开发时可以直接通过代码把字符转成整数。先看 C 语言的写法。C 语言中char本质上是小整型可以直接用%d输出#include stdio.h int main() { char ch A; printf(%c - %d (十六进制: 0x%X)\n, ch, ch, ch); return 0; }运行结果A - 65 (十六进制: 0x41)再看 Java 的写法。Java 中char是无符号 16 位整数把它转成int同样可以得到字符编码值public class AsciiDemo { public static void main(String[] args) { char ch a; System.out.println(ch - (int) ch); } }运行结果a - 97这里需要补充一点Java 中char本质上是 UTF-16 编码单元。对于 ASCII 范围内的字符其 UTF-16 码元值和 ASCII 码值是一致的所以上面的输出仍然可以直接理解为“字符的 ASCII 码”。但如果字符是中文或 emoji它对应的就不再属于 ASCII而是 Unicode 码点输出结果会明显不同。2.4 ASCII 和 Unicode、UTF-8 的关系很多初学者会把 ASCII、Unicode、UTF-8 混在一起。其实可以这样理解ASCII 是字符集同时也是一种编码方案它只规定了 128 个字符与数字的对应关系。Unicode 是更大的字符集试图给全世界所有字符一个统一编号。UTF-8 是 Unicode 的一种存储编码方式属于变长编码。但有一个关键点是Unicode 的前 128 个码点设计成了与 ASCII 完全一致。也就是说英文字母、数字、常用英文标点在 UTF-8 编码后的第一个字节与 ASCII 编码其实是兼容的。这也是为什么很多字符串函数在处理纯英文时可以直接按字节比较行为与 ASCII 码表一致。中文字符在 Unicode 中位于更靠后的码点区域所以它没有“ASCII 码”。如果硬要去查中文字的 ASCII 码得到的中文在不同编码方案里可能完全不同。这一条在后面的字符排序部分会再次用到。3. 快速排序核心原理拆解3.1 快速排序的宏观思路快速排序的整个流程可以概括成三步在待排序区间中挑选一个元素作为基准值。把区间内其他元素分成两部分比基准值小的放在左边比基准值大的放在右边。这个过程称为分区。对左右两个分区分别递归执行同样的操作。比如有下面这样一组数据[50, 30, 80, 40, 10, 70, 20, 60]假设每次都选最后一个元素作为基准那么第一次分区会选 60 作为基准。经过一轮比较和交换后数组可能变成这样比 60 小的部分[50, 30, 40, 10, 20] 基准 60 比 60 大的部分[80, 70]随后继续递归排序左右两边。这个过程看起来很像把一个复杂问题不断拆分成更小的问题也就是典型的分治思想。3.2 分区过程手动推导为了理解分区函数我们看一轮完整的分区过程。基准选最后一个元素 60用两个下标i表示“小于基准区”的末尾位置初始为-1。j从区间左端向右扫描到基准前一个位置。初始数组下标0 1 2 3 4 5 6 7 数组50 30 80 40 10 70 20 60 基准60逐步处理j050 60说明 50 应该放到小于区把i加 1 到 0并交换arr[0]与arr[0]相当于不动。j130 60小于区扩展位置不变。j280 60不处理。j340 60把arr[2]与arr[3]交换此时数组为[50, 30, 40, 80, 10, 70, 20, 60]。j410 60把arr[3]与arr[4]交换数组为[50, 30, 40, 10, 80, 70, 20, 60]。j570 60不处理。j620 60把arr[4]与arr[6]交换数组为[50, 30, 40, 10, 20, 70, 80, 60]。最后把基准 60 放到小于区和大于区中间也就是把arr[5]与arr[7]交换[50, 30, 40, 10, 20, 60, 80, 70]此时返回基准下标5。可以看到下标 5 左边的元素都小于等于 60右边的元素都大于等于 60但左右两侧内部仍然是乱序的。接下来只需要递归处理[0, 4]和[6, 7]这两个区间整个数组最终就会有序。3.3 递归终止条件与边界写法快速排序最常见的 bug 来自区间边界。递归的终止条件是区间里没有元素或者只有一个元素也就是low high。在基准选最后一个元素的写法中循环扫描范围是j从low到high - 1不能把基准自己也算进去。分区结束后交换arr[i 1]与arr[high]把基准放到真正属于它的位置然后返回i 1。如果基准选第一个元素扫描方向通常要反过来交换逻辑也会有差别。很多同学把两种模板记混写出来的分区就乱套了。建议刚开始只掌握一种最顺手的写法。4. 快速排序完整实现C 语言与 Java4.1 C 语言快速排序完整代码先看 C 语言版本。为了保证可读性我给每个函数都加上注释。// 文件路径quick_sort.c #include stdio.h
ASCII码与快速排序：从字符编码到排序算法实战解析
Hello大家好。最近整理计算机基础笔记时有一个很有意思的发现很多初学者会在笔试或面试题里同时遇到“ASC码表”和“快速排序”这两个知识点。表面看一个是字符编码一个是排序算法好像没什么交集但实际做工程时字符排序、字符串字典序、甚至不少数据比对问题底层都离不开“字符在码表中的位置”而快速排序又是理解这些排序过程最经典的算法之一。这篇文章会围绕“ASC码表”与“快速排序”展开先讲清楚字符码值到底是什么再用 C 语言和 Java 分别写一套可以直接运行的快速排序实现最后用一个“按 ASCII 码值给字符排序”的完整案例把这两个知识点串起来。如果你正准备学算法、复习数据结构或者曾经被快速排序的边界条件绕晕过这篇文章应该能帮上忙。1. 从“ASC码表”与快速排序说起1.1 ASC码表是什么先说明一个小的命名差异网上搜“ASC码表”时搜出来的大多是“ASCII 码表”。ASC 是 ASCII 在部分中文教材和资料里的缩写叫法全称是 American Standard Code for Information Interchange即美国信息交换标准代码。ASCII 是一种基于拉丁字母的字符编码标准它用二进制数来表示字符。为什么需要编码因为计算机内部只认 0 和 1字符要能存储、传输和显示就必须先被转换成一串二进制数。比如字符A在 ASCII 码表中对应十进制 65即二进制01000001字符a对应十进制 97。当程序执行char c A;时变量c在内存里保存的本质上就是数字 65。标准 ASCII 使用 7 位二进制数表示字符范围从 0 到 127一共 128 个字符。之后的扩展 ASCII 使用 8 位范围扩展到 0 到 255。需要特别注意的是0 到 127 这一部分在不同系统之间基本是统一的而 128 到 255 这一部分在不同编码方案里可能表示不同字符。1.2 为什么算法入门绕不开快速排序快速排序是计算机科学家 Tony Hoare 在 1960 年左右提出的排序算法。它采用分治思想把一个大数组拆成两个小数组分别解决后再合并结果甚至不需要额外合并因为元素在分区过程中已经移动到了正确位置。快速排序在平均情况下时间复杂度为 O(n log n)而且它是原地排序不需要像归并排序那样申请大量额外空间。正因如此很多编程语言的内置排序函数在设计时都考虑过快速排序或其改进版本。理解快速排序不只是为了应付面试更有助于理解底层排序机制以及为什么某些输入会让快排变慢。1.3 这篇文章适合谁读如果你属于下面几类读者阅读本文会比较顺畅刚开始学数据结构的同学想把快速排序完整啃下来。准备笔试面试、需要手写排序算法的开发者。需要处理字符排序、但搞不清为什么字符排序结果和预期不一样的开发者。想理解字符编码与程序排序关系的零基础学习者。阅读本文后你至少能掌握三件事ASCII 码表的整体结构以及如何在代码中查看任意字符的码值。快速排序的原理、C 与 Java 实现、核心边界条件。如何按 ASCII 码对字符数组进行快速排序并理解字符排序的本质。2. ASCII 编码基础与码表速查2.1 ASCII 编码的基本设计ASCII 码表通常用“十进制 十六进制 字符”的形式展示。比如数字字符0的 ASCII 码是 48十六进制 0x30大写字母A是 65十六进制 0x41小写字母a是 97十六进制 0x61。这些数字不是乱定的它们之间有非常清晰的规律数字0到9的 ASCII 码是连续的范围 48 到 57。大写字母A到Z的 ASCII 码是连续的范围 65 到 90。小写字母a到z的 ASCII 码是连续的范围 97 到 122。同一个字母的大小写 ASCII 码相差 32例如A是 65a是 97差值正好 32。所以在做字符处理时经常能看到char - 0这样的写法。例如8 - 0等价于56 - 48结果是整数 8。大小写转换也可以利用char 32或char - 32实现不过真实工程中更推荐使用标准库函数因为可读性更好也更安全。2.2 ASCII 码表整体结构整个 ASCII 码表可以按字符类型划分成几个区间先看最核心的部分。区间十进制字符类型说明0 - 31控制字符不可打印主要用于控制终端例如换行、回车等32空格可打印字符的最小值33 - 47标点与符号如!、、#、$、%、、等48 - 57数字0到9数字字符是连续的区间58 - 64标点与符号如:、;、、、、?、65 - 90大写字母A到Z大写字母连续区间91 - 96标点与符号如[、\、]、^、_、97 - 122小写字母a到z小写字母连续区间123 - 126标点与符号如{、|、}、~127DEL 删除字符控制字符程序员日常用得最多的几个 ASCII 码值可以单独保存一份速查表字符十进制十六进制二进制换行\n100x0A0000 1010回车\r130x0D0000 1101空格320x200010 00000480x300011 0000A650x410100 0001a970x610110 0001建议收藏这份表后面做算法题时遇到字符比较、判断数字、大小写转换会非常方便。2.3 代码中如何查看字符的 ASCII 码值不要死记硬背实际开发时可以直接通过代码把字符转成整数。先看 C 语言的写法。C 语言中char本质上是小整型可以直接用%d输出#include stdio.h int main() { char ch A; printf(%c - %d (十六进制: 0x%X)\n, ch, ch, ch); return 0; }运行结果A - 65 (十六进制: 0x41)再看 Java 的写法。Java 中char是无符号 16 位整数把它转成int同样可以得到字符编码值public class AsciiDemo { public static void main(String[] args) { char ch a; System.out.println(ch - (int) ch); } }运行结果a - 97这里需要补充一点Java 中char本质上是 UTF-16 编码单元。对于 ASCII 范围内的字符其 UTF-16 码元值和 ASCII 码值是一致的所以上面的输出仍然可以直接理解为“字符的 ASCII 码”。但如果字符是中文或 emoji它对应的就不再属于 ASCII而是 Unicode 码点输出结果会明显不同。2.4 ASCII 和 Unicode、UTF-8 的关系很多初学者会把 ASCII、Unicode、UTF-8 混在一起。其实可以这样理解ASCII 是字符集同时也是一种编码方案它只规定了 128 个字符与数字的对应关系。Unicode 是更大的字符集试图给全世界所有字符一个统一编号。UTF-8 是 Unicode 的一种存储编码方式属于变长编码。但有一个关键点是Unicode 的前 128 个码点设计成了与 ASCII 完全一致。也就是说英文字母、数字、常用英文标点在 UTF-8 编码后的第一个字节与 ASCII 编码其实是兼容的。这也是为什么很多字符串函数在处理纯英文时可以直接按字节比较行为与 ASCII 码表一致。中文字符在 Unicode 中位于更靠后的码点区域所以它没有“ASCII 码”。如果硬要去查中文字的 ASCII 码得到的中文在不同编码方案里可能完全不同。这一条在后面的字符排序部分会再次用到。3. 快速排序核心原理拆解3.1 快速排序的宏观思路快速排序的整个流程可以概括成三步在待排序区间中挑选一个元素作为基准值。把区间内其他元素分成两部分比基准值小的放在左边比基准值大的放在右边。这个过程称为分区。对左右两个分区分别递归执行同样的操作。比如有下面这样一组数据[50, 30, 80, 40, 10, 70, 20, 60]假设每次都选最后一个元素作为基准那么第一次分区会选 60 作为基准。经过一轮比较和交换后数组可能变成这样比 60 小的部分[50, 30, 40, 10, 20] 基准 60 比 60 大的部分[80, 70]随后继续递归排序左右两边。这个过程看起来很像把一个复杂问题不断拆分成更小的问题也就是典型的分治思想。3.2 分区过程手动推导为了理解分区函数我们看一轮完整的分区过程。基准选最后一个元素 60用两个下标i表示“小于基准区”的末尾位置初始为-1。j从区间左端向右扫描到基准前一个位置。初始数组下标0 1 2 3 4 5 6 7 数组50 30 80 40 10 70 20 60 基准60逐步处理j050 60说明 50 应该放到小于区把i加 1 到 0并交换arr[0]与arr[0]相当于不动。j130 60小于区扩展位置不变。j280 60不处理。j340 60把arr[2]与arr[3]交换此时数组为[50, 30, 40, 80, 10, 70, 20, 60]。j410 60把arr[3]与arr[4]交换数组为[50, 30, 40, 10, 80, 70, 20, 60]。j570 60不处理。j620 60把arr[4]与arr[6]交换数组为[50, 30, 40, 10, 20, 70, 80, 60]。最后把基准 60 放到小于区和大于区中间也就是把arr[5]与arr[7]交换[50, 30, 40, 10, 20, 60, 80, 70]此时返回基准下标5。可以看到下标 5 左边的元素都小于等于 60右边的元素都大于等于 60但左右两侧内部仍然是乱序的。接下来只需要递归处理[0, 4]和[6, 7]这两个区间整个数组最终就会有序。3.3 递归终止条件与边界写法快速排序最常见的 bug 来自区间边界。递归的终止条件是区间里没有元素或者只有一个元素也就是low high。在基准选最后一个元素的写法中循环扫描范围是j从low到high - 1不能把基准自己也算进去。分区结束后交换arr[i 1]与arr[high]把基准放到真正属于它的位置然后返回i 1。如果基准选第一个元素扫描方向通常要反过来交换逻辑也会有差别。很多同学把两种模板记混写出来的分区就乱套了。建议刚开始只掌握一种最顺手的写法。4. 快速排序完整实现C 语言与 Java4.1 C 语言快速排序完整代码先看 C 语言版本。为了保证可读性我给每个函数都加上注释。// 文件路径quick_sort.c #include stdio.h
