自己搞排序算法测试用例！

用户6557940

发布于 2022-07-24 16:28:46

1.1K0

发布于 2022-07-24 16:28:46

文章被收录于专栏：Jungle笔记

每次写完一个排序算法，比如冒泡排序、选择排序，总是要验证一下算法是否正确。如何验证呢？代码里创建一个数组arr[10]，如下：

  int arr[10] = { 10, 220, 3, 45, 0, 11, -1, 99, 84, 101 };
  // 测试选择排序算法
  SelectionSort(arr, 10);
  for (int i = 0; i < 10; i++){
    cout << arr[i] << "  ";
  }
  cout << endl;

如果打印出来的序列是有序的，这说明自己编码的排序算法对这个测试用例是正确的。但更多情况下，可能需要更多的测试用例，或者序列元素个数更大（50,100，甚至成千上万），这个时候还手写数组arr吗？显然很耗费时间。那不妨，搞一个生成排序算法测试用例的东西？

生成随机数

要保证序列中元素的无序，即随机，需要用到C中的 rand() 函数来生成随机数。但不能直接使用rand()，否则每次该函数生成的数字是一样的。这是因为rand()函数产生的随机数是伪随机数，是根据一个数值（种子）按照某个公式推算出来的。而这个种子在电脑启动后是不变的。所以要用srand函数修改这个种子。

    srand(time(NULL)); 
    for (int i = 0; i < n; i++){
      // 生成随机数
      arr[i] = rand() ;
    }

限定随机数范围

也许还希望生成的随机数能够限定在某个范围[Left, Right]里，那就再用一个求余运算，再加上一个偏移Left：

    // 设置随机种子
    srand(time(NULL));
    for (int i = 0; i < n; i++){
      // 生成随机数
      arr[i] = rand() % (Right - Left + 1) + Left;
    }
    return arr;

这样就ok了，不过我们默认Left <= Right。万一写错了呢？为避免这种情况，最好是在进行上述for循环之前做个判断：

if (Right < Left){
    cout << "error: wrong parameters!" << endl;
    abort();
  }

不过总觉得上述代码有点累赘，那直接用个assert：

assert(rangeL <= rangeR);

assert会计算括号里的表达式是否为真，表达式值为假（即为0），那么它先向stderr打印一条出错信息，然后通过调用 abort 来终止程序运行。

排序算法测试用例生成函数

综上所述，排序算法测试用例的生成函数的代码如下：

  // 生成有n个元素的随机数组，每个元素的随机范围为[rangeL, rangeR]
int* generateRandomArray(int n, int Left, int Right){
    assert(Left <= Right);
    int *arr = new int[n];

    // 设置随机种子
    srand(time(NULL));
    for (int i = 0; i < n; i++){
      // 生成随机数
      arr[i] = rand() % (Right - Left + 1) + Left;
    }
    return arr;
  }

生成比较有序的序列

有时候，我们需要测试一些算法对已经比较有序的序列的排序性能，这时候需要生成一个比较有序的序列。怎么办呢？这么办：

// 生成近乎有序的数据
  int* generateNearlyOrderedArray(int n, int swapTimes){
    int *arr = new int[n];
    for (int i = 0; i < n; i++){
      arr[i] = i;
    }
    srand(time(NULL));
    for (int i = 0; i < swapTimes; i++){
      int posx = rand() % n;
      int posy = rand() % n;
      swap(posx, posy);
    }
    return arr;
  }

入口参数swapTimes表示对一个完全有序的序列中的元素进行交换的次数。交换次数越少，这个序列有序度越高。

复制序列

有时候需要比较多个排序算法对同一个未排序序列的运算性能，那不妨再new一个空间，使用memcpy复制一下第一次生成的原始序列：

  int* copyArr(int inputArr[], int n){
    int* outputArr = new int[n];
    memcpy(outputArr, inputArr, sizeof(int)*n);
    return outputArr;
  }

缺憾之处在于，上面3个函数中都使用了new，那么在每次调用该函数后，务必要delete，而且是delete数组：

int *arr1 = SortTestHelper::generateRandomArray(n, 0, n);
// do something on arr1
delete[] arr1;

判断排序后的序列是否有序

如何来判断经过排序后的序列是否真的是有序了呢?不妨设计个函数isSorted：

  bool isSorted(int arr[], int n){
    for (int i = 0; i < n-1; i++){
      if (arr[i] > arr[i + 1]){
        return false;
      }
    }
    return true;
  }

测试排序算法性能

总得测试下排序算法的性能吧，这里的性能指的是时间。那就在排序前后记个时间，相减得到的时间差就ok：

  void testSort(string sortName, void(*sort)(T[], int), T arr[], int n){
    clock_t startTime = clock();
    sort(arr, n);
    clock_t endTime = clock();

    assert(isSorted(arr, n));
    cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
  }

测试结果

这样一来，就可以直接测试下已经写好的排序算法性能了：

  int n = 10000;
  int *arr1 = generateRandomArray(n, 0, n);
  int *arr2 = copyArr(arr1, n);
  int *arr3 = copyArr(arr1, n);
  int *arr4 = copyArr(arr1, n);
  testSort("SelectionSort", SelectionSort, arr1, n);
  testSort("InsertSort", InsertSort2, arr2, n);
  testSort("BubbleSort", BubbleSort, arr3, n);
  testSort("ShellSort1", ShellSort1, arr4, n);

  delete[] arr1;
  delete[] arr2;
  delete[] arr3;
  delete[] arr4;