通用QuickSort处理大量字符串时性能极差且触发段错误求助

问题概述 #

• 为大学作业实现了支持任意类型数组排序的C语言通用QuickSort
• 使用2000万行的records.csv（格式：<id[int]>,<field1[string]>,<field2[int]>,<field3[float]>）做压力测试：
  • 按field2（int）、field3（float）排序正常，耗时12-13秒
  • 按field1（字符串）排序时耗时极久且触发段错误，但1k行的小数据集无此问题
• 同文件中的merge_sort可正常处理该大数据集，耗时25秒
• 相关代码包含sortlib.c和mass_tester.c

可能的原因分析 #

1. 快速排序最坏时间复杂度触发 + 递归栈溢出 #

字符串字段如果存在大量重复、完全有序或逆序的情况，普通快速排序（如选首尾元素作为基准）会退化为**O(n²)**时间复杂度，导致耗时暴增。同时，极端情况下递归深度会达到2000万级，远超程序栈的默认大小（通常仅几MB），直接触发栈溢出，引发段错误。

小数据集递归深度小（1k行仅约10层），不会触发栈溢出；归并排序时间复杂度稳定为O(nlogn)，递归深度仅为log2(20000000)≈25，远低于栈的承载极限，因此可以正常运行。

2. 字符串比较函数的效率问题 #

如果自定义的字符串比较函数实现低效（如未提前终止匹配、重复计算长度），在大数据量下会大幅放大排序耗时，但通常不会直接导致段错误，更多是和递归栈溢出共同作用加剧问题。

3. 字符串元素交换/内存操作错误 #

如果快速排序中处理字符串元素的交换逻辑存在缺陷（如未正确复制字符串、访问野指针），在大数据量下可能触发内存越界，进而引发段错误。小数据集下内存访问冲突概率低，因此未暴露问题。

排查与修复建议 #

• 优化基准选择策略：改用三数取中或随机基准选择，避免最坏时间复杂度触发
• 限制递归深度/改用迭代实现：当递归深度超过阈值（如100）时切换为插入排序；或直接将快速排序改为迭代实现，彻底避免递归栈溢出
• 使用高效字符串比较：直接调用标准库的strcmp函数，避免自定义低效实现
• 检查内存操作逻辑：验证快速排序中字符串元素的交换、移动逻辑，确保无野指针、内存越界问题
• 调试定位段错误：使用gdb等工具，通过bt命令查看调用栈，确认段错误是递归栈溢出还是内存访问错误导致

内容的提问来源于stack exchange，提问作者Samuele Tonda Roc