递归/迭代快速排序耗时异常原因及C++绘图方案咨询

问题背景 #

计算机工程大二学生课程作业要求：测试长度1-500的随机vector在递归、迭代实现的快速排序下的耗时，原本预期迭代版本更快，但实测结果递归版本略快，怀疑算法或计时逻辑存在问题；同时需要C++绘图的可行方案。硬件配置为Ryzen 7 6800H 3.2GHz CPU、DDR5 4800MHz 16GB RAM。

用于计时的C++代码 #

#include <vector>
#include <random>
#include <iostream>
#include <sstream>
#include <limits>
#include <chrono>
#include <array>
#include <fstream>
#include <numeric>
#include <stack>

using namespace std;
using namespace std::chrono;

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

//function to partition the array
int partition(vector<int>& arr, int low, int high) {
    //pick the rightmost element as a pivot from the array
    int pivot = arr[high];
    int partIndex = low;

    for (int i = low; i < high; i++) {
        //if current element is smaller than or equal to the pivot
        if (arr[i] <= pivot) {
            swap(arr[i], arr[partIndex]);
            partIndex++;
        }
    }
    swap(arr[partIndex], arr[high]);
    return partIndex;
}

//recursive quick sort function
void recursivequickSort(vector<int>& arr, int low, int high) {
    //when low is less than high
    if (low < high) {
        int partIndex = partition(arr, low, high);
        //smaller elements than pivot go left and
        //higher elements go right
        recursivequickSort(arr, low, partIndex - 1);
        recursivequickSort(arr, partIndex + 1, high);
    }
}

//iterative Quicksort routine
void iterativeQuicksort(vector<int>& arr, int n)
{
    //create a stack of std::pairs
    stack<pair<int, int>> s;

    //get the low and high index of the given array
    int low = 0;
    int high = n - 1;

    //push the low and high index of the array into the stack
    s.push(make_pair(low, high));

    //loop till stack is empty
    while (!s.empty())
    {
        low = s.top().first, high = s.top().second;
        s.pop();

        //rearrange elements across pivot
        //lower to left, higher to right
        int pivot = partition(arr, low, high);

        if (pivot - 1 > low) {
            s.push(make_pair(low, pivot - 1));
        }

        if (pivot + 1 < high) {
            s.push(make_pair(pivot + 1, high));
        }
    }
}

//write the lists to a file
void writeListToFile(const std::vector<int>& list, int length) {
    std::ofstream outputFile("processed_lists.txt", std::ios::app); // Open file in append mode

    if (!outputFile.is_open()) {
        std::cerr << "Error: Could not open the file." << std::endl;
        return;
    }

    // Write the processed list to the file
    outputFile << "list with length " << length << " = [";
    for (int i = 0; i < length - 1; ++i) {
        outputFile << list[i] << ", ";
    }
    outputFile << list[length - 1] << "]\n";

    outputFile.close(); // Close the file
}

//function to generate a random vector of given length
std::vector<int> generateRandomVector(int length) {
    std::vector<int> randomVector;

    // Seed the random number generator
    std::random_device rd;
    std::mt19937 gen(rd());

    // Define the distribution for random integers (range from -100 to 100, for example)
    std::uniform_int_distribution<int> dis(-10000, 10000);

    // Generate random elements and fill the vector
    for (int i = 0; i < length; ++i) {
        randomVector.push_back(dis(gen));
    }
    return randomVector;
}

// Function to call both iterative and recursive merge sort on a given vector and return an array with the execution times
array<double, 2> sortingComparison(vector<int>& arr, int numTrials) {
    // Copy the input vector for recursive merge sort
    vector<int> recursiveArr = arr;
    vector<int> iterativeArr = arr;

    vector<int> quickRecursiveTimes;
    vector<int> quickIterativeTimes;

    for (int i = 0; i < numTrials; i++) {

        auto startIterative = high_resolution_clock::now();
        iterativeQuicksort(iterativeArr, iterativeArr.size());
        auto stopIterative = high_resolution_clock::now();
        auto quickIterativeTime = duration_cast<microseconds>(stopIterative - startIterative);
        quickIterativeTimes.push_back(quickIterativeTime.count());

        auto startRecursive = high_resolution_clock::now();
        recursivequickSort(recursiveArr, 0, recursiveArr.size() - 1);
        auto stopRecursive = high_resolution_clock::now();
        auto quickRecursiveTime = duration_cast<microseconds>(stopRecursive - startRecursive);
        quickRecursiveTimes.push_back(quickRecursiveTime.count());

    }

    // Calculate the sum of execution times for each sorting algorithm
    long long sumQuickRecursive = accumulate(quickRecursiveTimes.begin(), quickRecursiveTimes.end(), 0LL);
    long long sumQuickIterative = accumulate(quickIterativeTimes.begin(), quickIterativeTimes.end(), 0LL);

    // Calculate the average execution time for each sorting algorithm
    double averageQuickRecursive = static_cast<double>(sumQuickRecursive) / numTrials;
    double averageQuickIterative = static_cast<double>(sumQuickIterative) / numTrials;


    // Return array containing average execution times
    return { averageQuickRecursive, averageQuickIterative};
}

int main() {
    int upperBound = 500;
    int numTrials = 5; // Number of trials for each input size

    // Create vectors to store execution times
    vector<double> quickRecursiveTimes;
    vector<double> quickIterativeTimes;

    quickRecursiveTimes.reserve(upperBound);
    quickIterativeTimes.reserve(upperBound);

    // Add time measurements to the vectors
    for (int i = 1; i <= upperBound; ++i) {
        // Generate vector with i random numbers
        vector<int> numbers = generateRandomVector(i);
        writeListToFile(numbers, numbers.size());

        // Get time measurements for each sorting algorithm
        array<double, 2> executionTimes = sortingComparison(numbers, numTrials);
        quickRecursiveTimes.push_back(executionTimes[0]);
        quickIterativeTimes.push_back(executionTimes[1]);
    }

    // Print the two lists
    cout << "Quick recursive time measurements (micro seconds): ";
    cout << "[";
    for (int i = 0; i < upperBound - 1; ++i) {
        cout << quickRecursiveTimes[i] << ", ";
    }
    cout << quickRecursiveTimes[upperBound - 1] << "]" << endl;

    cout << "Quick iterative time measurements (micro seconds): ";
    cout << "[";
    for (int i = 0; i < upperBound - 1; ++i) {
        cout << quickIterativeTimes[i] << ", ";
    }
    cout << quickIterativeTimes[upperBound - 1] << "]" << endl;

    return 0;
}

用于绘图的Python代码 #

import matplotlib.pyplot as plt
import numpy as np

# Load the data from the text file
quick_recursive_times = []  # List of recursive time measurements
quick_iterative_times =  []  # List of iterative time measurements

# Generate x-axis values (list lengths)
x_values = np.arange(1, len(quick_recursive_times) + 1)

# Plot the merge recursive time measurements in blue
plt.plot(x_values, quick_recursive_times, color='blue', label='Quick sort recursive Approach')

# Plot the merge iterative time measurements in red
plt.plot(x_values, quick_iterative_times, color='red', label='Quick sort iterative Approach')

# Label the axes and title
plt.xlabel('List Length')
plt.ylabel('Time (micro seconds)')
plt.title('Sorting Execution Time Comparison')

# Add a legend
plt.legend()

# Show grid
plt.grid(True)

# Show the plot
plt.show()

执行时间对比图 #

耗时异常原因分析 #

1. 计时逻辑的核心错误 #

sortingComparison函数中，数组复制操作放在了测试循环外部，导致仅第一次循环测试的是未排序数组，后续4次循环均对已排序数组重复排序。快速排序对已排序数组的表现与随机数组差异极大：递归版本的分区逻辑虽会触发最坏情况，但现代CPU对函数调用栈的优化抵消了部分开销；而迭代版本的手动栈操作在有序数组场景下的额外开销被放大，最终导致递归版本耗时更低。

修正方法：将vector<int> recursiveArr = arr; vector<int> iterativeArr = arr;移至for (int i = 0; i < numTrials; i++)循环内部，确保每次测试都使用原始未排序数组。

2. 迭代版本的额外常数开销 #

迭代版本使用std::stack<std::pair<int,int>>手动维护调用栈，每次压栈、弹栈都涉及pair的构造、内存分配等操作；而递归版本依赖CPU原生的函数调用栈，这是硬件高度优化的机制，开销远低于手动实现的栈结构。在1-500的小数据规模下，常数项开销对整体耗时的影响占主导，导致迭代版本更慢。

3. 小数据规模的特殊性 #

当数据量较小时，算法的渐近复杂度差异不明显，常数项开销成为影响耗时的关键。递归的函数调用栈虽有开销，但CPU的栈帧复用、指令流水线等优化让实际开销极低，反而手动栈的操作成本更高。

C++绘图可行方案 #

方案1：调用Gnuplot（轻量高效） #

1. 安装Gnuplot：Windows下载官方安装包，Linux执行sudo apt install gnuplot，macOS执行brew install gnuplot。
2. 写入数据文件：将列表长度、递归耗时、迭代耗时按行写入文本文件，格式如下：

# 列表长度 递归耗时(微秒) 迭代耗时(微秒)
1 0.2 0.3
2 0.5 0.6
...
500 12.3 15.1

3. C++调用Gnuplot：通过管道执行绘图命令，示例代码：

#include <cstdio>
#include <vector>

void plotWithGnuplot(const std::vector<int>& sizes, const std::vector<double>& recTimes, const std::vector<double>& iterTimes) {
    // 写入数据文件
    FILE* dataFile = fopen("sort_times.dat", "w");
    if (!dataFile) return;
    for (int i = 0; i < sizes.size(); ++i) {
        fprintf(dataFile, "%d %.2f %.2f\n", sizes[i], recTimes[i], iterTimes[i]);
    }
    fclose(dataFile);

    // 调用Gnuplot绘图
    FILE* gnuplotPipe = popen("gnuplot -persist", "w");
    if (!gnuplotPipe) return;

    fprintf(gnuplotPipe, "set title '快速排序耗时对比'\n");
    fprintf(gnuplotPipe, "set xlabel '列表长度'\n");
    fprintf(gnuplotPipe, "set ylabel '耗时(微秒)'\n");
    fprintf(gnuplotPipe, "set grid\n");
    fprintf(gnuplotPipe, "plot 'sort_times.dat' using 1:2 with lines title '递归版本', '' using 1:3 with lines title '迭代版本'\n");

    pclose(gnuplotPipe);
}

// 在main函数中调用
int main() {
    // ... 原有计时逻辑 ...
    std::vector<int> sizes;
    for (int i=1; i<=500; ++i) sizes.push_back(i);
    plotWithGnuplot(sizes, quickRecursiveTimes, quickIterativeTimes);
    return 0;
}

方案2：使用Matplot库（纯C实现） #

Matplot是模仿Matplotlib的C绘图库，无需外部工具，直接在代码中绘图：

1. 安装库：通过CMake从GitHub克隆编译，或使用vcpkg执行vcpkg install matplotplusplus。
2. 示例代码：

#include <matplot/matplot.h>
#include <vector>

int main() {
    using namespace matplot;
    std::vector<int> x;
    for (int i=1; i<=500; ++i) x.push_back(i);
    
    plot(x, quickRecursiveTimes, "b-", "LineWidth", 2);
    hold(on);
    plot(x, quickIterativeTimes, "r-", "LineWidth", 2);
    
    xlabel("列表长度");
    ylabel("耗时(微秒)");
    title("快速排序耗时对比");
    legend({"递归版本", "迭代版本"});
    grid(on);
    show();
    
    return 0;
}

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