C++多类型快速排序遇段错误，无法打印迭代次数求助

问题背景 #

实现支持double/int/char/float类型的快速排序算法，测试double类型时出现进程退出码-1073740791（段错误），同时无法正常打印排序迭代次数。相关原代码如下：

原代码片段 #

// 生成随机double的代码
vector<double> generateDouble(int size, double min, double max)
{
    srand(time(0));
    vector<double> array(size);

    for (int index = 0; index < size; ++index)
    {
        double r = (((double)rand() / (double)RAND_MAX) * (max - min)) + min;
        array[index] = r;
    }

    return array;
}

// getIter()函数
int Sorting::getIter() const
{
    return iter;
}

// Sorting类的快速排序相关函数
void Sorting::quickSort()
{
    int first = 0;
    int last = listData.size() - 1;
    quickSort(listData, first, last);
}

void Sorting::quickSort(vector<double>& list, int first, int last)
{
    if (first < last)
    {
        int index = partition(list, first, last);

        quickSort(list, first, index - 1);
        quickSort(list, index + 1, last);
    }
}

int Sorting::partition(vector<double>& list, int first, int last)
{
    double pivot = list[last - 1];
    int i = first - 1;

    for (int j = first; j < last; j++)
    {
        if (list[j] < pivot)
        {
            i++;
            swap(list[i], list[j]);
        }
        iter++;
    }
    swap(list[i], list[last - 1]);
    return i;
}

// main函数中的调用代码
Sorting quickDSort(dd);
time.startTimer();
quickDSort.quickSort();
time.stopTimer();
cout << "(quick sort) Double Iterations: " << quickDSort.getIter() << endl;
cout << time.getSeconds() << endl;

错误原因分析 #

1. 分区函数越界访问
   • 选取基准值时使用list[last - 1]，当last为0（比如空数组或单元素数组进入递归时），last-1变为-1，触发数组越界访问，直接导致段错误。
   • 基准值交换逻辑错误：原代码将list[i]与基准值交换，正确逻辑应将基准值放到i+1的位置，否则会破坏分区结构。
2. 迭代次数统计失效
   • 未确保Sorting类的iter成员变量初始化为0，导致统计结果为随机值或无法正确累加。
3. 随机数种子重复初始化
   • generateDouble函数每次调用都执行srand(time(0))，短时间多次调用会导致生成重复的随机数序列。

修复后的代码 #

1. 修正分区函数 #

int Sorting::partition(vector<double>& list, int first, int last)
{
    // 选取最后一个元素作为基准，避免last-1越界
    double pivot = list[last];
    int i = first - 1;

    for (int j = first; j < last; j++)
    {
        if (list[j] < pivot)
        {
            i++;
            swap(list[i], list[j]);
        }
        iter++; // 统计每次元素比较的迭代次数
    }
    // 将基准值放到分区后的正确位置
    swap(list[i + 1], list[last]);
    return i + 1; // 返回基准值的索引，供递归使用
}

2. 确保迭代计数器初始化 #

在Sorting类的构造函数中初始化iter为0：

class Sorting {
private:
    vector<double> listData;
    int iter;
public:
    // 构造函数初始化iter为0
    Sorting(const vector<double>& data) : listData(data), iter(0) {}
    
    // 其他成员函数声明
    int getIter() const;
    void quickSort();
    void quickSort(vector<double>& list, int first, int last);
    int partition(vector<double>& list, int first, int last);
};

3. 修正随机数种子初始化 #

将srand(time(0))移到main函数开头，仅初始化一次：

vector<double> generateDouble(int size, double min, double max)
{
    vector<double> array(size);

    for (int index = 0; index < size; ++index)
    {
        double r = (((double)rand() / (double)RAND_MAX) * (max - min)) + min;
        array[index] = r;
    }

    return array;
}

int main() {
    srand(time(0)); // 仅初始化一次随机数种子
    // ... 生成数组、调用排序等逻辑
}

验证说明 #

• 修复后，处理空数组、单元素数组或正常数组时均不会触发越界，递归调用的边界逻辑正确。
• iter初始化为0后，每次元素比较都会递增，最终能正确输出排序的迭代次数。
• 随机数种子仅初始化一次，生成的随机数序列更符合预期。

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