如何构建评测机制

生成随机数

调用void srand(unsigned int seed); && int rand(void);可以生成随机数，注意如果使用了相同的种子，那么每次生成的随机数都是相同的，因此，实际使用的时候基本上都是通过设置时间 time()为种子，来生成随机数；

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(){
    srand((unsigned) time(NULL) );
    for(int i=0; i<20; ++i){
        printf("%d\n", rand());
    }
    return 0;
}

为了生成一定范围内的随机数，例如 \([m, n)\) 范围内的，可以通过调整 rand() 来实现；

int ran_num = rand() % (n-m+1) + m ;
// %(n-m+1) 保证生成 [0, n-m] 内的随机数；
// +m 保证最小的随机数为：m， 最大的随机数为：n - m + m = n;

多个随机数组验证

有了生成随机数的方法，我们即可生成随机数组，用来验证自己的排序算法的效率；

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 100

int main(){
    srand((unsigned) time(NULL) );
    // 用于指定随机数上下边界。
    int n = 78;
    int m = 11;
    
    int test_1[SIZE] = {0};
    for(int i=0; i<SIZE; ++i){
        test_1[i] = rand() % (n-m+1) + m;
        for(int j=0; j<test_1[i]; ++j){
            printf("*");
        }
        printf("\n");
    }
    return 0;
}

为了使结果更加直观，我让每行都输出横条，脑袋拧一下看，看起来就像是条形图一样，很带感，还很有利于水博客文章长度；

********************************
************************
**************************************************************
*************************************************************
*************
***************************************
**********************************************************
*************************************
**************************************************
*****************************************************************
******************
***************************************************************************
**********************************
*************************************************************
*****************************************
********************************************************************
******************************************************
**************************************************************
**********************************************************
*************************************************

排序一下，大概是这个样子：

*****************
******************
*******************
*******************
********************
********************
********************
*********************
*********************
**********************
***********************
************************
**************************
**************************
***************************
****************************
*****************************
******************************
******************************
*******************************
*******************************

生成随机数组完成；

评价指标

目前我也只简单的输出了交换次数的指标，其他的等到后面的小节会进行补充，上述的完整实验代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 100

int main(){
    srand((unsigned) time(NULL) );
    // 用于指定随机数上下边界。
    int n = 78;
    int m = 11;

    int test_1[SIZE] = {0};
    for(int i=0; i<SIZE; ++i){
        test_1[i] = rand() % (n-m+1) + m;
    }
    int count = 0;
    for(int i=0; i<SIZE; ++i){
        for(int j=0; j<SIZE-1-i; ++j){
            if(test_1[j]>test_1[j+1]){
                int temp = test_1[j];
                test_1[j] = test_1[j+1];
                test_1[j+1] = temp;
                ++count;
            }
        }
    }
    for(int i=0; i<SIZE; ++i){
        for(int j=0; j<test_1[i]; ++j){
            printf("*");
        }
        printf("\n");
    }
    printf("交换次数为：%d 次", count);
    return 0;
}

为了方便后续使用，进行封装：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int* rand_arr_gen(int size, int low, int high){
    int* arr = (int*)malloc(sizeof(int) * size);
    srand((unsigned) time(NULL) );
    for(int i=0; i<size; ++i){
        arr[i] = rand() % (high-low+1) + low;
    }
    return arr;
}

void pop_sort(int* arr, int size){
    for(int i=0; i<size; ++i){
        for(int j=0; j<size-1-i; ++j){
            if(arr[j]>arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void test(int* arr, int size){
    for(int i=0; i<size; ++i){
        printf("%d", arr[i]);
        if(i != size-1){
            printf(", ");
        }
    }
}
int main(){
    int* test_1 = rand_arr_gen(50, 1, 91);
    pop_sort(test_1, 50);
    test(test_1, 50);
    return 0;
}

Qsort

#include <stdlib.h>
void qsort(void* base, size_t num, size_t size, int (*compare)(cons void*, const void*));

是一种方便快捷的排序函数，他一共有四个参数：

• void* base：任意类型的数组，即待排数组；
• size_t num：size_t 是一种系统定义的 int，num 表示数组的大小；
• size_t size：表示每个元素的大小，单位是 字节；
• int (*compare)(cons void*, const void*)：是一个函数指针，用于比较；

比较函数的 demo 如下：

int compare(const void* a, const void* b){
   int* pa = (int*)a;
   int* pb = (int*)b;
   int num1 = *pa;
   int num2 = *pb;
   return num1 - num2;
}
//非递减顺序快排
/*	这个看起来更简洁
int compare(const void* a, const void* b){
    return *(int*)a - *(int*)b;
}
*/
int main(){
    int* test_1 = rand_arr_gen(50, 1, 91);
    qsort(test_1, 50, sizeof(int), compare);
    test(test_1, 50);
    return 0;
}

使用 qsort() 对结构体进行排序：

point.txt
   Raul 68 29 41
   Shelley 100 99 98
   Pigpig 23 59 12
   Qwq 97 10 18

typedef struct {
    char name[30];
    int Chinese;
    int math;
    int English;
} student;

student Stus[4];

void readDATA(){
    FILE* fp = fopen("./point.txt", "r");
    for(int i=0; i<4; ++i){
        fscanf(fp, "%s", Stus[i].name);
        fscanf(fp, "%d", &Stus[i].Chinese);
        fscanf(fp, "%d", &Stus[i].math);
        fscanf(fp, "%d", &Stus[i].English);
    }
    fclose(fp);
}

void display(){
    for(int i=0; i<4; ++i){
        printf("%s\t", Stus[i].name);
        printf("%d\t", Stus[i].Chinese);
        printf("%d\t", Stus[i].math);
        printf("%d\t", Stus[i].English);
        printf("\n");
    }
    printf("\n");
    printf("\n");
}

int cmp_math(const void* a, const void* b){
    if((*(student*)a).math > (*(student*)b).math){
        return 1;
    }else{
        return -1;
    }
}
int main(){
    readDATA();
    display();
    qsort(Stus, 4, sizeof(student), cmp_math);
    display();
    return 0;
}

output:
	Qwq	97	10	18	
	Raul	68	29	41	
	Pigpig	23	59	12	
	Shelley	100	99	98