企业官网建设流程全解析

如果把“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 全部背下来，真正高频的是下面这些锚点。只要记住这些，其他数字就能推导出来。

比较常见的手写大小写转换，也和这张表有关。因为大写字母'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' = 65，'b' = 98，所以程序会认为"Apple" < "banana"。但在日常按字母表排序时，我们通常会把大小写视为同一级。计算机只认码值，所以结果就是大写排前、小写排后。

1.4 码表在实践里最常见的用途

不要以为 ASCII 码表只是笔试里的背诵题。实际编码中，很多基础逻辑都会用到这些码值。

第一个是大小写转换。当你需要自己实现转换而不是调用现成 API 时，一般写法是：

if (c >= 'A' && c <= 'Z') { c = (char) (c + 32); }

第二个是数字字符转整型。比如把'5'转成数字 5：

int 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 应该用compareTo：

public 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'的码值是 49，'B'的码值是 66，'a'的码值是 97，'b'的码值是 98，'p'的码值是 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都做了大量优化。

如果你工作中只需要普通排序，调内置函数就够了。手写快速排序更多用于理解算法、应对面试，或者当内置函数的比较规则无法满足需求时，在自己实现的排序逻辑里加入自定义比较。

5. 字符排序和快排报错时的排查顺序

5.1 排序结果不对，先从这几个地方查

如果运行结果不是从小到大，我的排查顺序通常是：

第一，看比较条件是否写反。应该从右向左跳过大于等于 pivot 的元素，找到小于 pivot 的元素；从左向右跳过小于等于 pivot 的元素，找到大于 pivot 的元素。如果方向反了，结果会变成降序。

第二，看递归区间是否写对。partition 返回后，基准值已经在正确位置，左右递归不能包含它。常见错误是把右区间写成[index, right]，这样基准值会再次参与排序，虽然很多时候不会报错，但逻辑已经不对。

第三，看 partition 结束后，是否把