C++中用rand()生成插入排序时间分析随机字符数组出错及优化建议

原始问题与初始代码 #

我刚开始学习数据结构与算法中的插入排序，编写C++程序实现后想做时间分析可视化。用rand()生成随机字符数组时，末尾总是出现多余字符——数组元素应该全是'0'-'9'这类单数字符。后来按建议改成了vector版本，求进一步优化方案。

初始实现代码 #

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <iomanip>

using namespace std;

int size(char a[]) {
    int l = 0;
    while (a[l] != NULL) {
        l++;
    }
    return l;
}

void InsertionSort(char arr[]) {
    for (int k = 1; k < size(arr); k++) {
        char temp = arr[k];
        int i = k - 1;
        while (i >= 0 && arr[i] > temp) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = temp;
    }
}

int main(void) {
    //Generate Random Arrays of size snum
    for (int k = 1; k < 100; k++) {
        int snum = k * 100;
        char Array[snum];
        srand(time(NULL));
        for (int s = 0; s < snum; s++)
        {
            int no = rand() % 9 + 1;
            Array[s] = no + '0';
        }

        cout << "START\t";
        //cout<<"\n"<<Array<<"END\n"; // Character is being Printed at the end........ :-(
        clock_t start, end;
        start = clock();

        InsertionSort(Array);
        end = clock();
        double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
        cout << "\"" << fixed << time_taken << setprecision(9) << "\",\"" << 100 * k << "\"" << endl;
    }
}

编译运行命令 #

g++ InsertionSort.cpp 
./a.out > InsertionSort.txt

改用vector后的代码 #

RandomIntVector.cpp #

#include "RandomIntVector.h"
#include <random>
#include <vector>

using namespace std;

vector<int> RandomVector(int size){
    uniform_int_distribution<> d(1, 1000);
    mt19937 gen;

    vector<int> Ar;
    for(int s=0; s<(size-1); s++)
    {
        int no = d(gen);
        Ar.push_back(no);
    }
    return Ar;
}

InsertionSort.cpp #

#include "InsertionSort.h"
#include <vector>
using namespace std;

void InsertionSort(vector<int> arr){
    int size=arr.size();
    for(int k=1;k<size;k++){
        int temp = arr[k];
        int i=k-1;
        while(i>=0 && arr[i]>temp ){
            arr[i+1]=arr[i];
            i--;
        }
        arr[i+1]=temp;
    }
}

Main.cpp #

#include <iostream>
#include <vector>
#include <chrono>
#include <iomanip>
#include "RandomIntVector.h"
#include "InsertionSort.h"

using namespace std;

int main(void){
    //Generate Random Arrays of size snum
    for(int k=1;k<100;k++){
        vector<int> Array = RandomVector(100*k);

        clock_t start, end;
        start = clock();
        InsertionSort(Array);
        end = clock();

        double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
        
        //Print the Time Taken along with the size of the Input
        cout<<"\""<<fixed << time_taken << setprecision(9)<<"\",\"" <<100*k<<"\""<<endl;
    }
    return 0;
}

针对性优化建议 #

• 随机数生成修复与优化：
  • mt19937 gen;未初始化种子，每次生成的随机序列完全相同，改成mt19937 gen(std::random_device{}());用硬件随机源初始化，或者用时间戳初始化；
  • RandomVector里循环条件s<(size-1)会少生成一个元素，导致向量实际大小比预期小1，改成s<size才能生成指定长度的随机数组。
• 插入排序性能修复：
  • 当前InsertionSort是传值调用vector，会触发整个向量的拷贝，耗时极大，改成传引用void InsertionSort(vector<int>& arr)，彻底消除拷贝开销，这对大数组的时间测试结果影响尤为明显。
• 计时精度升级：
  • 替换clock()为<chrono>库的高精度时钟，能获得更精准的计时结果，示例代码：

    auto start = chrono::high_resolution_clock::now();
    InsertionSort(Array);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> time_taken = end - start;
    double seconds = time_taken.count();
    

• 代码效率与规范优化：
  • 生成vector时提前调用Ar.reserve(size);，预留足够内存，避免push_back过程中多次内存重分配；
  • 头文件中必须包含函数声明，比如RandomIntVector.h要加std::vector<int> RandomVector(int size);，InsertionSort.h加void InsertionSort(std::vector<int>& arr);，避免编译错误；
  • 尽量避免全局using namespace std;，尤其是头文件中，防止命名冲突，源文件中可以按需使用std::前缀。
• 测试结果稳定性优化：
  • 同一大小的数组多次排序后取平均时间，插入排序的耗时受输入数据有序度影响较大，取平均值能让可视化结果更准确。

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