logo资料库

数据结构课程设计-内部排序算法的性能分析.doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.13M 资料格式：doc 举报 版权申诉
第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
资料共23页，剩余部分请下载后查看
    1 问题描述
    设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数
    2 需求分析
    2．1原理
    2．2要求
    3 概要设计
    3．1抽象数据类型定义
    3．2子程序及功能要求
    3．3各程序模块之间的调用关系
    主函数调用子程序1。
    子程序1调用子程序2，3，4，5，6，7。
    主函数调用子程序2，2，4，5，6，7。
    4详细设计
    4．1设计相应数据结构
    4．2主要模块的算法描述
    4.2.1冒泡排序子程序流程图
    4.2.2插入排序子程序流程图
    4.2.3希尔排序子程序流程图
    4.2.4归并排序子程序流程图
    4.2.5快速排序子程序流程图
    4.2.6堆排序子程序流程图
    4.2.7系统流程图
    5 测试分析
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
    41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
    61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
    81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
    输入100个数据分五组比较，待排序表长为100，关键字比较结果如下：
    冒泡排序比较次数4950，移动次数6553701。
    插入排序比较次数12845154，移动次数6553701。
    希尔排序比较次数49，移动次数6553701。
    选择排序比较次数4950，移动次数6553701。
    快速排序比较次数1049，移动次数1114。
    堆排序比较次数71566300，移动次数112458500。
    6 课程设计的总结与体会
    参考文献
    附录（源程序清单）
    #include /*进行头文件的声明并对数据进行初始化*/
    #include
    #define N 100
    typedef int KeyType;/*运用结构体定义指针变量*/
    typedef struct rec
    {
    KeyType key;
    }rec;
    typedef struct rec sqlist[N];
    int p,q;
    /*冒泡排序*/
    void mergelist(sqlist a,int n)/*随机输入数据*/
    {int i;
    for(i=0;i
    {
    a[i].key=random(1000);
    }
    }
    void gensort(int b[],int n)
    {
    int i,j;int s=0,t=0;/*定义数据类型并初始化*/
    for(i=0;i
    {
    for(j=i+1;j
    {
    t++;
    if(b[i]>b[j])
    {
    int temp=b[i];
    b[i]=b[j];
    b[j]=temp;
    s+=3;
    }}}
    printf("\ngensort t=%ld,s=%ld\n",t,s);/*输出结果*/
    }
    }
    /*插入排序*/
    typedef int KeyType;/*定义指针类型与结构类型*/
    struct rec
    {
    KeyType key;
    };
    typedef rec sqlist[N];
    void insertsort(sqlist b,int n)
    {
    int i,j;int s=0,t=0;/*定义数据类型并初始化*/
    for(i=2;i
    {
    b[0]=b[i];/*b[0]是循环结束标志*/
    s++;
    j=i-1;
    t++;
    while(b[0].key
    {
    b[j+1]=b[j];
    j--;
    s++;
    t++;
    }
    b[j+1]=b[0];/*在j+1位置上插入r[i]*/
    s++;
    }
    printf("\nInsertSort t=%ld,s=%ld\n",t,s);/*输出结果
    }
    /*希尔排序*/
    void shellsort(sqlist b,int n)
    {
    int i,j,gap;/*定义数据类型*/
    rec x;
    int s=0,t=0;
    gap=n/2;/*设置增量初值*/
    while(gap>0)
    {
    for(i=gap+1;i
    {
    j=i-gap;
    while(j>0)
    {
    t++;
    if(b[j].key>b[j+gap].key)
    {
    x=b[j];b[j]=b[j+gap];/*将b[j]与b[j+gap]进行交换*/
    b[j+gap]=x;j=j-gap;
    s+=3;
    }
    else j=0;
    gap=gap/2;/*减小增量*/
    }}
    printf("\nshellsort t=%ld,s=%ld\n",t,s);
    }}
    /*选择排序*/
    void selectsort(int b[],int n)
    {
    int i,j,k;/*定义数据类型并初始化*/
    int s=0,t=0;
    for(i=0;i
    {k=i;
    for(j=i+1;j
    {
    t++;
    if(b[k]>b[j]) /*用k指出每趟在无序区段的最小元素*/
    {k=j;}
    }
    if(k!=i)
    {int temp=b[k];
    b[k]=b[i];/*找到最小值后进行交换*/
    b[i]=temp;
    s+=3;
    }}
    printf("\nSelectSort t=%ld,s=%ld\n",t,s);/*输出结果*/
    }
    /*快速排序*/
    void output(sqlist b,int n)/*输出元素值*/
    {
    for(int i=0;i
    printf(“%4d”,b[i].key”);
    printf(“endl”);
    }
    void display(int n,int m)/*输出计数*/
    {
    printf("\n t=%ld,s=%ld\n",s,t);
    }
    void BeforeSort()/*初始化计数器*/
    {
    p=0;q=0;
    }
    void quicksort(sqlist r,int s,int t)
    {
    int i=s,j=t;/*定义数据类型并初始化*/
    if(s
    {
    r[0]=r[s];p++;
    while(i
    {
    p++;
    while(i=r[0].key)/*比较*/
    j--;
    r[i]=r[j];
    q++;
    p++;
    p++;
    while(i
    i++;
    r[j]=r[i];q++;p++;
    }
    r[i]=r[0];p++;
    }
    else return;
    quicksort(r,s,j-1);
    quicksort(r,j+1,t);
    printf(“quicksort p=%d,q=%d”,p,q);
    }
    void sort(sqlist r,int s,int t)
    {
    BeforeSort();
    quicksort(r,s,t);
    display(p,q);
    }
    /*堆排序*/
    void sift(sqlist r,int s,int m)
    {
    int j;
    rec x;
    x=r[s];
    for(j=2*i;j<=m;j*=2)/*r(j)是r(s)的左结点*/
    {q++;
    if(j
    ++j;
    q++;
    if(!(x.key
    r[s]=r[j];s=j;p++;}/*将r[j]调到父结点的位置上，并修改s与j的值，以便继续向
    r[s]=x;p++;/*被筛结点的值放入最终位置*/
    }
    void heapsort(sqlist &r,int m)
    {
    int i;rec w;
    for(i=m/2;i>0;--i) /*建立初始堆*/
    sift(r,i,m);
    for(i=m;i>1;--i)/*进行n-1次循环，完成堆排序*/
    {
    w=r[i];r[i]=r[1];/*将第一个元素同当前区间内最后一个元素对换*/
    r[1]=w;
    p+=3;
    sift(r,1,i-1);/*筛r[1]结点，得到（i-1）个结点的堆*/
    }
    }
    void sorting(sqlist &r,int t)
    {
    BeforeSort();
    heapsort(r,t);
    display(p,q);}
    void main()
    {
    int a1[N],i;
    int e=N;
    for(i=0;i
    {a1[i]=e--;}
    printf("排序前数组:\n")
    for(i=0;i
    printf(“%4d”,a1[i]”);
    printf("endl")
    sqlist a,b;
    printf("起泡排序运行结果:\n");
    gensort(a1,sizeof(a1)/sizeof(int));
    printf("插入排序运行结果:\n");
    e=N;
    for(i=0;i
    {
    a[i].key=e--;
    }
    insertsort(a,N);
    e=N;
    for(i=0;i
    {
    b[i].key=e--;}
    printf("希尔排序运行结果:\n");
    shellsort(b,N);
    printf("选择排序运行结果:\n");
    e=N;
    int c1[N];
    for(i=0;i
    c1[i]=e--;
    selectsort(c1,N);
    printf("快速排序运行结果:\n");
    e=N;
    sqlist c;
    int low=0,high=10;
    for(i=0;i
    {
    c[i].key=e--;
    }
    sort(c,low,high);
    printf("堆排序运行结果:\n");
    sqlist d;
    e=N;
    for(i=0;i
    d[i].key=e--;
    sorting(d,N);
    printf("排序后数组:\n");
    for(i=0;i
    printf("%4d”,a1[i]);
    printf("endl");
    e=1;
    for(i=0;i
    {a1[i]=e++;}
    printf("排序前数组:\n");
    for(i=0;i
    printf("%4d”,a1[i]);
    printf("endl");
    printf("起泡排序运行结果:\n");
    gensort(a1,sizeof(a1)/sizeof(int));
    prinft("插入排序运行结果:\n");
    e=1;
    for(i=0;i
    {a[i].key=e++;}
    insertsort(a,N);
    e=1;
    for(i=0;i
    {
    b[i].key=e++;
    }
    printf("希尔排序运行结果:\n");
    shellsort(b,N);
    printf("选择排序运行结果:\n");
    e=1;
    for(i=0;i
    c1[i]=e++;
    selectsort(c1,N);
    printf("快速排序运行结果:\n");
    e=1;
    for(i=0;i
    {c[i].key=e++;}
    sort(c,low,high);
    printf("堆排序运行结果:\n");
    e=1;
    for(i=0;i
    d[i].key=e++;
    sorting(d,N);
    printf("排序后数组:\n");
    for(i=0;i
    printf("%4d”,a1[i]);
    printf("endl");
    printf("排序前数组:\n");
    for(i=0;i
    printf("%4d”,a1[i]);
    printf("endl");
    printf("起泡排序运行结果:\n");
    gensort(a1,sizeof(a1)/sizeof(int));
    printf("插入排序运行结果:\n");
    insertsort(a,N);
    printf("希尔排序运行结果:\n");
    shellsort(b,N);
    printf("选择排序运行结果:\n");
    selectsort(c1,N);
    printf("快速排序运行结果:\n");
    quicksort(c,low,high);
    printf("堆排序运行结果:\n");
    sorting(d,N);
    printf("排序后数组:\n");
    for(i=0;i
    printf("setw(4),a1[i]");
    printf("endl");
    getch();
    }
    目 录 1 问题描述 .................................................1 2 需求分析 .................................................1 3 概要设计 .................................................2 3．1 抽象数据类型定义 ................................................. 2 3．2 子程序及功能要求 ................................................. 2 3．3 各程序模块之间的调用关系 ......................................... 3 4 详细设计 ................................................ 3 4．1 设计相应数据结构 ................................................. 3 4．2 主要模块的算法描述 ............................................... 4 5 测试分析 ................................................11 6 课程设计的总结与体会 ................................... 12 参考文献 ..................................................12 附录（源程序清单） ........................................20
    1 问题描述 设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排 序、堆排序算法的关键字比较次数和移动次数以取得直观感受（待排序表的表长不小 于 100，表中数据随机产生，至少用 5 组不同数据作比较，比较指标有：关键字参 加比较次数和关键字的移动次数（关键字交换记为 3 次移动））。 2 需求分析 2．1 原理 该程序所做的工作的是，设计一个测试程序比较六种内部排序算法的关键字比较 次数和移动次数以取得直观感受，此程序规定： 试通过随机数据比较各算法的关键字比较次数和关键字的移动次数对以下六种 内部排序算法进行比较：希尔排序，直接选择排序，快速排序，注解插入排序，堆排 序，冒泡排序。待排序表的表长和数据可以由用户自己确定（待排序表的表长不小于 100，表中数据随机产生），也可以由随机数产生程序自动生成；至少要用五组不同 的输入数据做比较；比较的指标为关键字的比较次数和关键字的移动次数（关键字的 交换计为 3 次移动）。 2．2 要求 (1)熟悉对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序 算法进行比较； (2)理解待排序表的表长不小于 100，表中数据随机产生，至少用 5 组不同数据 作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为 3 次移动）； (3)熟悉内部排序的运行环境。 (4)熟练掌握 C 语言，调用各排序子程序和主函数进行读写数据的操作。 1
    3 概要设计 3．1 抽象数据类型定义 在程序的开头部分是声明了数据结构类型与数据类型，并分析子函数与主函数 的调用关系，并进行基本操作。 （ADT OrderableList{ 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为 n，元素值依次为 1，2，…，n 的有序表。 Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对 L 种的每个元素调用函数 visit( ) }ADT OrderableList 3．2 子程序及功能要求 （1）bubblesort(struct rec r[],int n)：扫描数据清单，寻找出现乱序的两个相邻的 项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所 有的项目都按顺序排好。 （2）insertsort(struct rec r[],int n)：经过 i-1 遍处理后,L[1..i-1]己排好序。第 i 遍处理仅将 L[i]插入 L[1..i-1]的适当位置，使得 L[1..i]又是排好序的序列。要达到 2
    这个目的，我们可以用顺序比较的方法。首先比较 L[i]和 L[i-1]，如果 L[i-1]≤ L[i]， 则 L[1..i]已排好序，第 i 遍处理就结束了；否则交换 L[i]与 L[i-1]的位置，继续比 较 L[i-1]和 L[i-2]，直到找到某一个位置 j(1≤j≤i-1)，使得 L[j] ≤L[j+1]时为止 （3）selectsort(struct rec r[],int n)：首先找到数据清单中的最小的数据，然后将 这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换 位置，以此类推。 （4）quicksort(struct rec r[],int s,int t): 通常分割点的数据是随机选取的。这样无 论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两 个子列表的大小差不多。 (5)shellsort(JD r[], int n):每次以不同的增量分组进行插入排序，在最后一次插入 排序排序时，所以键值“几乎”有序。 (6) sift(struct rec r[],int l,int m): 在排序过程中，将 R[1..N]看成是一颗完全二叉 树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最 小的元素。 3．3 各程序模块之间的调用关系 主函数调用子程序 1。 子程序 1 调用子程序 2，3，4，5，6，7。 主函数调用子程序 2，2，4，5，6，7。 4 详细设计 4．1 设计相应数据结构 （1）结构体表示的指针的定义 typedef int KeyType;/*定义一个指针类型*/ typedef struct rec/*运用一个结构体*/ { KeyType key; }rec; typedef struct rec sqlist[N];/*用结构体定义一个链表*/ int p,q; 3
    4．2 主要模块的算法描述 4.2.1 冒泡排序子程序流程图 N 结 束 开 始 exchange exchange Y bound=exchange exchange=0 j=1 Y jr[j+1] Y 交换 r[j]和 r[j+1]的值 exchange=j N j=j+1 4
    4.2.2 插入排序子程序流程图 结 束 r(j+1)~r(j) j~j-1 开 始 i=1 i
    4.2.3 希尔排序子程序流程图 开 始 s~n/2 s<1 按距离 s，对数组 d 分成的子序列， 结 束 6
    4.2.4 归并排序子程序流程图 开 始 FOR 循环初 始化 读入待排记录 调 用 MERGESORT 过程进行归并排序 FOR 循环输出 排序结果 结 束 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料