锐客网

  1. 首页 > it技术 > >

第十六周项目二----大数据集上排序算法性能的体验

/*烟台大学计算机与控制工程学院 作者：孙潇 时间：2015年12月19日 问题描述：设计一个函数，产生一个至少5万条记录的数据集合。在同一数据集上，用直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序等算法进行排序，记录所需要的时间，经过对比，得到对复杂度不同的各种算法在运行时间方面的感性认识。提示1：这一项目需要整合多种排序算法，可以考虑先建设排序算法库，作为我们这门课算法库的收官之作； 提示2：本项目旨在获得对于复杂度不同算法的感性认识，由于数据分布特点、计算机运行状态等不同，其结果并不能完全代替对算法复杂度的理论分析； 提示3：由于C语言标准提供的时间函数只精确到秒，几种O(nlog2n)级别的算法，在5万条记录的压力下，并不能明显地看出优劣，可以忽略直接插入排序、冒泡排序、直接选择排序这三种相对低效率的算法（以节约时间。若能够忍受他们长时间地运行，请自便），成10倍地加大数据量，然后进行观察。输入描述：无 输出描述：若干数据 */

头文件 —— sort.h


#ifndef SORT_H_INCLUDED #define SORT_H_INCLUDED#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); //基数排序#endif // SORT_H_INCLUDED

算法的实现—— sort.cpp
#include "sort.h" #include //1. 对R[0..n-1]按递增有序进行直接插入排序 void InsertSort(RecType R[],int n) { int i,j; RecType tmp; for (i=1; i=0 && tmp.key0) { for (i=gap; i=0 && tmp.keyi; j--)//比较,找出最小关键字的记录 if (R[j].keyi && R[j].key>=tmp.key) j--; //从右向左扫描,找第1个小于tmp.key的R[j] R[i]=R[j]; //找到这样的R[j],R[i]"R[j]交换 while (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-1data = https://www.it610.com/article/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; jdata%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; jnext=head[j]; t=tail[j]; } } t->next=NULL; //最后一个结点的next域置NULL //下面更新用于分离出第i位数字的d2 d2*=10; } }



测试用的主控程序——main.cpp


#include #include #include #include #include "sort.h"void GetLargeData(RecType *&R, int n) { srand(time(0)); R=(RecType*)malloc(sizeof(RecType)*n); for(int i=0; i


运行结果：
取五万条数据时
第十六周项目二----大数据集上排序算法性能的体验
文章图片

取五十万条数据时
【第十六周项目二----大数据集上排序算法性能的体验】第十六周项目二----大数据集上排序算法性能的体验
文章图片

取二百万条数据时
第十六周项目二----大数据集上排序算法性能的体验
文章图片

取四百万条数据时
第十六周项目二----大数据集上排序算法性能的体验
文章图片



?? ??

    推荐阅读


    上一篇：视图组件(继承不同类重写视图类第四层和第五层)、路由组件(修改路由的全部写法)

    下一篇：十大排序|十大排序--计数排序