基于ElemType的快速排序实现问题排查（含栈溢出警告）

初始实现与空指针问题 #

我尝试用快速排序实现VectorSort函数，初始代码如下：

#include "vector.h"

void quicksort(Vector* v, ElemType* first, ElemType* last) {
    ElemType i, j, pivot; 
    if (*first < *last) {
        i = first; 
        j = last; 
        pivot = v->data[*last];
        do {
            while (v->data[i] < v->data[pivot]) i++; 
            while (v->data[j] > v->data[pivot]) j--; 
            if (i <= j) {
                ElemSwap(v->data[i], v->data[j]); 
                i++; j--; 
            }
        } while (i <= j); 
        quicksort(v, first, j); 
        quicksort(v, i, last); 
    }
}


void VectorSort(Vector* v) {
    if (v == NULL) {
        return; 
    }
    quicksort(v, 0, (size_t)((v->size))); 
}

int main(void) {
    Vector v = {.capacity = 4, .size = 2};
    Vector* ptr = &v; 
    ptr->data[0] = 4; ptr->data[1] = 1; 
    VectorSort(ptr); 
    return 0; 
}

调试时触发错误：
"ptr->data was nullptr in line: "ptr->data[0] = 4; ptr->data[1] = 1;" (green squiggle)"

依赖代码 #

elemtype.h

#ifndef ELEMTYPE_INT_H_
#define ELEMTYPE_INT_H_

#include <stdbool.h>
#include <stdio.h>

typedef int ElemType; 
void ElemSwap(ElemType *e1, ElemType *e2);

#endif // ELEMTYPE_INT_H_

elemtype.c

#define _CRT_SECURE_NO_WARNINGS
#include "elemtype.h"

#include <string.h>
#include <stdlib.h>

void ElemSwap(ElemType *e1, ElemType *e2) {
    ElemType tmp = *e1;
    *e1 = *e2;
    *e2 = tmp;
}

vector.h

#pragma once
#include "elemtype.h"
#include <stdio.h>
#include <stdlib.h>
typedef struct {
    size_t capacity;
    size_t size;
    ElemType* data;
} Vector;

void VectorSort(Vector* v);

更新后的代码与递归溢出问题 #

修正空指针后更新代码如下，但出现新问题：

#include "vector.h"
void quicksort(Vector* v, size_t first, size_t last) {
    size_t i = 0; size_t j = 0; size_t pivot = 0; 
    if (first < last) {
        i = first; j = last; 
        pivot = v->data[last]; 
    }
    do {
        while (v->data[i] <= pivot) i++; 
        while (v->data[j] >= pivot) j--; 
        if (i <= j) {
            ElemSwap(&v->data[i], &v->data[j]); 
            i++; j--; 
        } 
    } while (i <= j); 
    quicksort(v, first, j);
    quicksort(v, i, last);
}
void VectorSort(Vector* v) {
    if (v == NULL) {
        return; 
    }
    quicksort(v, 0, v->size - 1); 
}


int main(void) {
    Vector* v = calloc(1, sizeof(Vector)); 
    if (v == NULL) {
        return 1; 
    }
    v->size = v->capacity = 3;
    v->data = calloc(3, sizeof(v->data)); 
    if (v->data == NULL) {
        free(v);
        return 1; 
    }
    v->data[0] = 2; v->data[1] = 1; v->data[2] = 7; 
    clock_t start; 
    clock_t end; 
    double cpu_time_used; 
    start = clock(); 
    for (int i = 0; i < v->size; i++) {
        VectorSort(v); 
    }
    end = clock(); 
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("Sorted in t(s) %lf ", cpu_time_used / 11);

    free(v->data);
    free(v);
    return 0; 
}  

现在无编译错误，但收到警告：
"quicksort: recursive on all control paths, function will cause runtime stack overflow"
程序无法正常运行。

问题分析与修复方案 #

1. 空指针问题根因 #

初始代码中直接声明Vector v时，v.data未分配内存，属于野指针，写入时触发空指针错误。更新后用calloc分配内存解决了该问题，但v->data = calloc(3, sizeof(v->data));存在错误：sizeof(v->data)是指针的大小（通常8字节），应改为sizeof(ElemType)以分配元素大小的内存。

2. 递归溢出问题根因 #

更新后的quicksort函数中，递归调用未被if (first < last)包裹，无论区间是否有效都会触发递归，导致无限递归，最终栈溢出。

修复后的完整代码 #

#include "vector.h"
#include <time.h>

void quicksort(Vector* v, size_t first, size_t last) {
    // 递归终止条件：区间无效或只有单个元素
    if (first >= last) {
        return;
    }
    size_t i = first; 
    size_t j = last; 
    // pivot是元素值，不是索引，修正类型为ElemType
    ElemType pivot = v->data[last]; 

    do {
        // 从左找大于等于pivot的元素，添加边界检查防止越界
        while (i <= last && v->data[i] < pivot) {
            i++;
        }
        // 从右找小于等于pivot的元素，添加边界检查
        while (j >= first && v->data[j] > pivot) {
            j--;
        }
        if (i <= j) {
            ElemSwap(&v->data[i], &v->data[j]); 
            i++; 
            // 防止size_t类型下溢
            if (j > 0) {
                j--;
            } else {
                break;
            }
        }
    } while (i <= j); 

    quicksort(v, first, j);
    quicksort(v, i, last);
}

void VectorSort(Vector* v) {
    if (v == NULL || v->data == NULL || v->size <= 1) {
        return; 
    }
    quicksort(v, 0, v->size - 1); 
}

int main(void) {
    Vector* v = calloc(1, sizeof(Vector)); 
    if (v == NULL) {
        return 1; 
    }
    v->size = v->capacity = 3;
    // 修正内存分配，使用ElemType的大小
    v->data = calloc(v->size, sizeof(ElemType)); 
    if (v->data == NULL) {
        free(v);
        return 1; 
    }
    v->data[0] = 2; v->data[1] = 1; v->data[2] = 7; 
    
    clock_t start = clock(); 
    // 无需循环排序多次，一次即可
    VectorSort(v); 
    clock_t end = clock(); 
    double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("Sorted in t(s) %lf\n", cpu_time_used);
    // 输出排序结果验证
    for (size_t i = 0; i < v->size; i++) {
        printf("%d ", v->data[i]);
    }
    printf("\n");

    // 释放内存，避免泄漏
    free(v->data);
    free(v);
    return 0; 
}  

核心修复点 #

• 添加递归终止条件：当first >= last时直接返回，终止无效递归。
• 修正pivot类型：pivot存储元素值而非索引，避免逻辑混乱。
• 边界检查：移动下标时添加边界判断，防止数组越界和size_t类型下溢。
• 内存分配修正：用sizeof(ElemType)分配元素内存，避免内存浪费或不足。
• 冗余排序移除：main函数中无需循环调用VectorSort，一次排序即可完成。

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