第15周 项目2_第15周项目2-程序员宅基地

问题及描述:
/*  
烟台大学计算机与控制工程学院  
  
姓名:李金朴
  
日期:2017.12.10  
  
文件名称:ycds2017  
  
问题描述:设计一个函数,产生一个至少5万条记录的数据集合。  
在同一数据集上,用直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序等算法进行排序,  
记录所需要的时间,经过对比,得到对复杂度不同的各种算法在运行时间方面的感性认识。  
  
  
输入:无  
  
  
输出:各排序算法的时间  
  
分文件  
  
  
*/    
    
//sort.h:    
    
#define MaxSize 50000      //最多的数据,取5万,只测试快速算法,可以往大调整    
    
//下面的符号常量和结构体针对基数排序    
#define Radix 10           //基数的取值    
#define Digits 10          //关键字位数    
    
typedef int KeyType;    //定义关键字类型    
typedef char InfoType[10];    
typedef struct          //记录类型    
{    
    KeyType key;        //关键字项    
    InfoType data;      //其他数据项,类型为InfoType    
} RecType;              //排序的记录类型定义    
    
typedef struct node    
{    
    KeyType data;      //记录的关键字,同算法讲解中有差别    
    struct node *next;    
} RadixRecType;    
    
void InsertSort(RecType R[],int n); //直接插入排序    
void ShellSort(RecType R[],int n);  //希尔排序算法    
void BubbleSort(RecType R[],int n); //冒泡排序    
void QuickSort(RecType R[],int n);  //快速排序    
void SelectSort(RecType R[],int n);  //直接选择排序    
void HeapSort(RecType R[],int n);  //堆排序    
void MergeSort(RecType R[],int n); //归并排序    
    
//下面函数支持基数排序    
void CreateLink(RadixRecType *&p,RecType R[],int n);   //创建基数排序用的链表    
void DestoryLink(RadixRecType *&p); //释放基数排序用的链表    
void RadixSort(RadixRecType *&p); //基数排序    
    
    
//sort.cpp:    
    
#include "sort.h"    
#include <malloc.h>    
    
//1. 对R[0..n-1]按递增有序进行直接插入排序    
void InsertSort(RecType R[],int n)    
{    
    int i,j;    
    RecType tmp;    
    for (i=1; i<n; i++)    
    {    
        tmp=R[i];    
        j=i-1;            //从右向左在有序区R[0..i-1]中找R[i]的插入位置    
        while (j>=0 && tmp.key<R[j].key)    
        {    
            R[j+1]=R[j]; //将关键字大于R[i].key的记录后移    
            j--;    
        }    
        R[j+1]=tmp;      //在j+1处插入R[i]    
    }    
}    
    
    
//2. 希尔排序算法    
void ShellSort(RecType R[],int n)    
{    
    int i,j,gap;    
    RecType tmp;    
    gap=n/2;                //增量置初值    
    while (gap>0)    
    {    
        for (i=gap; i<n; i++) //对所有相隔gap位置的所有元素组进行排序    
        {    
            tmp=R[i];    
            j=i-gap;    
            while (j>=0 && tmp.key<R[j].key)//对相隔gap位置的元素组进行排序    
            {    
                R[j+gap]=R[j];    
                j=j-gap;    
            }    
            R[j+gap]=tmp;    
            j=j-gap;    
        }    
        gap=gap/2;  //减小增量    
    }    
}    
    
//3. 冒泡排序    
void BubbleSort(RecType R[],int n)    
{    
    int i,j,exchange;    
    RecType tmp;    
    for (i=0; i<n-1; i++)    
    {    
        exchange=0;    
        for (j=n-1; j>i; j--)   //比较,找出最小关键字的记录    
            if (R[j].key<R[j-1].key)    
            {    
                tmp=R[j];  //R[j]与R[j-1]进行交换,将最小关键字记录前移    
                R[j]=R[j-1];    
                R[j-1]=tmp;    
                exchange=1;    
            }    
        if (exchange==0)    //没有交换,即结束算法    
            return;    
    }    
}    
    
//4. 对R[s]至R[t]的元素进行快速排序    
void QuickSortR(RecType R[],int s,int t)    
{    
    int i=s,j=t;    
    RecType tmp;    
    if (s<t)                //区间内至少存在两个元素的情况    
    {    
        tmp=R[s];           //用区间的第1个记录作为基准    
        while (i!=j)        //从区间两端交替向中间扫描,直至i=j为止    
        {    
            while (j>i && R[j].key>=tmp.key)    
                j--;        //从右向左扫描,找第1个小于tmp.key的R[j]    
            R[i]=R[j];      //找到这样的R[j],R[i]"R[j]交换    
            while (i<j && R[i].key<=tmp.key)    
                i++;        //从左向右扫描,找第1个大于tmp.key的记录R[i]    
            R[j]=R[i];      //找到这样的R[i],R[i]"R[j]交换    
        }    
        R[i]=tmp;    
        QuickSortR(R,s,i-1);     //对左区间递归排序    
        QuickSortR(R,i+1,t);     //对右区间递归排序    
    }    
}    
    
//4. 快速排序辅助函数,对外同其他算法统一接口,内部调用递归的快速排序    
void QuickSort(RecType R[],int n)    
{    
    QuickSortR(R, 0, n-1);    
}    
    
//5. 直接选择排序    
void SelectSort(RecType R[],int n)    
{    
    int i,j,k;    
    RecType temp;    
    for (i=0; i<n-1; i++)           //做第i趟排序    
    {    
        k=i;    
        for (j=i+1; j<n; j++)   //在当前无序区R[i..n-1]中选key最小的R[k]    
            if (R[j].key<R[k].key)    
                k=j;            //k记下目前找到的最小关键字所在的位置    
        if (k!=i)               //交换R[i]和R[k]    
        {    
            temp=R[i];    
            R[i]=R[k];    
            R[k]=temp;    
        }    
    }    
}    
    
//6. 堆排序辅助之——调整堆    
void sift(RecType R[],int low,int high)    
{    
    int i=low,j=2*i;                        //R[j]是R[i]的左孩子    
    RecType temp=R[i];    
    while (j<=high)    
    {    
        if (j<high && R[j].key<R[j+1].key)  //若右孩子较大,把j指向右孩子    
            j++;                                //变为2i+1    
        if (temp.key<R[j].key)    
        {    
            R[i]=R[j];                          //将R[j]调整到双亲结点位置上    
            i=j;                                //修改i和j值,以便继续向下筛选    
            j=2*i;    
        }    
        else break;                             //筛选结束    
    }    
    R[i]=temp;                                  //被筛选结点的值放入最终位置    
}    
    
//6. 堆排序    
void HeapSort(RecType R[],int n)    
{    
    int i;    
    RecType temp;    
    for (i=n/2; i>=1; i--) //循环建立初始堆    
        sift(R,i,n);    
    for (i=n; i>=2; i--) //进行n-1次循环,完成推排序    
    {    
        temp=R[1];       //将第一个元素同当前区间内R[1]对换    
        R[1]=R[i];    
        R[i]=temp;    
        sift(R,1,i-1);   //筛选R[1]结点,得到i-1个结点的堆    
    }    
}    
    
//7.归并排序辅助1——合并有序表    
void Merge(RecType R[],int low,int mid,int high)    
{    
    RecType *R1;    
    int i=low,j=mid+1,k=0; //k是R1的下标,i、j分别为第1、2段的下标    
    R1=(RecType *)malloc((high-low+1)*sizeof(RecType));  //动态分配空间    
    while (i<=mid && j<=high)       //在第1段和第2段均未扫描完时循环    
        if (R[i].key<=R[j].key)     //将第1段中的记录放入R1中    
        {    
            R1[k]=R[i];    
            i++;    
            k++;    
        }    
        else                            //将第2段中的记录放入R1中    
        {    
            R1[k]=R[j];    
            j++;    
            k++;    
        }    
    while (i<=mid)                      //将第1段余下部分复制到R1    
    {    
        R1[k]=R[i];    
        i++;    
        k++;    
    }    
    while (j<=high)                 //将第2段余下部分复制到R1    
    {    
        R1[k]=R[j];    
        j++;    
        k++;    
    }    
    for (k=0,i=low; i<=high; k++,i++) //将R1复制回R中    
        R[i]=R1[k];    
}    
    
//7. 归并排序辅助2——一趟归并    
void MergePass(RecType R[],int length,int n)    //对整个数序进行一趟归并    
{    
    int i;    
    for (i=0; i+2*length-1<n; i=i+2*length)     //归并length长的两相邻子表    
        Merge(R,i,i+length-1,i+2*length-1);    
    if (i+length-1<n)                       //余下两个子表,后者长度小于length    
        Merge(R,i,i+length-1,n-1);          //归并这两个子表    
}    
    
//7. 归并排序    
void MergeSort(RecType R[],int n)           //自底向上的二路归并算法    
{    
    int length;    
    for (length=1; length<n; length=2*length) //进行log2n趟归并    
        MergePass(R,length,n);    
}    
    
//以下基数排序,为了统一测试有改造    
//8. 基数排序的辅助函数,创建基数排序用的链表    
void CreateLink(RadixRecType *&p,RecType R[],int n)   //采用后插法产生链表    
{    
    int i;    
    RadixRecType *s,*t;    
    for (i=0; i<n; i++)    
    {    
        s=(RadixRecType *)malloc(sizeof(RadixRecType));    
        s->data = R[i].key;    
        if (i==0)    
        {    
            p=s;    
            t=s;    
        }    
        else    
        {    
            t->next=s;    
            t=s;    
        }    
    }    
    t->next=NULL;    
}    
    
//8. 基数排序的辅助函数,释放基数排序用的链表    
void DestoryLink(RadixRecType *&p)    
{    
    RadixRecType *q;    
    while(p!=NULL)    
    {    
        q=p->next;    
        free(p);    
        p=q;    
    }    
    return;    
}    
    
//8. 实现基数排序:*p为待排序序列链表指针,基数R和关键字位数D已经作为符号常量定义好    
void RadixSort(RadixRecType *&p)    
{    
    RadixRecType *head[Radix],*tail[Radix],*t; //定义各链队的首尾指针    
    int i,j,k;    
    unsigned int d1, d2=1;   //用于分离出第i位数字,见下面的注释    
    for (i=1; i<=Digits; i++)                  //从低位到高位循环    
    {    
        //分离出倒数第i位数字,先通过对d1=10^i取余,得到其后i位,再通过整除d2=10^(i-1)得到第i位    
        //例如,分离出倒数第1位,即个位数,先对d1=10取余,再整除d2=1    
        //再例如,分离出倒数第2位,即十位数,先对d1=100取余,再整除d2=10    
        //循环之前,d2已经初始化为1,在这一层循环末增加10倍    
        //下面根据d2,得到d1的值    
        d1=d2*10;    
        for (j=0; j<Radix; j++)                 //初始化各链队首、尾指针    
            head[j]=tail[j]=NULL;    
        while (p!=NULL)                 //对于原链表中每个结点循环    
        {    
            k=(p->data%d1)/d2;           //分离出第i位数字k    
            if (head[k]==NULL)          //进行分配    
            {    
                head[k]=p;    
                tail[k]=p;    
            }    
            else    
            {    
                tail[k]->next=p;    
                tail[k]=p;    
            }    
            p=p->next;                  //取下一个待排序的元素    
        }    
        p=NULL;                         //重新用p来收集所有结点    
        for (j=0; j<Radix; j++)             //对于每一个链队循环    
            if (head[j]!=NULL)          //进行收集    
            {    
                if (p==NULL)    
                {    
                    p=head[j];    
                    t=tail[j];    
                }    
                else    
                {    
                    t->next=head[j];    
                    t=tail[j];    
                }    
            }    
        t->next=NULL;                   //最后一个结点的next域置NULL    
        //下面更新用于分离出第i位数字的d2    
        d2*=10;    
    }    
}    
    
    
//main.cpp:    
    
#include <stdio.h>    
#include <malloc.h>    
#include <stdlib.h>    
#include <time.h>    
#include "sort.h"    
    
void GetLargeData(RecType *&R, int n)    
{    
    srand(time(0));    
    R=(RecType*)malloc(sizeof(RecType)*n);    
    for(int i=0; i<n; i++)    
        R[i].key= rand();  //产生0~RAND_MAX间的数    
    printf("生成了%d条记录\n", n);    
}    
    
//调用某一排序算法完成排序,返回排序用时    
long Sort(RecType *&R, int n, void f(RecType*, int))    
{    
    int i;    
    long beginTime, endTime;    
    RecType *R1=(RecType*)malloc(sizeof(RecType)*n);    
    for (i=0;i<n;i++)    
        R1[i]=R[i];    
    beginTime = time(0);    
    f(R1,n);    
    endTime = time(0);    
    free(R1);    
    return endTime-beginTime;    
}    
    
//调用基数排序算法完成排序,返回排序用时    
long Sort1(RecType *&R, int n)    
{    
    long beginTime, endTime;    
    RadixRecType *p;    
    CreateLink(p,R,n);    
    beginTime = time(0);    
    RadixSort(p);    
    endTime = time(0);    
    DestoryLink(p);    
    return endTime-beginTime;    
}    
    
int main()    
{    
    RecType *R;    
    int n = MaxSize;   //测试中, MaxSize取50W    
    GetLargeData(R, n);    
    printf("各种排序花费时间:\n");    
    printf("  直接插入排序:%ld\n", Sort(R, n, InsertSort));    
    printf("  希尔排序:%ld\n", Sort(R, n, ShellSort));    
    printf("  冒泡排序:%ld\n", Sort(R, n, BubbleSort));    
    printf("  快速排序:%ld\n", Sort(R, n, QuickSort));    
    printf("  直接选择排序:%ld\n", Sort(R, n, SelectSort));    
    printf("  堆排序:%ld\n", Sort(R, n, HeapSort));    
    printf("  归并排序:%ld\n", Sort(R, n, MergeSort));    
    printf("  基数排序:%ld\n", Sort1(R, n));    
    free(R);    
    return 0;    
}    

运行结果:

学习心得:

通过这次的 练习,我体 会到了算法时间复杂度的差异。


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ljp19980312/article/details/78800258

智能推荐

关于 httpUrlConnection 的 setDoOutput 与 setDoInput-程序员宅基地

httpUrlConnection.setDoOutput(true);以后就可以使用conn.getOutputStream().write()httpUrlConnection.setDoInput(true);以后就可以使用conn.getInputStream().read();get请求用不到conn.getOutputStream(),因为参数直接追加在地址后面,因此默认是fal...

qt 练习 题目3 雷达扫描_qt雷达效果源码-程序员宅基地

qt 练习 题目3 雷达扫描目的是: 修改为 qt creator 工程的1别人的源码是用的 visual studio 2019 写的我的电脑上的 环境是 visual studio 2017所以需要按照下面的配置 修改一下https://blog.csdn.net/weixin_39956356/article/details/103112448error MSB8020: 无法找到 v142 的生成工具(平台工具集 =“v142”)。若要使用 v142 生成工具进行生成,请安装 v1_qt雷达效果源码

2JavaScript词法作用域_java 词法作用域-程序员宅基地

词法作用域,eval,with,JavaScript_java 词法作用域

内存四区 & malloc/free与new/delete的区别-程序员宅基地

前言之前写了一篇关于《快速排序的4种优化》的博文,当时在验证各种情况的时候忽略内存分配的问题,导致所得到的结果分析的不全面。因为在刚开始写程序的时候将数组声明在main()里面,这样数组占用的栈空间,影响了递归的深度,也影响了程序处理的数据量(即使不用尾递归,处理的数据量也能超过4万)。在了解内存分配问题之前,先复习一下进程的概念。进程(Process)是计算机中的程序关于某数据集合上的一次运...

负样本采样及bias校准、ctr平滑-程序员宅基地

参考:https://zhuanlan.zhihu.com/p/31529643在CTR预估中,负样本采样是一种常见的特征工程方法。一般CTR预估的原始正负样本比可能达到1:1000~1:10000左右,而要获取好的效果,一般需要采样到1:5~1:15之间(VC维可推导)。我们详细分析采样对于pCTR的影响。设采样前CTR为,采样后CTR为,正样本数为,负样本数为..._负采样校准

随便推点

九宫格思维法_晓暮落枫的博客-程序员宅基地

记录:在2021-5-15晚上看到这个思维方法,觉得很有意思,在此记录一下。刚接触这个概念,可能理解不是很到位。九宫格思维法,顾名思义当然是有个九宫格呐。延伸点直接关联点延伸点直接关联点核心点直接关联点延伸点直接关联点延伸点这是一个用途非常广泛的思维方式,可以借助这个工具帮助自己快速扩展思维,从更多的角度看待问题。直接上例子:新能源车车主牌号新能源车能源车企这是我能想到的,直接与 新能源车这个核心点有关联的点,每个人_九宫格思维

RBD 导出一个image_librbd的image.read()-程序员宅基地

RBD 导出一个image_librbd的image.read()

linux搭建vsftp服务器_Linux安装配置vsftp搭建FTP的详细配置-程序员宅基地

vsftp是very secure ftp的缩写,它最初的发展理念就是构建一个安全的ftp服务。现在它确实是一个非常安全稳定的ftp服务软件,广泛用作在Unix/Linux操作系统中,作为文件服务器使用。安装vsftp这里演示使用yum安装,该软件非常的小,总大小不到1M。# yum install vsftpd通过systemctl来开启vsftp# systemctl start vsftpd..._linux version 3.10.0-1160.90.1.el7.x86_64 安装vsftp

java蓝桥杯之特殊回文数-程序员宅基地

问题描述  123321是一个非常特殊的数,它从左边读和从右边读是一样的。   输入一个正整数n, 编程求所有这样的五位和六位十进制数,满足各位数字之和等于n 。输入格式  输入一行,包含一个正整数n。输出格式  按从小到大的顺序输出满足条件的整数,每个整数占一行。样例输入52样例输出899998 989989 998899数据规模和约定  1&lt;=n&lt;=54。 ...

jQuery——怎么解决多库共存的问题_jquery解决多库共存问题_Try Tomato的博客-程序员宅基地

jQuery现在已经慢慢的淡出了我们的视界,越来越多的库、越来越多的工具,在帮助我们解决了很多问题的同时,更新迭代真的很快,有的工具也就辉煌那么一阵子我们知道jQuery使用的是$标识符,$这个符号还是比较火的,那么必然有其他的的库会用$作为标识符,那么这时就会造成一种混乱,引起一些冲突所以我们使用jQuery与其他库共存时,就需要一个能实现不冲突的一个需求,那么这个解决方案就叫做多库共存其实我们在jQuery中标识符不仅仅可以使用$,还可以使用jQueryjQuery("element"_jquery解决多库共存问题

httprunner学习1-环境搭建-程序员宅基地

环境配置:centos7python3.6mysql5.7django2环境搭建前准备:先找到系统的python安装在哪个目录,查看对应版本号和相关安装包cd / 先回到根目录whereis python 查看python所在目录/usr/bincd /usr/bin 切到python目录ll python* 查看python开头的相关文件详情yum安装依赖>...