使用不同位数GCC 4.9.2编译快速排序代码输出不一致求助

问题根源分析 #

你的代码在不同位数GCC下表现不一致，核心是未定义行为导致的随机结果，具体有几个关键错误：

• Partition函数返回值错误
  你在partition里返回的是基准元素的值arr[pv]，但main函数需要的是基准元素的索引来划分排序区间。比如输入中的基准值是5，pv会被赋值为5，后续调用quickSort(arr,0,5)时，内部代码会访问arr[6]（因为r = right + 1）——这是数组外的未初始化内存，32位下可能刚好是不影响的值，64位下则是0，最终输出出现异常。

• Partition函数缺少默认返回值
  当left >= right时，partition没有返回语句，会导致函数返回栈中的随机值。32位和64位栈布局不同，返回的随机值也不一样，加剧了行为差异。

• QuickSort重复实现分区逻辑
  你在quickSort里重新写了一遍分区代码，不仅冗余，还和partition的参数逻辑不一致（比如right到底是数组长度还是最后一个元素的索引），容易引发错误。

• 多余的getchar()输入处理
  scanf("%d")会自动跳过所有空白字符（空格、换行等），额外的getchar()是多余的，甚至可能在某些输入格式下导致后续scanf读取失败。

修复后的完整代码 #

下面是修复后的代码，关键修改点已标注：

#include "stdio.h"

int partition(int arr[], int left, int right);
void swap(int *a, int *b);
void quickSort(int arr[], int left, int right);

int main() {
    int sizeArr, arr[1005], pv;
    scanf("%d", &sizeArr);
    // 移除多余的getchar()，让scanf自动处理空白
    for (int i = 0; i < sizeArr; i++) {
        scanf("%d", &arr[i]);
    }
    // 修改：right传入最后一个元素的索引sizeArr-1，而非数组长度
    pv = partition(arr, 0, sizeArr - 1);
    // 修改：排序基准左区间是0到pv-1，右区间是pv+1到sizeArr-1
    quickSort(arr, 0, pv - 1);
    quickSort(arr, pv + 1, sizeArr - 1);
    
    printf("%d", arr[0]);
    for (int i = 1; i < sizeArr; i++) printf(" %d", arr[i]);
    printf("\n");
    return 0;
}

int partition(int arr[], int left, int right) {
    // 修改：区间无效时直接返回left，避免未定义行为
    if (left >= right) {
        return left;
    }
    int pv = left;
    int l = left;
    int r = right + 1;
    do {
        do l++; while (arr[l] < arr[pv]);
        do r--; while (arr[r] > arr[pv]);
        if (l < r) swap(&arr[l], &arr[r]);
    } while (l < r);
    swap(&arr[pv], &arr[r]);
    // 修改：返回基准元素的索引r，而非元素值
    return r;
}

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        // 修改：复用partition函数，避免重复代码
        int pv = partition(arr, left, right);
        quickSort(arr, left, pv - 1);
        quickSort(arr, pv + 1, right);
    }
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

关键修改说明 #

1. 修正Partition返回值：现在返回基准元素的索引r，确保quickSort能正确划分排序区间。
2. 补充默认返回值：区间无效时返回left，彻底避免未定义行为。
3. 统一参数含义：所有区间函数的right参数都表示最后一个元素的索引，避免越界访问。
4. 复用Partition函数：quickSort不再重复写分区逻辑，减少出错概率，代码更简洁。
5. 移除多余的getchar()：让scanf自动处理空白字符，避免输入异常。

修改后，无论是32位还是64位GCC编译运行，输入数组长度6和元素5 4 5 3 7 2，都会得到正确的排序结果。

内容的提问来源于stack exchange，提问作者iBRabbit