C语言中64位整数数组快速排序函数的段错误问题

问题描述 #

使用C语言实现针对uint64_t数组的快速排序，小数据集合（长度≤11）测试正常，但数组长度≥11时触发段错误。更换pivot位置等常规调整后问题仍存在，怀疑是uint64_t类型转换导致的错误。

快排实现代码 #

#include <stdio.h>
#include <stdlib.h>         
#include <time.h>
#include <stdint.h>

static void swap_int(uint64_t *a, uint64_t *b)
{
    uint64_t tmp = *a;
    *a  = *b;
    *b = tmp;
}

uint64_t QuickSortPartition(uint64_t *array, uint64_t begin, uint64_t end) {

    uint64_t i = begin, j;

    for (j = begin; j <= end; j++)
    {
        if (array[j] < array[end])
            swap_int(array + j, array + i++);
    }
    swap_int(array + i, array + end);

    return i;
}

void QuickSortFunction(uint64_t *array, uint64_t begin, uint64_t end) {
    if (begin < end) {
        uint64_t pivot = QuickSortPartition(array, begin, end);
        QuickSortFunction(array, begin, pivot - 1);
        QuickSortFunction(array, pivot + 1, end);
    }
}

测试代码 #

uint64_t rnd64(uint64_t n)
{
    const uint64_t z = 0x9FB21C651E98DF25;

    n ^= ((n << 49) | (n >> 15)) ^ ((n << 24) | (n >> 40));
    n *= z;
    n ^= n >> 35;
    n *= z;
    n ^= n >> 28;

    return n;
}

int main(int argc, char const *argv[]) {
    int n = 64;
    uint64_t Size = strtoull(argv[1], NULL, 10);

    uint64_t *S = malloc(Size * sizeof(uint64_t));

    uint64_t state = 1;
    for (uint64_t i = 0; i < Size; i++)
    {
        const uint64_t n = rnd64(state++);
        S[i] = n;
    }

    QuickSortFunction(S, 0, Size - 1);

    printf("Sorted S:\n");
    Display_set(S, Size, n);
}

注：Size通过命令行参数传入，Display_set为按顺序打印数组元素的标准函数。

问题根源 #

核心错误是无符号整数的下溢行为：

• 所有表示数组索引的变量（begin、end、pivot、i、j）都使用了uint64_t无符号类型。
• 当递归过程中pivot的值为0时，pivot - 1会触发无符号整数下溢，结果变为UINT64_MAX（即0xFFFFFFFFFFFFFFFF）。
• 此时递归调用QuickSortFunction(array, begin, pivot - 1)时，end被设置为一个极大值，访问数组时会直接越界，触发段错误。
• 数组长度≤11时，递归路径中恰好未出现pivot=0的情况，因此问题未暴露；长度增大后，出现该情况的概率提升，段错误触发。

修复方案 #

将表示数组索引的变量改为有符号整数类型（推荐int64_t，兼容超大数组），避免无符号下溢问题：

修改后的快排代码 #

#include <stdio.h>
#include <stdlib.h>         
#include <time.h>
#include <stdint.h>

static void swap_int(uint64_t *a, uint64_t *b)
{
    uint64_t tmp = *a;
    *a  = *b;
    *b = tmp;
}

int64_t QuickSortPartition(uint64_t *array, int64_t begin, int64_t end) {

    int64_t i = begin, j;

    for (j = begin; j <= end; j++)
    {
        if (array[j] < array[end])
            swap_int(array + j, array + i++);
    }
    swap_int(array + i, array + end);

    return i;
}

void QuickSortFunction(uint64_t *array, int64_t begin, int64_t end) {
    if (begin < end) {
        int64_t pivot = QuickSortPartition(array, begin, end);
        QuickSortFunction(array, begin, pivot - 1);
        QuickSortFunction(array, pivot + 1, end);
    }
}

测试代码对应修改 #

仅需调整QuickSortFunction的调用参数，将Size-1转换为int64_t：

// 原调用
// QuickSortFunction(S, 0, Size - 1);
// 修改后
QuickSortFunction(S, 0, (int64_t)Size - 1);

额外说明 #

如果你的数组长度不会超过int的范围（通常是32位，最大约20亿），也可以用int替代int64_t，效果一致。核心是避免用无符号类型表示数组索引，防止递归时出现下溢导致的越界访问。

内容的提问来源于stack exchange，提问作者E. G.