[数据结构与算法]数据结构实验：内部排序算法的性能分析

前言

记录下本学期的数据结构实验
本实验主要集中于比较几种内部排序算法

提示：以下是本篇文章正文内容，下面案例可供参考

一、问题描述

设计一个程序，对各种内部排序算法的关键字比较次数和移动次数进行比较。具体要求如下：
⑴ 编程实现内部排序算法：编程实现直接插入排序，希尔排序，冒泡排序，快速排序，简单选择排序，堆排序，归并排序算法。
⑵ 要求数据规模：待排序数据类型不限（整型或浮点型），读取自磁盘文件。需用多组、多规模数据进行测试并记录实验结果。例如，数据规模为：{50000,100000,250000,500000,750000}；对每组数据规模，建议至少生成5组不同的数据进行测试，以5组数据的性能平均值作为测试结果。
⑶ 评价排序的指标有：在表长相同的情况下，各种排序算法的关键字比较次数、关键字移动次数（关键字交换记为3次移动）、排序时间、排序算法的稳定性；当改变表长时，各种排序算法的性能变化情况，
⑷ 结果记录及分析：在报告中以图和表的形式记录测试结果。例如（以下表格形式仅供参考）。对不同排序算法的性能差异进行分析；提出针对不同的数据集，应该如何选择内部排序算法的建议。
⑸ 建议测试你的系统所能实现内部排序算法的数据规模上限，并针对这一问题，在报告中提出如何解决超大规模数据排序问题的思路。

二、问题分析

1.数据存储结构

如图1，定义结构体NODE，结构体内含有主关键字key，用于存储数据。

2.排序中可能面临的难点问题
（1）快速排序、归并排序的程序编写。归并排序使用的数组除了中间要合并用的是静态数组，其他都是动态数组创建的，堆创建数组本来是挺好的，可是这里却因为数据规模较大的时候，递归太深，只能用数组；快速排序对堆栈要求高，需要的堆栈太大，需要调整堆栈。
（2）交换次数的计数。题目中要求：关键字交换记为3次移动。由于没有清晰这个概念，导致后面的数据均有问题，重新编写代码并填写数据。其中，归并排序并没有交换元素，一开始我是置零处理的，但是后来发现了上述的乌龙，个人认为这里的交换次数其实是指移动次数，因此再次更改了代码和数据。

3.如何观察稳定性
本次实验的数据规模均较大，拟采用另外数据规模为20的数据组，通过debug的方式，进行分析各排序方法的稳定性。

4.数据规模的选择
在正式进行本实验之前，预先测试过不同数据规模下，各排序方法的性能情况。实验中发现，数据规模的选择不宜过小，否则排序时间太短，不利于分析比较各排序方法之间的差别；同时，数据规模的选择也不宜过大，否则排序时间太长，实验的时间会过于太长。

三、实验结果及分析

（1）实验数据描述

①数据规模：本实验的数据规模为1w、2.5w、5w、10w，为四组数据。
②磁盘文件存储格式：.txt格式。文件存储内容如图2所示。

③数据生成方法：
本实验采用随机数生成法生成数据集。首先利用rand（）函数生成指定数目的随机数存入data数组，再将数组中的元素存储到DataSet_50000.txt文件中，再通过磁盘读入函数load()从文件中读入数据并存入data数组，最后进行实验测试。具体数据见图2所示。具体实现函数如图3、4所示。

（2）实验结果

实验结果如图5、6所示。

本次实验测试了数据规模分别为1w、2.5w、5w、10w的排序情况，为了数据的稳定，每种数据规模各分为5组进行测试取平均值。
需要注意的是，归并排序原理上是将两个无序的数组合并成一个有序的数组的递归函数，并没有进行数据交换，这里的交换次数仅表示数据移动的概念。

（3）性能分析

①表格分析：
（1）由上面4张表格可以看出，随着数据规模增大，各种排序方法耗时均相应增加，交换次数和比较次数也逐渐增加。
（2）由表格数据可以看出，较快的排序算法有快速排序、堆排序、归并排序、希尔排序；较慢的排序有冒泡排序、直接插入排序、选择排序。
（3）其中我对直接插入算法中，带监视哨和不带监视哨的情况进行了测试，发现带监视哨比不带监视哨的排序时间普遍较短，比较次数也相对较少。
（4）相同数据规模下，选择排序法的比较次数相同，归并排序算法的交换次数相同。
②实验数据统计图表分析
A.比较不同排序方法的比较次数和交换次数之间的关系

ⅰ.由上图图7可知，不同排序方法，比较次数和交换次数有较大的差别。
ⅱ.其中，选择排序、直接选择排序、冒泡排序、不带监视哨的直接插入排序这四种排序方法，他们的比较次数均大于交换次数。而带监视哨的直接插入排序的比较次数和交换次数相差较小，可以忽略不计。
ⅲ.但是，快速排序、堆排序、归并排序和希尔排序此处仅能看出与其他排序方法的比较次数和交换次数的差别，即远小于其他排序方法的比较次数和交换次数，不能够比较内部的比较次数和交换次数之间的关系。因此，在去掉选择排序、直接选择排序、冒泡排序、不带监视哨的直接插入排序、带监视哨的直接插入排序这五种排序方法的干扰后，重新比较了快速排序、堆排序、归并排序和希尔排序这四种排序方法的比较次数和交换次数之间的关系。具体如下图图8所示。

ⅳ.由图8可以看出，快速排序、归并排序和希尔排序，他们的比较次数均大于交换次数，而堆排序的比较次数和归并次数相差较小。
ⅴ.由以上分析可以得知，不同排序方法在相同数据测试的情况下，得到的数据相差较大，在使用图表进行分析时，会导致部分数据被较大的掩盖了其本身的重要关系，进而影响分析的准确性和合理性。因此，根据分析之前得到的图表数据，我决定将这九组分为复杂排序和简单排序两类，即为
复杂排序类：选择排序、直接选择排序、冒泡排序、
不带监视哨的直接插入排序、带监视哨的直接插入排序
简单排序类：快速排序、堆排序、归并排序、希尔排序

B.比较不同数据规模下，不同排序方法之间的比较次数关系

四、源代码

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

#define N 25000 //元素最大个数
typedef struct {
    int key;  //主关键字
} NODE;

void creatfile(NODE data[], int *n);//创建磁盘文件

void load(NODE data[], int n);//导入磁盘文件中的信息

void prn(NODE data[], int begin, int n);//输出随机数组begin..n-1

int partition(NODE data[], int low, int high);

void quicksort(NODE data[], int low, int high);//快速排序算法

void selesort(NODE data[], int n);//选择排序

void dselesort(NODE data[], int n);//直接选择排序

void pasort(NODE data[], int n);//冒泡排序

void dpasort(NODE data[], int n);//改进的冒泡排序

void sift(NODE data[], int i, int j);

void creatheap(NODE data[], int n);//堆排序，建立大根堆

void heapsortt(NODE *data, int n);//堆排序算法

void merge(NODE data[], int low, int m, int high);//归并

void mergepass(NODE data[], int n, int length);//一趟归并算法

void mergesortt(NODE *data, int n);//自底向上的二路归并排序算法

void inser(NODE data[], int n);//直接插入排序（不带监视哨）

void sinser(NODE data[], int n);//直接插入排序（带监视哨）

void shellsort(NODE data[], int n);//希尔排序算法

void Menu(void);

long exchange_time, compare_time;

void main() {
    NODE DATA[N];
    int n, op;

    clock_t start, finish;
    double total_time;
    Menu();
    scanf("%d", &op);
    while (op != 20) {
        switch (op) {
            case 1:
                creatfile(DATA, &n);
                break;
            case 2:
                load(DATA, n);
                break;
            case 3:
                prn(DATA, 0, n);
                break;
            case 4:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t4.快速排序算法\n");
                load(DATA, n);
                start = clock();
                quicksort(DATA, 0, n - 1);
                finish = clock();
                prn(DATA, 0, n);
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                printf("比较次数：%ld\n", compare_time);printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 5:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t5.选择排序\n");
                load(DATA, n);
                start = clock();
                selesort(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 0, n);
                printf("比较次数：%ld\n", compare_time);printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 6:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t6.直接选择排序\n");
                load(DATA, n);
                start = clock();
                dselesort(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 0, n);
                printf("比较次数：%ld\n", compare_time);printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 7:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t7.冒泡排序\n");
                load(DATA, n);
                start = clock();
                pasort(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 0, n);
                printf("比较次数：%ld\n", compare_time);printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 8:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t8.改进的冒泡排序\n");
                load(DATA, n);
                start = clock();
                dpasort(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 0, n);

                printf("比较次数：%ld\n", compare_time);printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 9:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t9.堆排序算法\n");
                load(DATA, n);
                start = clock();
                heapsortt(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 1, n);
                printf("比较次数：%ld\n", compare_time); printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 10:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t10.归并排序算法\n");
                load(DATA, n);
                start = clock();
                mergesortt(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 0, n);
                printf("比较次数：%ld\n", compare_time);printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 11:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t11.直接插入排序（不带监视哨）\n");
                load(DATA, n);
                start = clock();
                inser(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 0, n);
                printf("比较次数：%ld\n", compare_time);printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 12:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t12.直接插入排序（带监视哨）\n");
                load(DATA, n);
                start = clock();
                sinser(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 1, n);
                printf("比较次数：%ld\n", compare_time);printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            case 13:
                exchange_time = 0;
                compare_time = 0;
                printf("\t\t13.希尔排序算法\n");
                load(DATA, n);
                start = clock();
                shellsort(DATA, n);
                finish = clock();
                total_time = (double) (finish - start) / CLOCKS_PER_SEC;
                prn(DATA, 0, n);
                printf("比较次数：%ld\n", compare_time);
                printf("交换次数：%ld\t", exchange_time);
                printf("运行时间：%lf s\n", total_time);
                break;
            default:
                printf("ERROR!\n");
                break;
        }
        Menu();
        scanf("%d", &op);
    }
}

//********************************************
//创建磁盘文件resource.txt
//保存100个1000以内的随机数(无重复)
//********************************************
/*void creatfile(NODE data[], int *n) {
    FILE *fp;
    int i, j, key, flag;
    unsigned seed;
    *n = N;
    if ((fp = fopen("resource.txt", "w")) == NULL) {
        printf("打开文件失败!\n");
        exit(0);
    }
    seed = time(NULL);
    srand(seed);  //设置随机种子
    for (i = 0; i < *n;) {
        key = rand() % 1000;
        flag = 1;
        for (j = 0; j <= i - 1; j++)
            if (key == data[j].key) {
                flag = 0;
                break;
            }
        if (flag)
            data[i++].key = key;
    }
    for (i = 0; i < *n; i++)
        fprintf(fp, "%d\n", data[i].key);  //写一个整数到磁盘文件
    fclose(fp);
}*/
void creatfile(NODE data[], int *n) {
    FILE *fp;
    int i, key;
    unsigned seed;
    *n = N;
    if ((fp = fopen("/Users/xiaoyee/Desktop/数据结构实验作业/实验报告/内部排序/2/DataSet_50000.txt", "w")) == NULL) {
        printf("can't open the file!\n");
        exit(0);
    }
    seed = time(NULL);
    srand(seed);  //设置随机种子
    for (i = 0; i < *n; i++) {
        key = rand() % N;
        data[i].key = key;
    }

    for (i = 0; i < *n; i++) {
        fprintf(fp, "%d\n", data[i].key);  //写一个整数到磁盘文件
    }
    fclose(fp);
}

//********************************************
//导入磁盘文件resource.txt中的信息
//将文件中的数据，存入全局数组中
//********************************************
void load(NODE data[], int n) {
    FILE *fp;
    int i;
    if ((fp = fopen("/Users/xiaoyee/Desktop/数据结构实验作业/实验报告/内部排序/2/DataSet_50000.txt", "r")) == NULL) {
        printf("打开文件失败!\n");
        exit(0);
    }
    for (i = 0; i < n; i++)
        fscanf(fp, "%d", &data[i].key);
    fclose(fp);
}

//********************************************
//输出随机数组
//********************************************
void prn(NODE data[], int begin, int n) {
    printf("\n");
    for (int i = begin; i < n; i++) {
        printf("%3d  ", data[i].key);
        if ((i + 1) % 5 == 0)
            printf("\n");
    }
}

//********************************************
//快速排序的区域划分算法
//在区间了low和high之间进行一次划分
//********************************************
int partition(NODE data[], int low, int high) {
    int i = low;
    int j = high;
    int t = data[i].key;  //t为划分的基准值
    //寻找基准点的位置
    do {
        compare_time++;
        while (t <= data[j].key && i < j) {//基准点与右半区的元素逐个比较大小
            j--;
            compare_time++;
        }
        compare_time++;
        if (i < j) //右半区中找到一个比基准点小的记录
        {
            data[i] = data[j];  //将基准点与该记录交换,将小的记录放到左半区中
            i++;
            exchange_time++;
        }
        compare_time++;
        while (data[i].key <= t && i < j) {//在基准点的左半区中搜索比它大的记录
            i++;
            compare_time++;
        }
        compare_time++;
        if (i < j) //左半区中找到一个比基准点大的记录
        {
            data[j] = data[i]; //将基准点与该记录交换,将大的记录放到右半区中
            j--;
            exchange_time++;
        }
        compare_time++;
    } while (i < j);  //如此重复,直到左右半区相接
    data[i].key = t;
    exchange_time++;
    return i;
}

//********************************************
//快速排序算法
//********************************************
void quicksort(NODE data[], int low, int high) {
    int position;
    if (low < high)   //当区间下界小于区间上届d
    {
        compare_time++;
        position = partition(data, low, high);  //将该区间分成两半,position为分界点
        quicksort(data, low, position - 1);  //对左半区进行快速排序
        quicksort(data, position + 1, high);  //对右半区快速排序
    }
}

//********************************************
//选择排序
//********************************************
void selesort(NODE data[], int n) {
    int i, j;
    NODE t;
    for (i = 0; i < n - 1; i++)  //n个数,排序n-1轮
    {
        compare_time++;
        for (j = i + 1; j < n; j++)  //选择本轮的最小值
        {
            compare_time++;
            if (data[i].key > data[j].key)  //发现更小的数,则交换
            {
                t = data[i];
                data[i] = data[j];
                data[j] = t;
                exchange_time += 3;
            }
            compare_time++;
        }//本循环结束,data[i]中是本轮找到的最小值
        compare_time++;
    }
    compare_time++;
}

//********************************************
//直接选择排序
//********************************************
void dselesort(NODE data[], int n) {
    int i, j, k;
    NODE t;
    for (i = 0; i < n - 1; i++) {
        compare_time++;
        k = i;
        for (j = i + 1; j < n; j++)//寻找本轮中的最小值
        {
            compare_time++;
            if (data[k].key > data[j].key) { //记下最小值的位置
                k = j;
                exchange_time++;
            }
        }
        compare_time++;
        //把data[i]和最小值data[k]交换
        if (k != i) {
            t = data[i];
            data[i] = data[k];
            data[k] = t;
            exchange_time += 3;
        }
        compare_time++;
    }
    compare_time++;
}

//********************************************
//冒泡排序
//********************************************
void pasort(NODE data[], int n) {
    int i, j;
    NODE t;
    for (i = 0; i < n - 1; i++) {
        compare_time++;
        for (j = 0; j < n - 1 - i; j++) {
            compare_time++;
            if (data[j].key > data[j + 1].key) {
                t = data[j], data[j] = data[j + 1], data[j + 1] = t;
                exchange_time += 3;
            }
            compare_time++;
        }
        compare_time++;
    }
    compare_time++;
}

//********************************************
//改进的冒泡排序
//********************************************
void dpasort(NODE data[], int n) {
    int i = 0, j;
    NODE t;
    int flag;
    do {
        compare_time++;
        flag = 1;
        for (j = 0; j < n - 1 - i; j++) {
            compare_time++;
            if (data[j].key > data[j + 1].key) {
                t = data[j], data[j] = data[j + 1], data[j + 1] = t;
                flag = 0;
                exchange_time += 3;
            }
            compare_time++;
        }
        compare_time++;
        i++;  //比较的轮次增1
    } while (!flag);
}

//********************************************
//筛选法,将:以结点i为根的二叉树(但所有大于i的顶点j,j都满足堆定义),调整成一个大根堆
//调整范围: 结点i---结点j
//********************************************
void sift(NODE data[], int i, int j) {
    NODE temp;
    int p = 2 * i;  //p指向i的左孩子
    int t;
    while (p <= j) //如果i的左孩子存在,则调整,否则,i是叶子,不调整
    {
        compare_time++;
        t = p;   //t指向i的左孩子
        if (p < j) {  //如果i有右孩子
            if (data[p].key < data[p + 1].key) {
                t = p + 1;  //p指向键值较大的孩子
            }
            compare_time++;
        }
        compare_time++;
        compare_time++;
        if (data[i].key < data[t].key)  //如果根i的键值比孩子小
        {
            temp = data[i];
            data[i] = data[t];
            data[t] = temp;
            i = t;   //互换后势必影响以t为根的堆的性质，所以对以t为根的堆再进行调整
            p = 2 * i;
            exchange_time += 4;
        }//将根与较大的孩子互换
        else break;  //如果根i的键值比两个孩子都大,则是大根堆,无需调整
    }

}

//********************************************
//堆排序，建立大根堆
//********************************************
void creatheap(NODE data[], int n) {
    int k;
    for (k = n / 2; k >= 1; k--) {
        compare_time++;
        sift(data, k, n);  //对非叶子结点k,利用调整算法
    }
    compare_time++;
    //使以该节点k为根的树变成大根堆
    //调整区间:(k--n)
}

//********************************************
//堆排序算法
//数据集合1--n之间的数进行堆排序
//数据元素data[0]留空
//可作为辅助变量,实现两个元素的互换
//********************************************
void heapsortt(NODE *data, int n) {
    int i;
    creatheap(data, n);  //将data中的n个元素创建成大根堆
    for (i = n; i > 1; i--)   //堆排序,data[1]中始终为无序区的最大值
    {
        compare_time++;
        data[0] = data[i];  //将根(最大值)换到无序区的末尾
        data[i] = data[1];  //data[0]作为辅助变量
        data[1] = data[0];
        exchange_time += 3;
        sift(data, 1, i - 1);  //调整无序区中的数据,使之保持大根堆性质
    }
    compare_time++;
}

//********************************************
//一次归并
//********************************************
void merge(NODE data[], int low, int m, int high) {
    int i = low, j = m + 1, p = 0;
    NODE *t;  //辅助存储空间,可采用动态申请的方式
    t = (NODE *) malloc(sizeof(NODE) * (high - low + 1));  //动态申请辅助存储空间
    while (i <= m && j <= high) { //合并
        compare_time++;
        t[p++] = data[i].key < data[j].key ? data[i++] : data[j++];
        compare_time++;
        exchange_time++;
    }
    compare_time++;
    while (i <= m) {//若前一组还有多余数据,全部复制到辅助空间
        compare_time++;
        t[p++] = data[i++];
        exchange_time++;
    }
    compare_time++;
    while (j <= high) { //若后一组还有多余数据,全部复制到辅助空间
        compare_time++;
        t[p++] = data[j++];
        exchange_time++;
    }
    compare_time++;

    for (p = 0, i = low; i <= high; i++, p++) {
        compare_time++;
        data[i] = t[p]; //从辅助空间写回到原数据空间
        exchange_time++;
    }
    compare_time++;
}

//********************************************
//一趟归并算法
//********************************************
void mergepass(NODE data[], int n, int length) {
    int i;
    for (i = 0; i + 2 * length - 1 < n; i += 2 * length) { //在data的某个区间上进行一次归并排序
        //区间下界:i,上界:i+2*length-1，两个子序列长度都为length
        //上下界分界点: i+length-1
        compare_time++;
        merge(data, i, i + length - 1, i + 2 * length - 1);
    }
    compare_time++;
    if (i + length - 1 < n - 1)  //最后一次合并时，1<=第二个子序列长度<length
        merge(data, i, i + length - 1, n - 1);
    compare_time++;
}

//********************************************
//自底向上的二路归并排序算法
//********************************************
void mergesortt(NODE *data, int n) {
    int length;
    for (length = 1; length < n; length *= 2) { //进行若干轮次的归并排序,
        //n个数,归并log2n次,分组元素个数为1,2,4,8,16....2^length
        compare_time++;
        mergepass(data, n, length);
    }
    compare_time++;
}

//********************************************
//直接插入排序（不带监视哨）
//********************************************
void inser(NODE data[], int n) {
    int i, j;
    NODE t;
    for (i = 0; i < n - 1; i++)//i表示趟数，同时0..i有序
    {
        compare_time++;
        j = i + 1;    //j代表无序区的起点，也是插入元素下标
        t = data[j]; //将待插入的结点保存到t中，防止向后移动时被覆盖
        for (; j > 0; j--)  //寻找插入点，并进行元素的移动
        {
            compare_time += 2;
            if (t.key < data[j - 1].key) { //如果前一结点的键值比待插入点大
                data[j] = data[j - 1]; //结点向后移动
                exchange_time++;
            } else break;  //否则，找到插入点
        }
        compare_time++;
        data[j] = t;  //插入待排序的结点
        exchange_time++;
    }
    compare_time++;
}

//********************************************
//直接插入排序（带监视哨）
//********************************************
void sinser(NODE data[], int n) {
    int i, j;
    for (i = 2; i <= n; i++)//i表示插入元素下标，此时1..i-1有序
    {
        compare_time++;
        j = i - 1;  //j表示比较元素下标
        data[0] = data[i];   //设置监视哨，将其设置为待插入的结点
        while (data[0].key < data[j].key)  //寻找插入点，并进行元素的移动
        {
            compare_time++;
            data[j + 1] = data[j]; //前一结点向后移动
            exchange_time++;
            j--;
        }
        compare_time++;
        data[j + 1] = data[0];  //插入待排序的结点，即监视哨的值
        exchange_time++;
    }
    compare_time++;
}

//**********************************************************
//希尔排序算法
//**********************************************************
void shellsort(NODE data[], int n) {
    int j;
    int k;
    NODE t;
    int d = n / 2;     //置初始增量为元素个数的一半
    while (d >= 1)   //依次取出各增量
    {
        compare_time++;
        for (k = d; k < n; k++)  //对每一元素实施插入排序，将其分别插入各自的分组中
        {
            compare_time++;
            t = data[k];  //保存待插入记录
            j = k - d;   //待插入记录所属分组的前一记录
            while (j >= 0 && t.key < data[j].key)  //比较两个记录的大小
            {
                compare_time++;
                data[j + d] = data[j];  //插入排序，较大的前一记录向后移动
                exchange_time++;
                j -= d;  //寻找本分组的前一记录
            }
            compare_time++;
            data[j + d] = t;  //插入一个记录
            exchange_time++;
        }
        compare_time++;
        d /= 2;  //增量减半
    }
    compare_time++;
}


void Menu(void) {
    printf("=======================MENU=========================\n");
    printf("\t\t1.创建磁盘文件\n");
    printf("\t\t2.导入磁盘文件\n");
    printf("\t\t3.输出随机数组\n");
    printf("\t\t4.快速排序算法\n");
    printf("\t\t5.选择排序\n");
    printf("\t\t6.直接选择排序\n");
    printf("\t\t7.冒泡排序\n");
    printf("\t\t8.改进的冒泡排序\n");
    printf("\t\t9.堆排序算法\n");
    printf("\t\t10.归并排序算法\n");
    printf("\t\t11.直接插入排序（不带监视哨）\n");
    printf("\t\t12.直接插入排序（带监视哨）\n");
    printf("\t\t13.希尔排序算法\n");
    printf("\t\t20.Exit.\n");
    printf("====================================================\n");
    printf("Your option:");
}